Am I missing something

[Youjaes]

From an offsite conversation:


>>I think they catch potential errors with the double checking.
https://www.mersenne.org/various/mat...ouble_checking

-----

"GIMPS double-checking goes a bit further to guard against programming errors. Prior to starting the Lucas-Lehmer test, the S0 value is left-shifted by a random amount. Each squaring just doubles how much we have shifted the S value. Note that the mod 2P-1 step merely rotates the p-th bits and above to the least significant bits, so there is no loss of information. "

>>>>>
Umm, not true. From https://en.wikipedia.org/wiki/Lucas%...primality_test
>>>>>

Alternate starting values[edit]
Starting values s0 other than 4 are possible, for instance 10, 52, and others (sequence A018844 in the OEIS). The Lucas-Lehmer residue calculated with these alternative starting values will still be zero if Mp is a Mersenne prime. However, the terms of the sequence will be different and a non-zero Lucas-Lehmer residue for non-prime Mp will have a different numerical value from the non-zero value calculated when s0 = 4.

It is also possible to use the starting value (2 mod Mp)(3 mod Mp)−1, usually denoted by 2/3 for short.[1] This starting value equals (2p + 1) /3, the Wagstaff number with exponent p.

Starting values like 4, 10, and 2/3 are universal, that is, they are valid for all (or nearly all) p. There are infinitely many additional universal starting values.[1] However, some other starting values are only valid for a subset of all possible p, for example s0 = 3 can be used if p = 3 (mod 4).[2] This starting value was often used where suitable in the era of hand computation, including by Lucas in proving M127 prime.[3] The first few terms of the sequence are 3, 7, 47, ... (sequence A001566 in the OEIS).



https://oeis.org/A018844

A018844 Arises from generalized Lucas-Lehmer test for primality. 3
4, 10, 52, 724, 970, 10084, 95050, 140452, 1956244, 9313930, 27246964, 379501252, 912670090, 5285770564, 73621286644, 89432354890, 1025412242452, 8763458109130, 14282150107684, 198924689265124 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1

COMMENTS
Apparently this was suggested by an article by R. M. Robinson.

Starting values for Lucas-Lehmer test that result in a zero term (mod Mersenne prime Mp) after P-1 steps. - Jason Follas (jfollas_mersenne(AT)hotmail.com), Aug 01 2004

>>>>>>>

A quick verification using "grade-school" math The following Vb.Net program produced this output..

>>>>>>>

s[p-2] = 0 residual counts for s[0] = 2^x where x <= 100000 and p <= 31

3, 33333, 33%
5, 20000, 20%
7, 28571, 28%
13, 23077, 23%
17, 23530, 23%
19, 26316, 26%
31, 25806, 25%

7, 2^2
7, 2^4052
7, 2^18587
7, 2^23942
7, 2^27887
7, 2^49982
7, 2^53297
7, 2^70352
7, 2^77867
7, 2^83222
7, 2^96392

0, 12244
1, 30190
2, 31597
3, 18194
4, 6372
5, 1244
6, 147
7, 11


s[p-2] = 0 residual counts for s[0] = x where x <= 100000 and p <= 31

3, 28572, 28%
5, 25807, 25%
7, 25197, 25%
13, 25007, 25%
17, 24979, 24%
19, 24900, 24%
31, 25025, 25%

Mp universal starting values less than 100000 from OEIS A018844
4, 10, 52, 724, 970, 10084, 95050

7, 4
7, 10
7, 52
7, 430
7, 724
7, 970
7, 1851
7, 3202
7, 3265
7, 4442
7, 9614
7, 10084
7, 11554
7, 17798
7, 18498
7, 20611
7, 21634
7, 31686
7, 35598
7, 38090
7, 51481
7, 55548
7, 58083
7, 70690
7, 76052
7, 76745
7, 82450
7, 89989
7, 95050
7, 97863

0, 13183
1, 29491
2, 31492
3, 18064
4, 6250
5, 1324
6, 165
7, 30


Elapsed Time 39.8160247s
Done.

>>>>>>>>


Dim BeginTime = Now.Ticks

Dim Prime
Dim s0 As UInt64 '= 2

Dim ix, jx, ic, ip, s As UInt64
Dim ModP As UInt64 '= 2 ^ Prime - 1

Dim ScanType

For ScanType = 1 To 2

Const MAXSEARCH = 100000

If ScanType = 1 Then
TB2.Text &= "s[p-2] = 0 residual counts for s[0] = 2^x where x <=" & Str(MAXSEARCH) & " and p <= 31" & vbCrLf & vbCrLf
Else
TB2.Text &= "s[p-2] = 0 residual counts for s[0] = x where x <=" & Str(MAXSEARCH) & " and p <= 31" & vbCrLf & vbCrLf
End If

