GQ(1127239) is PRP!

Cruelty · 2006-11-16, 21:57

(2^1127239+2^563620+1)/5 is 3-PRP!, which AFAIK is the largest GQ so far

The question I have now is, how to prove it is, or it is not a prime

BTW: I don't consider using PRIMO or other ECPP based software for this purpose as it would take more than my life to complete

Kosmaj · 2006-11-16, 22:59

There is no way to prove it prime, AFAIK. Primo distributed version (not publicly available) takes months on 20k digit numbers, and yours has more than 300k digits!

What you can do is the following, all using pfgw: test that it's PRP in another 2-3 bases, for example in base 7 run:
pfgw -b7 -q(2^1127239+2^563620+1)/5

as other two bases select a prime between 10 and 30 and one larger than 100.

And finally run the "-tc" test
pfgw -tc -q...
it will do some extra tests to show that it is "Fermat and Lucas PRP".

You can submit it to the list of largest PRPs maintained by Henri Lifchitz

currently, it will be the largest one.
Congratulations!

Kosmaj · 2006-11-17, 01:19

I see that you sent it to Top-5000. I'm afraid it will be deleted, but at least the tc test will be done on their machine

It's going to take a while though (24 hrs?).

paulunderwood · 2006-11-17, 20:56

Cruelty -- and this goes for all who submit to the top5000 primes list -- please check before your submissions to the top5000 primes that your numbers are indeed proven prime. Why did you submit it? Did you think some magic would happen?

However, congrats for finding, by far, the world's largest known "probable prime"

paulunderwood · 2006-11-18, 01:11

the number is composite: http://primes.utm.edu/primes/page.php?id=78860

Congrats for largest PRP is retracted by me

Command: /home/caldwell/client/pfgw -tc -q"(2^1127239+2^563620+1)/5" 2>&1
PFGW Version 20031027.x86_Dev (Beta 'caveat utilitor') [FFT v22.13 w/P4]
Primality testing (2^1127239+2^563620+1)/5 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Using SSE2 FFT
Adjusting authentication level by 1 for PRIMALITY PROOF
Reduced from FFT(131072,20) to FFT(131072,19)
Reduced from FFT(131072,19) to FFT(131072,18)
2254482 bit request FFT size=(131072,18)
Running N-1 test using base 3
Using SSE2 FFT
Adjusting authentication level by 1 for PRIMALITY PROOF
Reduced from FFT(131072,20) to FFT(131072,19)
Reduced from FFT(131072,19) to FFT(131072,18)
2254482 bit request FFT size=(131072,18)
Running N+1 test using discriminant 11, base 3+sqrt(11)
Using SSE2 FFT
Adjusting authentication level by 1 for PRIMALITY PROOF
Reduced from FFT(131072,20) to FFT(131072,19)
Reduced from FFT(131072,19) to FFT(131072,18)
2254490 bit request FFT size=(131072,18)
(2^1127239+2^563620+1)/5 is composite (-1716.3205s+0.0000s)
[Ellapsed time: 94132 seconds]

Kosmaj · 2006-11-18, 02:58

Sorry to hear that

There are several possibilities:
1) It's really 3-PRP but composite. That's entirely possible and that's the reason to try several more bases, and show that it's 7-PRP, 13-PRP etc. Check some entries on the largest PRP list, for example Jean-Louis Charton [Congrats Jean!] who holds the record tested as many as 7 bases on 4^341233-3^341233 (205443 digits).

2) There is a bug in LLR. That's also possible because GQ feature is a new one, much less tested than the mean-stream k*2^n-1 one.

3) Your hardware problem.

Therefore, please run "pfgw -q(2^1127239+2^563620+1)/5", base=3 implied, on a stable hardware, if it's PRP mistery solved, if not than more tests will be required to find out what really happened. BTW, the PRP test will take much less time than the tc test which took 26 hrs on a Top-5000 machine, not more than 3 hrs on a 3GHz P-4 I think.

paulunderwood · 2006-11-18, 05:47

I confirmed Cruelty's 3-PRP with llr (for linux) and am now running PFGW PRP test with base 137, and then I will check with base-3 and maybe too I will test with PFGW -tc. But I am only using 3.4Ghz Pentium 4

Cruelty · 2006-11-18, 06:00

Strange, I have tested it with PFGW to find that:
(2^1127239+2^563620+1)/5 is 3-PRP! (6992.4544s+0.0010s)
(2^1127239+2^563620+1)/5 is 7-PRP! (22176.6766s+0.0022s)
(2^1127239+2^563620+1)/5 is 13-PRP! (22235.2301s+0.0018s)

I will run "-tc" command over weekend.

paulunderwood · 2006-11-18, 06:14

Cruelty, what version of PFGW did you uses? 1.2.0?

axn · 2006-11-18, 07:27

Quote:

Originally Posted by Kosmaj

There are several possibilities:
1) It's really 3-PRP but composite. That's entirely possible and that's the reason to try several more bases, and show that it's 7-PRP, 13-PRP etc. Check some entries on the largest PRP list, for example Jean-Louis Charton [Congrats Jean!] who holds the record tested as many as 7 bases on 4^341233-3^341233 (205443 digits).

2) There is a bug in LLR. That's also possible because GQ feature is a new one, much less tested than the mean-stream k*2^n-1 one.

3) Your hardware problem.

How about a bug in PFGW?

paulunderwood · 2006-11-18, 09:54

Quote:

How about a bug in PFGW?

