PRPNet 3.0.0 Released - Page 20

rogue · 2010-08-02, 19:59

Quote:

Originally Posted by mdettweiler

I'm assuming that "is 3-PRP!" means that it definitely was done with a 3-PRP test, right?

Yes. So if base 5 were used, then you would see "is 5-PRP". For example

Code:

pfgw -b5 -q50633872*3^^25032-1
PFGW Version 3.3.4.20100405.Win_Stable [GWNUM 25.14]

50633872*3^25032-1 is 5-PRP! (5.4775s+0.0007s)

For N-1, the primality test is similar to a PRP test with one main exception, the base is chosen with care so that the conditions of the test can be used to prove primality. If you choose the wrong base, then all you get is a PRP test. I expect that if you run LLR with base 3 numbers with c=1 that you will see LLR choosing bases other than 3.

For N+1, a Lucas sequence is used (similar to what Prime95 does for Mersenne testing). The base is important, but not in the same way.

mdettweiler · 2010-08-02, 22:37

Quote:

Originally Posted by rogue

Yes. So if base 5 were used, then you would see "is 5-PRP". For example

Code:

pfgw -b5 -q50633872*3^^25032-1
PFGW Version 3.3.4.20100405.Win_Stable [GWNUM 25.14]
 
50633872*3^25032-1 is 5-PRP! (5.4775s+0.0007s)

For N-1, the primality test is similar to a PRP test with one main exception, the base is chosen with care so that the conditions of the test can be used to prove primality. If you choose the wrong base, then all you get is a PRP test. I expect that if you run LLR with base 3 numbers with c=1 that you will see LLR choosing bases other than 3.

For N+1, a Lucas sequence is used (similar to what Prime95 does for Mersenne testing). The base is important, but not in the same way.

Ah, I see. Okay, I've done another test similar to the last (20 composites, 1 known prime), this time on 2*3^n+1 so that LLR will do an N-1. Here goes:

Code:

2*3^25005+1 is composite: RES64: [138E120DC6867BA4] (1.8038s+0.0007s)
2*3^25012+1 is composite: RES64: [4644F83087C00C84] (1.7564s+0.0015s)
2*3^25024+1 is composite: RES64: [9FFB2BCD7F90E064] (1.7818s+0.0038s)
2*3^25025+1 is composite: RES64: [4330842A84D85E90] (1.7347s+0.0012s)
2*3^25049+1 is composite: RES64: [794BE89B47AC55FA] (1.7315s+0.0049s)
2*3^25052+1 is composite: RES64: [941ABEFB40C05B99] (1.7823s+0.0039s)
2*3^25056+1 is composite: RES64: [6A0B0EBBEEA2F1C8] (1.7373s+0.0059s)
2*3^25074+1 is composite: RES64: [236729660C6BB8F0] (1.7582s+0.0105s)
2*3^25086+1 is composite: RES64: [586B570BCD44C707] (1.7570s+0.0029s)
2*3^25109+1 is composite: RES64: [6DAA4AA28E9222AE] (1.6774s+0.0019s)
2*3^25116+1 is composite: RES64: [411E046C5F6E9A6C] (1.7494s+0.0021s)
2*3^25120+1 is composite: RES64: [C707DB3927ABA184] (1.7846s+0.0019s)
2*3^25134+1 is composite: RES64: [7782FDD7A6EDD431] (1.6955s+0.0075s)
2*3^25137+1 is composite: RES64: [108E2724D21E2CA0] (1.7081s+0.0019s)
2*3^25142+1 is composite: RES64: [CAE8B247C88C6194] (1.6980s+0.0019s)
2*3^25149+1 is composite: RES64: [FB5F02680A303FB6] (1.8011s+0.0059s)
2*3^25157+1 is composite: RES64: [7CE7A675C184E565] (1.8578s+0.0086s)
2*3^25160+1 is composite: RES64: [9E4A959BAF8EB314] (1.8513s+0.0030s)
2*3^25164+1 is composite: RES64: [04BAB61743130F6E] (1.8077s+0.0023s)
2*3^25172+1 is composite: RES64: [DF5A91DAB7BC3CD3] (1.7832s+0.0025s)
173369962*3^25030+1 is 3-PRP! (3.8557s+0.0083s)