Dim s0Count(MAXSEARCH)
Dim MpCount = 0

For ip = 2 To 31
Prime = ip
ModP = 2 ^ Prime - 1
s0 = 2

ic = 0
For ix = 2 To MAXSEARCH
s0 = (s0 + s0) Mod ModP
s = s0
If ScanType = 2 Then s = ix
For jx = 1 To Prime - 2
If s < 2 Then s += ModP
s = (s * s - 2) Mod ModP
Next jx
If s = 0 Then ic += 1 : s0Count(ix) += 1
Next ix

If ic Then MpCount += 1 : TB2.Text &= Str(Prime) & "," & Str(ic) & "," & Str(Fix(ic / MAXSEARCH * 100)) & "%" & vbCrLf
Application.DoEvents()
Next ip

TB2.Text &= vbCrLf

If ScanType = 2 Then
TB2.Text &= "Mp universal starting values less than 100000 from OEIS A018844" & vbCrLf
TB2.Text &= "4, 10, 52, 724, 970, 10084, 95050" & vbCrLf & vbCrLf
End If

Dim Universal(MAXSEARCH)
For ix = 2 To MAXSEARCH
Universal(s0Count(ix)) += 1
If s0Count(ix) >= MpCount Then
If ScanType = 1 Then
TB2.Text &= Str(s0Count(ix)) & ", 2^" & Trim(Str(ix)) & vbCrLf
Else
TB2.Text &= Str(s0Count(ix)) & ", " & Trim(Str(ix)) & vbCrLf
End If
End If
Next
TB2.Text &= vbCrLf

For ix = 0 To MpCount + 1
If Universal(ix) Then TB2.Text &= Str(ix) & "," & Str(Universal(ix)) & vbCrLf
Next
TB2.Text &= vbCrLf & vbCrLf
Next ScanType

TB2.Text &= "Elapsed Time" & Str((Now.Ticks - BeginTime) / 10000000) & "s" & vbCrLf
TB2.Text &= "Done."

>>>>>

Am I missing something or is the Emperor not wearing any clothes and we are off to the races to reverify lower p with the proven s0=4?

James

[Viliam Furik]

I am not sure, what you think you are missing or not, but if you are talking about the double-checking of the LL results, that's done because one test can have errors (thus potentially hiding a prime), but if two tests match, with different starting shifts, then there is almost no chance of it being the incorrect result.

I hope that's enough as an answer.

[Youjaes]

Originally Posted by Viliam Furik

I am not sure, what you think you are missing or not, but if you are talking about the double-checking of the LL results, that's done because one test can have errors (thus potentially hiding a prime), but if two tests match, with different starting shifts, then there is almost no chance of it being the incorrect result.

I hope that's enough as an answer.

If you say so.

-----

p = 29, s[0] = 2^2, s[27] = 458738443
p = 29, s[0] = 2^3, s[27] = 399253392
p = 29, s[0] = 2^4, s[27] = 173583544
p = 29, s[0] = 2^5, s[27] = 356285411
p = 29, s[0] = 2^6, s[27] = 454916308
p = 29, s[0] = 2^7, s[27] = 418665456
p = 29, s[0] = 2^8, s[27] = 159352507
p = 29, s[0] = 2^9, s[27] = 124138405
p = 29, s[0] = 2^10, s[27] = 280363297
p = 29, s[0] = 2^11, s[27] = 257365289
p = 29, s[0] = 2^12, s[27] = 324441881
p = 29, s[0] = 2^13, s[27] = 196341819
p = 29, s[0] = 2^14, s[27] = 163269510
p = 29, s[0] = 2^15, s[27] = 2
p = 29, s[0] = 2^16, s[27] = 399434360
p = 29, s[0] = 2^17, s[27] = 111230369
p = 29, s[0] = 2^18, s[27] = 82827156
p = 29, s[0] = 2^19, s[27] = 231142063
p = 29, s[0] = 2^20, s[27] = 229791253
p = 29, s[0] = 2^21, s[27] = 98213813
p = 29, s[0] = 2^22, s[27] = 330020529
p = 29, s[0] = 2^23, s[27] = 300822586
p = 29, s[0] = 2^24, s[27] = 206105139
p = 29, s[0] = 2^25, s[27] = 523959422
p = 29, s[0] = 2^26, s[27] = 525969049
p = 29, s[0] = 2^27, s[27] = 247553531
p = 29, s[0] = 2^28, s[27] = 109218723

