A possible bug in LLR/PFGW while using GWNUM (no bug in P95)

Batalov · 2014-12-15, 07:56

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?

axn · 2014-12-15, 08:10

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?

Batalov · 2014-12-15, 08:44

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.

axn · 2014-12-15, 09:04

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 ?

Batalov · 2014-12-15, 09:20

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.)

axn · 2014-12-15, 10:08

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

Batalov · 2014-12-15, 11:23

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...)

axn · 2014-12-15, 11:50

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.

Batalov · 2014-12-15, 11:59

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).

paulunderwood · 2014-12-15, 22:01

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 <SNIP> 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.

Prime95 · 2014-12-15, 22:13

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?

2014-12-15, 10:08	#6
axn Jun 2003 1010100111110₂ 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×7×479 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 10243^1877301+1 [N-1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 5 10243^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, 22:01	#10
paulunderwood Sep 2002 Database er0rr 5·29·31 Posts	How many digits does your problem number have? I ask because TPP says 895704, but I get this: Code: ./pfgw64 -od -q"10243^1877301+1" PFGW Version 3.7.7.64BIT.20130722.x86_Dev [GWNUM 27.11] 10243^1877301+1: 16554132 <SNIP> 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
PFGW 4.0.4 (with gwnum v30.10) Released	rogue	Software	545	2023-01-20 14:12
LLR V3.8.2 using gwnum 26.2 is available!	Jean Penné	Software	25	2010-11-01 15:18
PFGW 3.3.6 or PFGW 3.4.2 Please update now!	Joe O	Sierpinski/Riesel Base 5	5	2010-09-30 14:07
GWNUM?	Unregistered	Information & Answers	3	2010-09-12 19:52
GWNUM as DLL?	Cyclamen Persicum	Software	1	2007-01-02 20:53

2014-12-15, 08:44	#3
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3·7·479 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:20	#5
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3·7·479 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, 11:59	#9
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3·7·479 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:13	#11
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 8164₁₀ 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?