Code:

2*3^25005+1 is not prime.  RES64: 138E120DC6867BA4.  OLD64: C5413481D8467042  Time : 3.390 sec.
2*3^25012+1 is not prime.  RES64: 4644F83087C00C84.  OLD64: C2ACA4FCE174E543  Time : 3.367 sec.
2*3^25024+1 is not prime.  RES64: 9FFB2BCD7F90E064.  OLD64: DFF183687EB2A129  Time : 4.304 sec.
2*3^25025+1 is not prime.  RES64: 4330842A84D85E90.  OLD64: 6A8591B72D2B19A6  Time : 4.409 sec.
2*3^25049+1 is not prime.  RES64: 794BE89B47AC55FA.  OLD64: 1F300AF2038CD35D  Time : 3.095 sec.
2*3^25052+1 is not prime.  RES64: 941ABEFB40C05B99.  OLD64: A55CCB5674942A02  Time : 3.957 sec.
2*3^25056+1 is not prime.  RES64: 6A0B0EBBEEA2F1C8.  OLD64: FB1A3A1038332F4F  Time : 3.421 sec.
2*3^25074+1 is not prime.  RES64: 236729660C6BB8F0.  OLD64: 6A9CB226DD128FA7  Time : 3.731 sec.
2*3^25086+1 is not prime.  RES64: 586B570BCD44C707.  OLD64: 830231C2F02EE89F  Time : 3.543 sec.
2*3^25109+1 is not prime.  RES64: 6DAA4AA28E9222AE.  OLD64: 216D5BCBADDE52A0  Time : 4.028 sec.
2*3^25116+1 is not prime.  RES64: 411E046C5F6E9A6C.  OLD64: B312D701F44E327B  Time : 3.673 sec.
2*3^25120+1 is not prime.  RES64: C707DB3927ABA184.  OLD64: 551791AB7702E489  Time : 4.692 sec.
2*3^25134+1 is not prime.  RES64: 7782FDD7A6EDD431.  OLD64: F51C701FCC6D209D  Time : 3.649 sec.
2*3^25137+1 is not prime.  RES64: 108E2724D21E2CA0.  OLD64: 44C579ABF2DF20CF  Time : 3.123 sec.
2*3^25142+1 is not prime.  RES64: CAE8B247C88C6194.  OLD64: 835F1D348B843A53  Time : 3.701 sec.
2*3^25149+1 is not prime.  RES64: FB5F02680A303FB6.  OLD64: E9EA65612B5E5AD1  Time : 3.350 sec.
2*3^25157+1 is not prime.  RES64: 7CE7A675C184E565.  OLD64: 76B6F361448EB02C  Time : 3.389 sec.
2*3^25160+1 is not prime.  RES64: 9E4A959BAF8EB314.  OLD64: 80A1D0BA531B5BF6  Time : 3.297 sec.
2*3^25164+1 is not prime.  RES64: 04BAB61743130F6E.  OLD64: 0E302245C9392E47  Time : 3.685 sec.
2*3^25172+1 is not prime.  RES64: DF5A91DAB7BC3CD3.  OLD64: A0A835F965EC9553  Time : 2.921 sec.
173369962*3^25030+1 is prime!  Time : 6.479 sec.

All the residues match. Interestingly enough, LLR actually chose base 3 every time for the test; one such example follows:

Code:

Base prime factor(s) taken : 3
Starting N-1 prime test of 2*3^25172+1
Using all-complex FFT length 2048, a = 3

2*3^25172+1 is not prime.  RES64: DF5A91DAB7BC3CD3.  OLD64: A0A835F965EC9553  Time : 2.921 sec.

(Again, I'm assuming that "a = 3" means that it used base 3. Please feel free to correct me if I'm wrong here.)

And also quite interestingly, LLR was able to prove the prime on the very first try(!):

Code:

Base prime factor(s) taken : 3
Starting N-1 prime test of 173369962*3^25030+1
Using zero-padded FFT length 4K, a = 3
173369962*3^25030+1 may be prime, trying to compute gcd's
3^((N-1)/3)-1 is coprime to N!
173369962*3^25030+1 is prime!  Time : 6.479 sec.

Any idea what's going on here?

rogue · 2010-08-03, 13:05