p = 31, s[0] = 2^2, s[29] = 0
p = 31, s[0] = 2^3, s[29] = 1395627816
p = 31, s[0] = 2^4, s[29] = 2
p = 31, s[0] = 2^5, s[29] = 475947287
p = 31, s[0] = 2^6, s[29] = 2
p = 31, s[0] = 2^7, s[29] = 665640517
p = 31, s[0] = 2^8, s[29] = 0
p = 31, s[0] = 2^9, s[29] = 1159698774
p = 31, s[0] = 2^10, s[29] = 0
p = 31, s[0] = 2^11, s[29] = 1085580077
p = 31, s[0] = 2^12, s[29] = 2147483645
p = 31, s[0] = 2^13, s[29] = 0
p = 31, s[0] = 2^14, s[29] = 568206011
p = 31, s[0] = 2^15, s[29] = 1022830437
p = 31, s[0] = 2^16, s[29] = 2
p = 31, s[0] = 2^17, s[29] = 1825686668
p = 31, s[0] = 2^18, s[29] = 0
p = 31, s[0] = 2^19, s[29] = 2147483645
p = 31, s[0] = 2^20, s[29] = 143692922
p = 31, s[0] = 2^21, s[29] = 870057803
p = 31, s[0] = 2^22, s[29] = 0
p = 31, s[0] = 2^23, s[29] = 106150822
p = 31, s[0] = 2^24, s[29] = 2147483645
p = 31, s[0] = 2^25, s[29] = 806493586
p = 31, s[0] = 2^26, s[29] = 0
p = 31, s[0] = 2^27, s[29] = 797013063
p = 31, s[0] = 2^28, s[29] = 2
p = 31, s[0] = 2^29, s[29] = 1073741822
p = 31, s[0] = 2^30, s[29] = 0

James

[Viliam Furik]

Originally Posted by Youjaes

If you say so.

-----

p = 29, s[0] = 2^2, s[27] = 458738443
p = 29, s[0] = 2^3, s[27] = 399253392
p = 29, s[0] = 2^4, s[27] = 173583544
p = 29, s[0] = 2^5, s[27] = 356285411
p = 29, s[0] = 2^6, s[27] = 454916308
p = 29, s[0] = 2^7, s[27] = 418665456
p = 29, s[0] = 2^8, s[27] = 159352507
p = 29, s[0] = 2^9, s[27] = 124138405
p = 29, s[0] = 2^10, s[27] = 280363297
p = 29, s[0] = 2^11, s[27] = 257365289
p = 29, s[0] = 2^12, s[27] = 324441881
p = 29, s[0] = 2^13, s[27] = 196341819
p = 29, s[0] = 2^14, s[27] = 163269510
p = 29, s[0] = 2^15, s[27] = 2
p = 29, s[0] = 2^16, s[27] = 399434360
p = 29, s[0] = 2^17, s[27] = 111230369
p = 29, s[0] = 2^18, s[27] = 82827156
p = 29, s[0] = 2^19, s[27] = 231142063
p = 29, s[0] = 2^20, s[27] = 229791253
p = 29, s[0] = 2^21, s[27] = 98213813
p = 29, s[0] = 2^22, s[27] = 330020529
p = 29, s[0] = 2^23, s[27] = 300822586
p = 29, s[0] = 2^24, s[27] = 206105139
p = 29, s[0] = 2^25, s[27] = 523959422
p = 29, s[0] = 2^26, s[27] = 525969049
p = 29, s[0] = 2^27, s[27] = 247553531
p = 29, s[0] = 2^28, s[27] = 109218723

p = 31, s[0] = 2^2, s[29] = 0
p = 31, s[0] = 2^3, s[29] = 1395627816
p = 31, s[0] = 2^4, s[29] = 2
p = 31, s[0] = 2^5, s[29] = 475947287
p = 31, s[0] = 2^6, s[29] = 2
p = 31, s[0] = 2^7, s[29] = 665640517
p = 31, s[0] = 2^8, s[29] = 0
p = 31, s[0] = 2^9, s[29] = 1159698774
p = 31, s[0] = 2^10, s[29] = 0
p = 31, s[0] = 2^11, s[29] = 1085580077
p = 31, s[0] = 2^12, s[29] = 2147483645
p = 31, s[0] = 2^13, s[29] = 0
p = 31, s[0] = 2^14, s[29] = 568206011
p = 31, s[0] = 2^15, s[29] = 1022830437
p = 31, s[0] = 2^16, s[29] = 2
p = 31, s[0] = 2^17, s[29] = 1825686668
p = 31, s[0] = 2^18, s[29] = 0
p = 31, s[0] = 2^19, s[29] = 2147483645
p = 31, s[0] = 2^20, s[29] = 143692922
p = 31, s[0] = 2^21, s[29] = 870057803
p = 31, s[0] = 2^22, s[29] = 0
p = 31, s[0] = 2^23, s[29] = 106150822
p = 31, s[0] = 2^24, s[29] = 2147483645
p = 31, s[0] = 2^25, s[29] = 806493586
p = 31, s[0] = 2^26, s[29] = 0
p = 31, s[0] = 2^27, s[29] = 797013063
p = 31, s[0] = 2^28, s[29] = 2
p = 31, s[0] = 2^29, s[29] = 1073741822
p = 31, s[0] = 2^30, s[29] = 0

