20210301, 18:28  #1 
Mar 2021
7_{16} 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 doublechecking goes a bit further to guard against programming errors. Prior to starting the LucasLehmer test, the S0 value is leftshifted by a random amount. Each squaring just doubles how much we have shifted the S value. Note that the mod 2P1 step merely rotates the pth 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 LucasLehmer 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 nonzero LucasLehmer residue for nonprime Mp will have a different numerical value from the nonzero 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 LucasLehmer 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 LucasLehmer test that result in a zero term (mod Mersenne prime Mp) after P1 steps.  Jason Follas (jfollas_mersenne(AT)hotmail.com), Aug 01 2004 >>>>>>> A quick verification using "gradeschool" math The following Vb.Net program produced this output.. >>>>>>> s[p2] = 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[p2] = 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[p2] = 0 residual counts for s[0] = 2^x where x <=" & Str(MAXSEARCH) & " and p <= 31" & vbCrLf & vbCrLf Else TB2.Text &= "s[p2] = 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 
20210301, 23:45  #2 
"Viliam Furík"
Jul 2018
Martin, Slovakia
3×149 Posts 
I am not sure, what you think you are missing or not, but if you are talking about the doublechecking 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. 
20210302, 00:29  #3  
Mar 2021
7_{8} Posts 
Quote:
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 

20210302, 00:31  #4  
"Viliam Furík"
Jul 2018
Martin, Slovakia
110111111_{2} Posts 
Quote:


20210302, 00:49  #5 
Mar 2021
7 Posts 
What you said doesn't match the facts. I posted the residuals for p = 29 and 31 and s0 equals 2^2 to 2^(p1). The residuals don't match for shifted s0 except for s(p2)=0 on some cases for Mp. Are you still not getting it?

20210302, 00:53  #6 
Feb 2017
Nowhere
2×5×449 Posts 
It's not entirely clear to me how the double checking of an LL test using a leftshifted initial value is supposed to work. From what I have read,
1) The LL leftshifted doublecheck 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 doublecheck 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. 
20210302, 01:08  #7  
Mar 2021
7 Posts 
Quote:
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 LucasLehmer 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 nonzero LucasLehmer residue for nonprime Mp will have a different numerical value from the nonzero value calculated when s0 = 4. 

20210302, 01:32  #8  
"Viliam Furík"
Jul 2018
Martin, Slovakia
3×149 Posts 
Quote:
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. 

20210302, 01:45  #9  
Mar 2021
7 Posts 
Quote:
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 

20210302, 01:48  #10 
Apr 2020
2×11^{2} Posts 
The 2 that's subtracted at each iteration needs to be bitshifted 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.

20210302, 03:36  #11 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
1001110110001_{2} 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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Missing Work  tomtuba  Software  3  20190416 10:02 
Missing top 10?  R.D. Silverman  GMPECM  3  20110318 21:35 
what causes missing results?  ixfd64  PrimeNet  1  20080828 05:15 
A missing identity  fivemack  Factoring  4  20080304 05:04 
missing?  tha  Data  6  20030914 21:36 