You can read this to understand the N-1 primality test that LLR is using:

If, for some integer b, the quantity b^(N-1) is congruent to 1
modulo N, and if b^((N-1)/q) is NOT congruent to 1 modulo N for
ANY prime divisor q of N-1, then N is a prime.

In your test case b = 3 and q = 3. Here is a number that can't be proven with b=3:

Code:

cllr -d -q"27*496^551+1"
Base prime factor(s) taken : 31
Starting N-1 prime test of 27*496^551+1
Using all-complex FFT length 512, a = 3
27*496^551+1 may be prime, trying to compute gcd's
27*496^551+1 may be prime, but N divides 3^((N-1)/31))-1, restarting with a=5  Time : 71.032 ms.
Restarting N-1 prime test of 27*496^551+1
Using all-complex FFT length 512, a = 5
27*496^551+1 may be prime, trying to compute gcd's
5^((N-1)/31)-1 is coprime to N!
27*496^551+1 is prime!  Time : 69.811 ms.

It does a PRP test with b=3, but since N because 3^((N-1)/31) is congruent to 1 module N, then it is just a PRP test. LLR then tries b=5. Since 5^((N-1)/31)-1 is coprime (congruent) to N, the number is prime.

I believe that LLR works in the following fashion:

1) Set b=3.
2) Do a PRP test (Fermat's Little Theorem).
3) If composite, print the residue and exit.
4) If PRP, determine if b^((N-1)/q)-1 is coprime to N.
5) If coprime, then N is prime and exit.
6) If not coprime, then set b to the next prime.
7) Go back to step 2.

Eventually I will add step 4 to phrot, but it isn't a trivial step as I know that there is more going on under the covers than what I am showing here. There are cases (one I have buried in an e-mail somewhere) that requires two values of q for the given base, so step 4 is really:

4a) If PRP, determine if b^((N-1)/q1)-1 is coprime to N.
4b) If coprime, determine if b^((N-1)/q2)-1 is coprime to N.
...

All of the q values must be used to determine coprimeness to N before primality can be established. If there is only one q, then step 4 is easy, but if there are multiple, that's where things become much more complex.

Presuming that I am correct with the steps listed above, then LLR will always have a base 3 residue if the number is composite, bit it also implies that sometimes (albeit rarely) LLR will need more time for a primality test than PFGW. PFGW is able to establish primality with b=3:

Code:

pfgw -V -tm -q"16*406^420+1"
PFGW Version 3.3.4.20100405.Win_Stable [GWNUM 25.14]

Primality testing 16*406^420+1 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 3
Special modular reduction using all-complex FFT length 512 on 16*406^420+1
Calling Brillhart-Lehmer-Selfridge with factored part 56.00%
16*406^420+1 is prime! (0.0313s+0.0054s)

mdettweiler · 2010-08-03, 16:31

That makes sense--it would seem to jive well with what I'd observed of LLR's behavior. I've actually noticed that it needs to try multiple bases a LOT more than PFGW when proving a possible prime--to the point where numbers that can be proven by LLR on the first try (like the base 3 one in my example) are a tad on the rare side.

In that case, it would seem we don't have to worry about incompatible residues, since the only time it runs another base is if it's PRP (which for any somewhat large number, means it's almost definitely prime), hence the residue is 0 regardless of base. The only situation in which an incompatible residue would arise is if a 3-PRP is found that later turns out to be composite in another base, but again, for non-trivially-sized numbers that's nearly impossible anyway.

Nonetheless, I can still see some other situations in which the usellroverpfgw= option would be useful, such as with S208, which as I mentioned earlier is a wacky case that can actually be algebraically converted to base 2, which LLR 3.8 does, but PRPnet only recognizes the more basic power-of-2 conversions, so it just passes it to either PFGW or LLR verbatim. PFGW does a standard 3-PRP test, but LLR converts it to base 2 and does a Proth test--leading to incompatible residues. Running with usellroverpfgw=1 for such bases would solve that problem. So, if the coding's already done, I'd go ahead and include the feature in PRPnet 3.4.0 as planned.

Mini-Geek · 2010-08-10, 14:37

I've got a minor bug to report. I'm using 3.3.6. The "Max N" field on server_stats.html (also appears at / and all.html) is in a <td> instead of a <th> field like the rest of the headers. This means it's not bold and centered.

rogue · 2010-08-10, 17:33

Quote:

Originally Posted by Mini-Geek

I've got a minor bug to report. I'm using 3.3.6. The "Max N" field on server_stats.html (also appears at / and all.html) is in a <td> instead of a <th> field like the rest of the headers. This means it's not bold and centered.

Thanks. It will be fixed in the next release.

Xentar · 2010-09-16, 19:02

After the last problems with pfgw:
Maybe you should add a column "PRPingProgramVersion" or something, so that all tests can be done again with a newer version (if a specific option is set)?

Edit: Yes, I know I could just enable double checking - but at the moment, I don't like to double-check tests, that have been done with the newest pfgw version. Just these one, that have been done with the older version.

Edit2: Full stop ;) I now understand, that a double check of all tests is not neccessary. So you can delete this post, sorry.