James

Again, I don't know what you are trying to say with these numbers.

[Youjaes]

Originally Posted by Viliam Furik

Again, I don't know what you are trying to say with these numbers.

What you said doesn't match the facts. I posted the residuals for p = 29 and 31 and s0 equals 2^2 to 2^(p-1). The residuals don't match for shifted s0 except for s(p-2)=0 on some cases for Mp. Are you still not getting it?

[Dr Sardonicus]

It's not entirely clear to me how the double checking of an LL test using a left-shifted initial value is supposed to work. From what I have read,

1) The LL left-shifted double-check is only done when the initial LL test says the number is composite. (If the initial LL test says it's prime, the LL test is repeated by hordes of volunteers using different programs on different types of hardware.)

2) I read one place that the final "double check" residue is "adjusted" after the last iteration, to account for the original left shift of the starting value. Alas, there was no explanation of how this is done.

3) AFAICT the "adjusted" value from the double-check test doesn't actually have to be equal to the value from the original test. The residues only have to agree in the 64 least significant bits.

[Youjaes]

Originally Posted by Dr Sardonicus

It's not entirely clear to me how the double checking of an LL test using a left-shifted initial value is supposed to work. From what I have read,

1) The LL left-shifted double-check is only done when the initial LL test says the number is composite. (If the initial LL test says it's prime, the LL test is repeated by hordes of volunteers using different programs on different types of hardware.)

2) I read one place that the final "double check" residue is "adjusted" after the last iteration, to account for the original left shift of the starting value. Alas, there was no explanation of how this is done.

3) AFAICT the "adjusted" value from the double-check test doesn't actually have to be equal to the value from the original test. The residues only have to agree in the 64 least significant bits.

This what I know.

From https://en.wikipedia.org/wiki/Lucas%...primality_test
>>>>>

Alternate starting values[edit]
Starting values s0 other than 4 are possible, for instance 10, 52, and others (sequence A018844 in the OEIS). The Lucas-Lehmer residue calculated with these alternative starting values will still be zero if Mp is a Mersenne prime. However, the terms of the sequence will be different and a non-zero Lucas-Lehmer residue for non-prime Mp will have a different numerical value from the non-zero value calculated when s0 = 4.

[Viliam Furik]

Originally Posted by Youjaes

What you said doesn't match the facts. I posted the residuals for p = 29 and 31 and s0 equals 2^2 to 2^(p-1). The residuals don't match for shifted s0 except for s(p-2)=0 on some cases for Mp. Are you still not getting it?

I think George (Prime95 forum username) is most qualified to answer this, but I will try a bit.

Yes, they don't, but from what I've heard, there is a process done that somehow extracts the correct residue from the shifted one.

Well, that's actually all I can say about it, and I didn't find any more information so far.

[Youjaes]

Originally Posted by Viliam Furik

I think George (Prime95 forum username) is most qualified to answer this, but I will try a bit.

Yes, they don't, but from what I've heard, there is a process done that somehow extracts the correct residue from the shifted one.

Well, that's actually all I can say about it, and I didn't find any more information so far.

Okay, well, here is some sample data to work on. Reconcile the following:


For p = 29, the 64 bit LL residues (full value) for s0=4,8,16,32,64 are

s0 = 4, Residue = 458738443
s0 = 8, Residue = 399253392
s0 = 16, Residue = 173583544
s0 = 32, Residue = 356285411
s0 = 64, Residue = 454916308


For p = 31 = Mp, the 64 bit LL residues (full value) for s0=4,8,16,32,64 are

s0 = 4, Residue = 0
s0 = 8, Residue = 1395627816
s0 = 16, Residue = 2
s0 = 32, Residue = 475947287
s0 = 64, Residue = 2

James

[charybdis]

The 2 that's subtracted at each iteration needs to be bit-shifted too. This ensures that the residue at each iteration is just a shifted version of the "correct" residue, but the squarings that are carried out are different, so it's virtually impossible for two tests with different shifts to return the same incorrect result.

[kriesel]

Consider OP, that there may be unclarity or error in your thinking, programming, and communication. As there may be in mine, after having long ago written LL code (without floating point, without shifts) and having read these threads for years and followed prime95's development for decades.

Take it one iteration at a time.
See https://www.mersenneforum.org/showth...818#post572818
Those who've written the major GIMPS software are welcome to comment on that here.