mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Forum Feedback

Reply
 
Thread Tools
Old 2021-03-01, 18:28   #1
Youjaes
 
Mar 2021

716 Posts
Default 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[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
Youjaes is offline   Reply With Quote
Old 2021-03-01, 23:45   #2
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

3×149 Posts
Default

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.
Viliam Furik is online now   Reply With Quote
Old 2021-03-02, 00:29   #3
Youjaes
 
Mar 2021

78 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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
Youjaes is offline   Reply With Quote
Old 2021-03-02, 00:31   #4
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

1101111112 Posts
Default

Quote:
Originally Posted by Youjaes View Post
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.
Viliam Furik is online now   Reply With Quote
Old 2021-03-02, 00:49   #5
Youjaes
 
Mar 2021

7 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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?
Youjaes is offline   Reply With Quote
Old 2021-03-02, 00:53   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×5×449 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-03-02, 01:08   #7
Youjaes
 
Mar 2021

7 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
Youjaes is offline   Reply With Quote
Old 2021-03-02, 01:32   #8
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

3×149 Posts
Default

Quote:
Originally Posted by Youjaes View Post
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.
Viliam Furik is online now   Reply With Quote
Old 2021-03-02, 01:45   #9
Youjaes
 
Mar 2021

7 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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
Youjaes is offline   Reply With Quote
Old 2021-03-02, 01:48   #10
charybdis
 
charybdis's Avatar
 
Apr 2020

2×112 Posts
Default

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.
charybdis is offline   Reply With Quote
Old 2021-03-02, 03:36   #11
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

10011101100012 Posts
Default 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.
kriesel is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 14:12.

Fri Apr 23 14:12:04 UTC 2021 up 15 days, 8:52, 0 users, load averages: 1.61, 1.74, 1.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.