mersenneforum.org Am I missing something
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2021-03-01, 18:28 #1 Youjaes   Mar 2021 7 Posts Am I missing something 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 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
 2021-03-01, 23:45 #2 Viliam Furik   "Viliam Furík" Jul 2018 Martin, Slovakia 44610 Posts 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.
2021-03-02, 00:29   #3
Youjaes

Mar 2021

7 Posts

Quote:
 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

2021-03-02, 00:31   #4
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

6768 Posts

Quote:
 Originally Posted by Youjaes If you say so. Code: ----- 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.

2021-03-02, 00:49   #5
Youjaes

Mar 2021

7 Posts

Quote:
 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?

 2021-03-02, 00:53 #6 Dr Sardonicus     Feb 2017 Nowhere 17×263 Posts 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.
2021-03-02, 01:08   #7
Youjaes

Mar 2021

7 Posts

Quote:
 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
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.

2021-03-02, 01:32   #8
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

2·223 Posts

Quote:
 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.

2021-03-02, 01:45   #9
Youjaes

Mar 2021

78 Posts

Quote:
 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

 2021-03-02, 01:48 #10 charybdis   Apr 2020 23310 Posts 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.
 2021-03-02, 03:36 #11 kriesel     "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 503110 Posts LL with shift 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post tomtuba Software 3 2019-04-16 10:02 R.D. Silverman GMP-ECM 3 2011-03-18 21:35 ixfd64 PrimeNet 1 2008-08-28 05:15 fivemack Factoring 4 2008-03-04 05:04 tha Data 6 2003-09-14 21:36

All times are UTC. The time now is 07:25.

Tue Apr 20 07:25:23 UTC 2021 up 12 days, 2:06, 0 users, load averages: 2.52, 2.45, 2.59