mersenneforum.org A possible bug in LLR/PFGW while using GWNUM (no bug in P95)
 Register FAQ Search Today's Posts Mark Forums Read

2014-12-15, 07:56   #1
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×3,329 Posts
A possible bug in LLR/PFGW while using GWNUM (no bug in P95)

Quote:
 Originally Posted by Prime95 Congrats. Try adding PRPBase=n to prime.txt.
Hmmm...

I added PRPBase=7 to prime.txt and I got that 1024 · 3^1877301 + 1 is a 7-PRP (??).
I changed PRPBase=11 in prime.txt and I got that 1024 · 3^1877301 + 1 is a 11-PRP (??).
Yet it is a composite by pfgw and llr (or mprime doesn't actually change the base). Though it is likely a 3-PRP (and a 3-SPRP by llr).

I am using one worker with 12, 16, 24 threads (27.9, the AVX code is being used).
Maybe the multi-threaded code doesn't change the base?

2014-12-15, 08:10   #2
axn

Jun 2003

34×67 Posts

Quote:
 Originally Posted by Batalov Maybe the multi-threaded code doesn't change the base?
Easy enough to check by applying it on (another) (small) composite number and making sure the residues are all different?

 2014-12-15, 08:44 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3×3,329 Posts That's a good idea! Thanks. RES64 values are different! I've now put PRPBase=5 everywhere. Before [PrimeNet] section, after, and in local.txt, too. ;-) Now, I am thinking, maybe this is after all a prime? Can't be so easily a 7-PRP and a 11-PRP and a 3-PRP and then a composite. Maybe the reason is a devious FFT overflow.
2014-12-15, 09:04   #4
axn

Jun 2003

542710 Posts

Quote:
 Originally Posted by Batalov Now, I am thinking, maybe this is after all a prime? Can't be so easily a 7-PRP and a 11-PRP and a 3-PRP and then a composite. Maybe the reason is a devious FFT overflow.
If the latest PFGW still supports it, time to run it with -a1 or -a2 ?

 2014-12-15, 09:20 #5 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 270316 Posts Yes, I am running that but it will take quite a bit of time. Another one that I am running (actually times five): llr N-1 with FermatBase=7, 11, 13, 17, 19 (you change it in llr.ini, before the test). What is nice is that with a=11, a different FFT size is chosen. (For a=5 240K, for a=11, 256K.)
 2014-12-15, 10:08 #6 axn     Jun 2003 124638 Posts FWIW Code: 1024*3^1877301+1 is a probable prime! We4: EC696ADA,00000000 This is with Code: PRPBase=2 Running single thread using P95 v28.5 build 2 Win64 version on a Core-i5 3340M
 2014-12-15, 11:23 #7 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3×3,329 Posts My pfgw runs finished. By them, ... it is a prime, after all. Code: PFGW Version 3.7.2.64BIT.20130122.x86_Dev [GWNUM 27.9] Output logging to file pfgw.out Factoring numbers to 1% of normal. Primality testing 1024*3^1877301+1 [N-1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 5 1024*3^1877301+1 is prime! (12398.0381s+0.0164s) This thing is driving me nuts. ;-) There must be some numeric instability in FFT. (Plus many PRP tests in many bases with P95 are positive. The -a2 test is still running...)
2014-12-15, 11:50   #8
axn

Jun 2003

34·67 Posts

Quote:
 Originally Posted by Batalov This thing is driving me nuts. ;-) There must be some numeric instability in FFT.
Indeed. Over the years, there have been similar instances reported in the forum -- where a positive PRP test was overruled by a proof test.

I think in all such cases, we should suspect the proof test, because it is much more probable that an error caused the "composite" result rather than the incredibly rare occurrence of a large pseudoprime.

 2014-12-15, 11:59 #9 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3·3,329 Posts This is probably confined to k*b^n+-1 where b>2, especially b=3 (because the default PRP/N-1 test base is 3). Only those who hunt for "non-boring" primes occasionally step into these traps -- this includes people at CRUS. b=2 is relatively much better debugged - traditional Proth/Riesel which are the mainstream. The prime database is cracking at the seams with these (esp. the b=2, n=1290000).
 2014-12-15, 22:01 #10 paulunderwood     Sep 2002 Database er0rr 2·3·727 Posts How many digits does your problem number have? I ask because TPP says 895704, but I get this: Code:  ./pfgw64 -od -q"1024*3^1877301+1" PFGW Version 3.7.7.64BIT.20130722.x86_Dev [GWNUM 27.11] 1024*3^1877301+1: 16554132 818435073 Code:  wc Serge 1 1 895705 Serge ps. I am running your number through a GMP implementation of my algorithm with the GWNUM 27.11 output from pfgw64. Last fiddled with by paulunderwood on 2014-12-15 at 22:08
 2014-12-15, 22:13 #11 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 11111100101002 Posts I ran this using prime95 version 28.5 with AVX but not FMA FFTs. Prime95 chose a 240K FFT size. Round off error was only 0.02. It worked. My conclusion is the problem is not in choosing an FFT size that is too small. Either a GWNUM bug was fixed between 27.9 and 28.5 or PFGW's PRP code is doing something subtly different than prime95's and either has a bug or reveals a bug in GWNUM. I'm a little confused about what is failing in PFGW. Does PFGW report it as a PRP or is the problem only in the N-1 proving code?

 Similar Threads Thread Thread Starter Forum Replies Last Post rogue Software 526 2022-11-17 19:55 Jean Penné Software 25 2010-11-01 15:18 Joe O Sierpinski/Riesel Base 5 5 2010-09-30 14:07 Unregistered Information & Answers 3 2010-09-12 19:52 Cyclamen Persicum Software 1 2007-01-02 20:53

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

Wed Nov 30 14:17:59 UTC 2022 up 104 days, 11:46, 1 user, load averages: 1.55, 1.32, 1.14