mdettweiler · 2010-10-11, 19:12

FYI: PRPnet 4.0.0 has now been released as an Alpha over in the Software forum. See here:
http://www.mersenneforum.org/showthread.php?t=14046

MyDogBuster · 2010-10-12, 18:04

Curiosity. PRPNET used to have memory problems when loading to many candidates into the database. I'm assuming that since MYSQL was implemented, that memory restriction is now resolved. I should be able to load 2.5M candidates into a database and let her rip. CORRECT????

Using 3.3.6 currently

rogue · 2010-10-12, 18:40

Quote:

Originally Posted by MyDogBuster

Curiosity. PRPNET used to have memory problems when loading to many candidates into the database. I'm assuming that since MYSQL was implemented, that memory restriction is now resolved. I should be able to load 2.5M candidates into a database and let her rip. CORRECT????

Using 3.3.6 currently

Yes, but I haven't tried that many. I have loaded more than 700,000 into a single database without problems. I'd like to know how well that works for you.

MyDogBuster · 2010-10-12, 19:03

Quote:

I'd like to know how well that works for you.

It will be awhile before I try it. Just planning ahead looking for biggest bang for the buck. It it works, it would make working on the bases with loads of k's left easier, rather than having to split up k's.

2010-08-03, 13:05	#212
rogue "Mark" Apr 2003 Between here and the 2⁴·397 Posts	You can read this to understand the N-1 primality test that LLR is using: If, for some integer b, the quantity b^(N-1) is congruent to 1 modulo N, and if b^((N-1)/q) is NOT congruent to 1 modulo N for ANY prime divisor q of N-1, then N is a prime. In your test case b = 3 and q = 3. Here is a number that can't be proven with b=3: Code: cllr -d -q"27496^551+1" Base prime factor(s) taken : 31 Starting N-1 prime test of 27496^551+1 Using all-complex FFT length 512, a = 3 27496^551+1 may be prime, trying to compute gcd's 27496^551+1 may be prime, but N divides 3^((N-1)/31))-1, restarting with a=5 Time : 71.032 ms. Restarting N-1 prime test of 27496^551+1 Using all-complex FFT length 512, a = 5 27496^551+1 may be prime, trying to compute gcd's 5^((N-1)/31)-1 is coprime to N! 27496^551+1 is prime! Time : 69.811 ms. It does a PRP test with b=3, but since N because 3^((N-1)/31) is congruent to 1 module N, then it is just a PRP test. LLR then tries b=5. Since 5^((N-1)/31)-1 is coprime (congruent) to N, the number is prime. I believe that LLR works in the following fashion: 1) Set b=3. 2) Do a PRP test (Fermat's Little Theorem). 3) If composite, print the residue and exit. 4) If PRP, determine if b^((N-1)/q)-1 is coprime to N. 5) If coprime, then N is prime and exit. 6) If not coprime, then set b to the next prime. 7) Go back to step 2. Eventually I will add step 4 to phrot, but it isn't a trivial step as I know that there is more going on under the covers than what I am showing here. There are cases (one I have buried in an e-mail somewhere) that requires two values of q for the given base, so step 4 is really: 4a) If PRP, determine if b^((N-1)/q1)-1 is coprime to N. 4b) If coprime, determine if b^((N-1)/q2)-1 is coprime to N. ... All of the q values must be used to determine coprimeness to N before primality can be established. If there is only one q, then step 4 is easy, but if there are multiple, that's where things become much more complex. Presuming that I am correct with the steps listed above, then LLR will always have a base 3 residue if the number is composite, bit it also implies that sometimes (albeit rarely) LLR will need more time for a primality test than PFGW. PFGW is able to establish primality with b=3: Code: pfgw -V -tm -q"16406^420+1" PFGW Version 3.3.4.20100405.Win_Stable [GWNUM 25.14] Primality testing 16406^420+1 [N-1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 3 Special modular reduction using all-complex FFT length 512 on 16406^420+1 Calling Brillhart-Lehmer-Selfridge with factored part 56.00% 16*406^420+1 is prime! (0.0313s+0.0054s)

2010-08-03, 16:31	#213
mdettweiler A Sunny Moo Aug 2007 USA (GMT-5) 3×2,083 Posts	That makes sense--it would seem to jive well with what I'd observed of LLR's behavior. I've actually noticed that it needs to try multiple bases a LOT more than PFGW when proving a possible prime--to the point where numbers that can be proven by LLR on the first try (like the base 3 one in my example) are a tad on the rare side. In that case, it would seem we don't have to worry about incompatible residues, since the only time it runs another base is if it's PRP (which for any somewhat large number, means it's almost definitely prime), hence the residue is 0 regardless of base. The only situation in which an incompatible residue would arise is if a 3-PRP is found that later turns out to be composite in another base, but again, for non-trivially-sized numbers that's nearly impossible anyway. Nonetheless, I can still see some other situations in which the usellroverpfgw= option would be useful, such as with S208, which as I mentioned earlier is a wacky case that can actually be algebraically converted to base 2, which LLR 3.8 does, but PRPnet only recognizes the more basic power-of-2 conversions, so it just passes it to either PFGW or LLR verbatim. PFGW does a standard 3-PRP test, but LLR converts it to base 2 and does a Proth test--leading to incompatible residues. Running with usellroverpfgw=1 for such bases would solve that problem. So, if the coding's already done, I'd go ahead and include the feature in PRPnet 3.4.0 as planned. Last fiddled with by mdettweiler on 2010-08-03 at 16:31

