|
Am I missing something
From an offsite conversation:
>>I think they catch potential errors with the double checking. [url]https://www.mersenne.org/various/math.php#double_checking[/url] ----- "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 [url]https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test[/url] >>>>> 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). [url]https://oeis.org/A018844[/url] 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 |
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. |
[QUOTE=Viliam Furik;572801]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.[/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 |
[QUOTE=Youjaes;572804]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[/CODE] James[/QUOTE] Again, I don't know what you are trying to say with these numbers. |
[QUOTE=Viliam Furik;572805]Again, I don't know what you are trying to say with these numbers.[/QUOTE]
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? |
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 [b][color=red]composite[/color][/b]. (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. |
[QUOTE=Dr Sardonicus;572809]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 [b][color=red]composite[/color][/b]. (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.[/QUOTE] This what I know. From [url]https://en.wikipedia.org/wiki/Lucas%...primality_test[/url] >>>>> 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. |
[QUOTE=Youjaes;572808]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?[/QUOTE]
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 [I]correct[/I] 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. |
[QUOTE=Viliam Furik;572812]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 [I]correct[/I] 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.[/QUOTE] 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 |
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.
|
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 [url]https://www.mersenneforum.org/showthread.php?p=572818#post572818[/url] Those who've written the major GIMPS software are welcome to comment on that here. |
@OP:
Yes. You are missing something. Those numbers are wrong. A multiplication with a power of 2 (random shift) will rotate all the operations by that amount, therefore when you square, you double the amount, and when you subtract 2 from the result, that 2 is rotated too, because the result is rotated. See posts #5, and the following discussion in posts #16, #17, #18, [URL="https://www.mersenneforum.org/showthread.php?p=280798"]in this thread[/URL]. OTOH, if you suggest that starting LL tests with different initial values, instead of the actual** random shift method, would be better (sorry, but as pointed by the former posters, I have no idea what do you want from us with those numbers, so I am trying to guess your mind), then it won't work, because, regardless of the value you start with, after a while the path converges (squaring numbers mod x is not a bijection, all negatives result in positives, so you only have half of the values in the co-domain), therefore FFT will work with the same numbers (or their negatives), which will defeat the goal: to make the FFT deal each time with different data, which would eliminate a bug in the code. Note that while other measures (GEC test, certification, etc) target hardware errors, cosmic rays, CPU going drunk, user's dishonesty (cheating for credits or whatever reasons), the random shift targets possible errors in software implementation of the FFT (software errors). If the FFT deals with completely different data each time and still produces the same result at the end (shifted or not) then we can be quite confident that the implementation is right. [CODE]Ex: 19: Starts with 10: 10, 98, 9602, 448177, 409322, 200240, 160699, 412414, 313150, 282018, 338709, 353913, 150119, 286038, 129657, 199279, 1024, 0 Starts with 52: 52, 2702, 485071, 160883, 339071, 343957, 7723, 400296, 100378, 519603, 444087, 87082, 511841, 238249, 129657, 199279, 1024, 0 [/CODE]You will note that the last iterations produce the same numbers. Other starting values could produce more or less common iteration (including all of them, for example, if you start with 4 or with -4 (mod Mp), they will coincide from the first). That's not the goal of the random shift. ---------- **former. Since PRP tricks invented by people here, LL is not anymore "actual" |
If you are genuinely interested in different starting values (and not just understanding the current implementation),
read Bas Jansen's PhD thesis, available here: [URL]https://scholarlypublications.universiteitleiden.nl/handle/1887/20310[/URL] |
[QUOTE=kriesel;572819]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 [url]https://www.mersenneforum.org/showthread.php?p=572818#post572818[/url] Those who've written the major GIMPS software are welcome to comment on that here.[/QUOTE] If you like, I can post all the intermediate s values for p=29 and 31 for s0 = 4, 8, and 16. It's not a problem since I'm already calculating the residuals for p<32 with s0 = 4 << (x-2) = 2^x for x = 2..100000. Here are the number of cases out of 99999 where the residual was zero for p<32. Cases for p where the count of zero residues was zero out 99999 were tested but omitted from the list, including p is not Mp and p is not prime. 3, 33333, 33% 5, 20000, 20% 7, 28571, 28% 13, 23077, 23% 17, 23530, 23% 19, 26316, 26% 31, 25806, 25% For the 99,999 simple cases of s0=x, x= 2.100000 the counts for residues = 0 for the 7 set of Mp's tested are 3, 28572, 28% 5, 25807, 25% 7, 25197, 25% 13, 25007, 25% 17, 24979, 24% 19, 24900, 24% 31, 25025, 25% My expectation is that for arbitrary starting values of s0, an Mp has a 1 in 4 chance of returning a zero residue and for not Mp, two different starting values have unrelated residues. Hopefully we'll hear from someone who can shed light on what's happening since frankly, using a start value other than s0=4 is a waste of time. If you can't calculate that residual accurately, the rest isn't worth much |
[QUOTE=LaurV;572825]@OP:
Yes. You are missing something. Those numbers are wrong. A multiplication with a power of 2 (random shift) will rotate all the operations by that amount, therefore when you square, you double the amount, and when you subtract 2 from the result, that 2 is rotated too, because the result is rotated. See posts #5, and the following discussion in posts #16, #17, #18, [URL="https://www.mersenneforum.org/showthread.php?p=280798"]in this thread[/URL].[/QUOTE]Ah, the examples tell the tale. When you shift the initial value k bits to the left, it is no longer the constant value 2 being subtracted after each squaring. (This is not mentioned in the given explanation, which only says the [i]initial value[/i] is shifted.) The subtrahend is being systematically shifted, with each iteration. Instead of subtracting the constant value 2 after each squaring starting with 4*2^k, you subtract 2*2^(2*k) after the first squaring, 2*2^(4*k) after the second, 2*2^(8*k) after the third, etc. This is what makes the new sequence of residues merely a shifted version of the original. |
[QUOTE=Youjaes;572843]
Hopefully we'll hear from someone who can shed light on what's happening since frankly, using a start value other than s0=4 is a waste of time. If you can't calculate that residual accurately, the rest isn't worth much[/QUOTE] Several people have already shed light on what's happening. When we run LL with a shift, we are not just starting with a different power of 2 and iterating x^2-2. We're also shifting the 2 that we subtract at each step. Since squaring doubles the number of bits we shift by, at each iteration we need to double the number of bits that the 2 is shifted by. Kriesel explained this in his post that he linked to. For example, let's say we shift left by 5 bits, so we start with 2^7 = 128 instead of 2^2 = 4. After the first squaring, the shift doubles to 10 bits, so we need to subtract a 2 shifted left by 10 bits, so 2^11. The unshifted LL gives 4^2-2 = 14, or 1110 in binary. The shifted LL gives 128^2-2^11 = 14336, or 11100000000000 in binary, and this is just 1110 shifted left by 10 bits. At the next iteration the squaring doubles the shift again to 20 bits, so we must subtract 2^21, and so on. Of course we reduce mod 2^p-1 at each step, so we do the same to the power of 2 that we subtract: if p=17, for example, then instead of subtracting 2^21 we subtract 2^4. Edit: beaten to it, but more examples can only help. |
[QUOTE=LaurV;572825]@OP:
Note that while other measures (GEC test, certification, etc) target hardware errors, cosmic rays, CPU going drunk, user's dishonesty (cheating for credits or whatever reasons), the random shift targets possible errors in software implementation of the FFT (software errors). If the FFT deals with completely different data each time and still produces the same result at the end (shifted or not) then we can be quite confident that the implementation is right. [CODE]Ex: 19: Starts with 10: 10, 98, 9602, 448177, 409322, 200240, 160699, 412414, 313150, 282018, 338709, 353913, 150119, 286038, 129657, 199279, 1024, 0 Starts with 52: 52, 2702, 485071, 160883, 339071, 343957, 7723, 400296, 100378, 519603, 444087, 87082, 511841, 238249, 129657, 199279, 1024, 0 [/CODE][/QUOTE] You chose special starting values known to produce zero residues for known Mp as of 2004. Only one in four arbitrary starting values do that for any particular Mp which I was easily able to calculate with 64-bit ints for p<32 is Mp. For example, starting values of 8,16,32,64, etc. have residues of zero ~25% of the time for the first 100,000 and the first 1,000,000 shifted single bits. Starting values of consecutive integers demonstrates the same pattern for the first 100,000 and 1,000,000 integers. If the intention is to test the hardware and FFT, wouldn't it be simpler and more efficient to generate p pseudorandom bits, X, and it's conjugate Y = ((2^p - 1) Xor X) = (2^p - 1) - X, i.e. X + Y = X Or Y = 2^p - 1, since (X*X - 2) mod (2^p - 1) = (Y*Y - 2) mod (2^p - 1) and compute a 128-bit Xor checksum on the two values (Xor 128 bit chunks of data at a time together) and if they don't match, do the two multiplications again so that if the error results are the same, then transmit the RNG seed and the two 128-bit checksums because you just found a confirmed error in the math so it's off to see the wizard. If this test were to be performed every 1,000 or 10,000 multiplications during the LL test, then the health of the computing device can be verified independent of the algorithm immediately and you don't have to wait till you are done and not know until someone runs a second LL to find out there is a problem. This way, you don't have to screw around with start values and can always use s0=4 with confidence. I good RNG can be found on the Wikipedia page for Xorshift. [url]https://en.wikipedia.org/wiki/Xorshift[/url] James |
[QUOTE=Youjaes;572961]
If the intention is to test the hardware and FFT, wouldn't it be simpler and more efficient to generate p pseudorandom bits, X, and it's conjugate Y = ((2^p - 1) Xor X) = (2^p - 1) - X, i.e. X + Y = X Or Y = 2^p - 1, since (X*X - 2) mod (2^p - 1) = (Y*Y - 2) mod (2^p - 1) and compute a 128-bit Xor checksum on the two values (Xor 128 bit chunks of data at a time together) and if they don't match, do the two multiplications again so that if the error results are the same, then transmit the RNG seed and the two 128-bit checksums because you just found a confirmed error in the math so it's off to see the wizard. If this test were to be performed every 1,000 or 10,000 multiplications during the LL test, then the health of the computing device can be verified independent of the algorithm immediately and you don't have to wait till you are done and not know until someone runs a second LL to find out there is a problem. This way, you don't have to screw around with start values and can always use s0=4 with confidence. [/QUOTE] 1. If I'm understanding you correctly, your idea is to periodically compute X^2 and (N-X)^2 mod N for a random X as a simple hardware check. There are at least two major problems with this. Firstly, your hardware could make errors too rarely to be picked up by your check, but frequently enough to regularly produce incorrect LL residues - say, if it makes an error once in every 100M squarings. Secondly, your check doesn't use any of the actual intermediate values from the LL test, so you could never be totally sure that the test itself contained no errors, even if you ran hundreds of checks for every LL iteration. 2. Using a shift is [B]not[/B] "screwing around with start values". It's [B]still using s0=4[/B], but everything is shifted, including the -2. The shift is a separate concept from using an alternative starting value such as 10, which would give a completely different sequence of residues. If we run one test on a composite Mersenne with s0=4 and another with s0=10, we won't get matching residues, so this would not be a suitable method for double-checking (except for primes). 3. As LaurV says, the main intention of the shift is that it will pick up bugs in the FFT implementation: while morally we're performing the same calculations, the numbers that we need to square are bit-shifted, so the FFT computations are different. An FFT bug would therefore produce different incorrect residues with different shifts. Hardware errors are much easier to pick up: even without a shift, they would lead to residues that don't match, if they don't get caught by other means first. 4. GIMPS now prefers to use PRP rather than LL for primality tests, apart from double-checks of LL results. This is because there is a robust error-checking procedure called the [URL="https://www.mersenneforum.org/showthread.php?t=22510"]Gerbicz error-check[/URL] which is almost certain to catch any errors during the test. PRP tests can also be [URL="https://www.mersenneforum.org/showthread.php?t=25638"]certified[/URL], allowing a quick verification that the work was done correctly; this means that a double-check is not needed. |
[QUOTE=charybdis;572966]<snip>
4. GIMPS now prefers to use PRP rather than LL for primality tests, apart from double-checks of LL results. This is because there is a robust error-checking procedure called the [URL="https://www.mersenneforum.org/showthread.php?t=22510"]Gerbicz error-check[/URL] which is almost certain to catch any errors during the test. PRP tests can also be [URL="https://www.mersenneforum.org/showthread.php?t=25638"]certified[/URL], allowing a quick verification that the work was done correctly; this means that a double-check is not needed.[/QUOTE]Because of this, apart from double checks on previously LL tested M[sub]p[/sub], very few LL tests will be run in future on any M[sub]p[/sub], unless it has first tested as a probable prime (i.e. the PRP test fails to prove it composite). If it PRP tests as a probable prime, the result of the LL test will be conclusive. If M[sub]p[/sub] LL tests as prime, that would be news, because another Mersenne prime would have been found. If an M[sub]p[/sub] that PRP tests as probable prime then LL tests as composite, that would also be news, because it would be a composite that "fooled" the PRP test. |
| All times are UTC. The time now is 13:10. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.