Indeed! It seems PFGW's combined N+1/N-1 test can be flaky at such dizzy heights, according to David Broadhurst. It is looking good with two "LLR" tests and PRP bases 3,7,13 and 137 test with PFGW all passed (by Cruelty and me). Cruelty is doing PFGW -tc again but presumable not with the beta version that Chris Caldwell (UTM) uses for "top5000" work. Ken is doing an 11-PRP with PFGW and I am doing an N+1 test and an N-1 test.

I reinstate my congratulations for Cruelty for the ~50% improvement of the PRP record (even though it was naughty of him to submit it to UTM without first verifying it as a prime.)

Lastly, great work Jean and Citrix (and Jim and George!)

2006-11-17, 20:56	#4
paulunderwood Sep 2002 Database er0rr 2²×19×43 Posts	Cruelty -- and this goes for all who submit to the top5000 primes list -- please check before your submissions to the top5000 primes that your numbers are indeed proven prime. Why did you submit it? Did you think some magic would happen? However, congrats for finding, by far, the world's largest known "probable prime" Last fiddled with by paulunderwood on 2006-11-17 at 20:59

2006-11-16, 21:57	#1
Cruelty May 2005 3122₈ Posts	(2^1127239+2^563620+1)/5 is 3-PRP!, which AFAIK is the largest GQ so far The question I have now is, how to prove it is, or it is not a prime BTW: I don't consider using PRIMO or other ECPP based software for this purpose as it would take more than my life to complete

2006-11-16, 22:59	#2
Kosmaj Nov 2003 2×1,811 Posts	There is no way to prove it prime, AFAIK. Primo distributed version (not publicly available) takes months on 20k digit numbers, and yours has more than 300k digits! What you can do is the following, all using pfgw: test that it's PRP in another 2-3 bases, for example in base 7 run: pfgw -b7 -q(2^1127239+2^563620+1)/5 as other two bases select a prime between 10 and 30 and one larger than 100. And finally run the "-tc" test pfgw -tc -q... it will do some extra tests to show that it is "Fermat and Lucas PRP". You can submit it to the list of largest PRPs maintained by Henri Lifchitz currently, it will be the largest one. Congratulations!

2006-11-17, 01:19	#3
Kosmaj Nov 2003 111000100110₂ Posts	I see that you sent it to Top-5000. I'm afraid it will be deleted, but at least the tc test will be done on their machine It's going to take a while though (24 hrs?).

2006-11-18, 01:11	#5
paulunderwood Sep 2002 Database er0rr 2²·19·43 Posts	the number is composite: http://primes.utm.edu/primes/page.php?id=78860 Congrats for largest PRP is retracted by me Command: /home/caldwell/client/pfgw -tc -q"(2^1127239+2^563620+1)/5" 2>&1 PFGW Version 20031027.x86_Dev (Beta 'caveat utilitor') [FFT v22.13 w/P4] Primality testing (2^1127239+2^563620+1)/5 [N-1/N+1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 2 Using SSE2 FFT Adjusting authentication level by 1 for PRIMALITY PROOF Reduced from FFT(131072,20) to FFT(131072,19) Reduced from FFT(131072,19) to FFT(131072,18) 2254482 bit request FFT size=(131072,18) Running N-1 test using base 3 Using SSE2 FFT Adjusting authentication level by 1 for PRIMALITY PROOF Reduced from FFT(131072,20) to FFT(131072,19) Reduced from FFT(131072,19) to FFT(131072,18) 2254482 bit request FFT size=(131072,18) Running N+1 test using discriminant 11, base 3+sqrt(11) Using SSE2 FFT Adjusting authentication level by 1 for PRIMALITY PROOF Reduced from FFT(131072,20) to FFT(131072,19) Reduced from FFT(131072,19) to FFT(131072,18) 2254490 bit request FFT size=(131072,18) (2^1127239+2^563620+1)/5 is composite (-1716.3205s+0.0000s) [Ellapsed time: 94132 seconds]

2006-11-18, 02:58	#6
Kosmaj Nov 2003 2·1,811 Posts	Sorry to hear that There are several possibilities: 1) It's really 3-PRP but composite. That's entirely possible and that's the reason to try several more bases, and show that it's 7-PRP, 13-PRP etc. Check some entries on the largest PRP list, for example Jean-Louis Charton [Congrats Jean!] who holds the record tested as many as 7 bases on 4^341233-3^341233 (205443 digits). 2) There is a bug in LLR. That's also possible because GQ feature is a new one, much less tested than the mean-stream k*2^n-1 one. 3) Your hardware problem. Therefore, please run "pfgw -q(2^1127239+2^563620+1)/5", base=3 implied, on a stable hardware, if it's PRP mistery solved, if not than more tests will be required to find out what really happened. BTW, the PRP test will take much less time than the tc test which took 26 hrs on a Top-5000 machine, not more than 3 hrs on a 3GHz P-4 I think.

2006-11-18, 05:47	#7
paulunderwood Sep 2002 Database er0rr 2²·19·43 Posts	I confirmed Cruelty's 3-PRP with llr (for linux) and am now running PFGW PRP test with base 137, and then I will check with base-3 and maybe too I will test with PFGW -tc. But I am only using 3.4Ghz Pentium 4

2006-11-18, 06:00	#8
Cruelty May 2005 2×809 Posts	Strange, I have tested it with PFGW to find that: (2^1127239+2^563620+1)/5 is 3-PRP! (6992.4544s+0.0010s) (2^1127239+2^563620+1)/5 is 7-PRP! (22176.6766s+0.0022s) (2^1127239+2^563620+1)/5 is 13-PRP! (22235.2301s+0.0018s) I will run "-tc" command over weekend.

2006-11-18, 06:14	#9
paulunderwood Sep 2002 Database er0rr 2²·19·43 Posts	Cruelty, what version of PFGW did you uses? 1.2.0?