2010-09-16, 19:02	#216
Xentar Sep 2006 11·17 Posts	After the last problems with pfgw: Maybe you should add a column "PRPingProgramVersion" or something, so that all tests can be done again with a newer version (if a specific option is set)? Edit: Yes, I know I could just enable double checking - but at the moment, I don't like to double-check tests, that have been done with the newest pfgw version. Just these one, that have been done with the older version. Edit2: Full stop ;) I now understand, that a double check of all tests is not neccessary. So you can delete this post, sorry. Last fiddled with by Xentar on 2010-09-16 at 19:12

2010-10-12, 18:04	#218
MyDogBuster May 2008 Wilmington, DE 101100100100₂ Posts	Curiosity. PRPNET used to have memory problems when loading to many candidates into the database. I'm assuming that since MYSQL was implemented, that memory restriction is now resolved. I should be able to load 2.5M candidates into a database and let her rip. CORRECT???? Using 3.3.6 currently Last fiddled with by MyDogBuster on 2010-10-12 at 18:05

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
PRPNet 5.4.3 Released	rogue	Software	178	2021-06-24 11:56
PSP goes prpnet	ltd	Prime Sierpinski Project	86	2012-06-06 02:30
PRPNet 4.0.0 Released	rogue	Software	84	2011-11-16 21:20
PRPNet 4.0.1 Released	Joe O	Sierpinski/Riesel Base 5	1	2010-10-22 20:11
PRPNet released!	rogue	Conjectures 'R Us	250	2009-12-27 21:29

2010-08-10, 14:37	#214
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 17×251 Posts	I've got a minor bug to report. I'm using 3.3.6. The "Max N" field on server_stats.html (also appears at / and all.html) is in a <td> instead of a <th> field like the rest of the headers. This means it's not bold and centered.

2010-10-11, 19:12	#217
mdettweiler A Sunny Moo Aug 2007 USA (GMT-5) 3×2,083 Posts	FYI: PRPnet 4.0.0 has now been released as an Alpha over in the Software forum. See here: http://www.mersenneforum.org/showthread.php?t=14046