Yet another LLR bug

nuggetprime · 2011-02-18, 16:33

I have observed the following in LLR version 3.8.5:
When testing 10^500+961, LLR tells me:

Code:

Starting probable prime test of 10^500+961

10^500+961 is not prime, although base 3-Fermat PSP!!  Time : 32.815 ms.

but 10^500+961 has been certified prime using Primo!

Nugget

rogue · 2011-02-18, 17:12

Quote:

Originally Posted by nuggetprime

I have observed the following in LLR version 3.8.5:
When testing 10^500+961, LLR tells me:

Code:

Starting probable prime test of 10^500+961

10^500+961 is not prime, although base 3-Fermat PSP!!  Time : 32.815 ms.

but 10^500+961 has been certified prime using Primo!

LLR cannot prove primality for this number. If anything, the message is inaccurate.

nuggetprime · 2011-02-18, 17:51

Normally,LLR outputs when it can't prove a number prime:

Code:

Starting probable prime test of 2^21954+77899
2^21954+77899 is base 3-Strong Fermat PRP!  Time : 1.728 sec.
Starting Lucas sequence
2^21954+77899 is Lucas PRP, Starting Frobenius test sequence
 2^21954+77899 is Frobenius PRP! (P = 4, Q = 2, D = 8)  Time : 6.928 sec.

But for 10^500+961 it doesn't run a Lucas or Frobenius sequence and instead says the number is not prime.
So I think it really is a bug.

nuggetprime · 2011-02-18, 17:57

Code:

./llr-3.8.5 -d -q5*10^19737+3
Starting probable prime test of 5*10^19737+3
                                                                                                                                                                5*10^19737+3 is base 3-Strong Fermat PRP!  Time : 12.733 sec.
Starting Lucas sequence
Speicherzugriffsfehlerlength 4K, P = 4, Q = 2

"Speicherzugriffsfehler" means that it SEGV'ed here,trying to compute the Lucas sequence.

nuggetprime · 2011-02-23, 12:31

BUMPed.
Also forwarded to Jean Penne.

Jean Penné · 2011-02-28, 21:14

Hi,

These two bugs are now fixed :

- For 10^500+961, it is really a bug of the strong Fermat PRP code in the Llr.c file. It will be fixed in the Development version ; here is the correct behaviour :

Starting probable prime test of 10^500+961
Using all-complex FFT length 192, a = 3
10^500+961 is base 3-Strong Fermat PRP! Time : 121.052 ms.
Starting Lucas sequence
Using all-complex FFT length 192, P = 5, Q = 3
10^500+961 is strong-Fermat and Lucas PRP, Starting Frobenius test sequence
Using all-complex FFT length 192, Q = 3
10^500+961 is strong-Fermat, Lucas and Frobenius PRP! (P = 5, Q = 3, D = 13) Time : 72.780 ms.

For 5*10^19737+3, it is a gwnum problem : gwnum chooses a full-complex 4K FFT, which seems to be too small, and causes a segmentation fault after a few iterations... And the test works if I force the program to choose the third next larger FFT! Here is the result, using the uncorrected LLR on Linux :

~/llr385src/linuxllr $ ./llr -a3 -oVerbose=1 -oLucasPRPtest=1 -oFFT_Increment=3 -d -q"5*10^19737+3"
Starting Lucas sequence
5*10^19737+3 is Lucas PRP, Starting Frobenius test sequence
5*10^19737+3 is Frobenius PRP! (P = 4, Q = 2, D = 8) Time : 127.685 sec.

The chosen FFT is then Zero padded 10K...

Note : The -oLucasPRPtest=1 is necessary here, to skip the Fermat test which reset the FFT increment at its completion... This drawback will be corrected in the Development version. I shall release it soon...

I shall also warn George about this gwnum problem.
Best Regards,
Jean

rogue · 2011-02-28, 21:52

Quote:

Originally Posted by Jean Penné

Hi,

These two bugs are now fixed :

- For 10^500+961, it is really a bug of the strong Fermat PRP code in the Llr.c file. It will be fixed in the Development version ; here is the correct behaviour :

Starting probable prime test of 10^500+961
Using all-complex FFT length 192, a = 3
10^500+961 is base 3-Strong Fermat PRP! Time : 121.052 ms.
Starting Lucas sequence
Using all-complex FFT length 192, P = 5, Q = 3
10^500+961 is strong-Fermat and Lucas PRP, Starting Frobenius test sequence
Using all-complex FFT length 192, Q = 3
10^500+961 is strong-Fermat, Lucas and Frobenius PRP! (P = 5, Q = 3, D = 13) Time : 72.780 ms.

For 5*10^19737+3, it is a gwnum problem : gwnum chooses a full-complex 4K FFT, which seems to be too small, and causes a segmentation fault after a few iterations...

I suspect that it might be CPU specific or specific to the 32-bit version. On 64-bit MacIntel, pfgw chooses the 4K FFT and it runs without a problem. Granted pfgw and llr use different code. I would have to try with 64-bit llr on MacIntel to know for certain.

Prime95 · 2011-02-28, 23:37

Quote:

Originally Posted by Jean Penné

For 5*10^19737+3, it is a gwnum problem : gwnum chooses a full-complex 4K FFT, which seems to be too small, and causes a segmentation fault after a few iterations... And the test works if I force the program to choose the third next larger FFT!

What system is this? A PRP test using 32-bit Windows Prime95 on a Core 2 works using a 4K FFT.

Jean Penné · 2011-03-01, 21:10

Quote:

Originally Posted by Prime95

What system is this? A PRP test using 32-bit Windows Prime95 on a Core 2 works using a 4K FFT.

Hi,

I can now add some precisions about this problem :

-It occurs each time I am running a Lucas PRP test on a k*b^n+c number with c != 1 AND a full complex FFT is chosen.

- If I force a larger FFT, the test works as soon as Zero padded is chosen.
- It works also if I force generic reduction.

- No matter if the base b is two or not...

- Surprisingly, the simple strong Fermat PRP test (which uses only gwsquare) works always!

For the Lucas test, I get a segmentation fault on these two systems :

On Windows 2000 and VC 6.0 :
CPU Information:
Intel(R) Pentium(R) 4 CPU 2.53GHz
CPU speed: 2533.16 MHz
CPU features: RDTSC, CMOV, PREFETCH, MMX, SSE, SSE2
L1 cache size: 8 KB
L2 cache size: 512 KB

On Linux with 32 bit gcc and gwnum library :
CPU Information:
AMD Athlon(tm) 64 Processor 3700+
CPU speed: 2199.85 MHz
CPU features: RDTSC, CMOV, PREFETCH, MMX, SSE, SSE2
L1 cache size: 64 KB
L2 cache size: 1024 KB

I hope it will help...

Regards,
Jean

rogue · 2011-03-01, 22:16

I was able to reproduce this on Windows (in LLR). The problem is triggered by this line:

gwfftmul (gwdata, tmp2, tmp4); /* Compute s*random */

in gwmul_carefully. Both tmp2 and tmp4 are good values.

Prime95 · 2011-03-02, 01:20

Ugh, I cannot reproduce in Prime95 using my QA code that calls every gwnum routine.

I did download and compile the LLR source, but don't know how to use it. Can you upload an input file that exhibits the problem? Thanks.

2011-02-18, 16:33	#1
nuggetprime Mar 2007 Austria 456₈ Posts	Yet another LLR bug I have observed the following in LLR version 3.8.5: When testing 10^500+961, LLR tells me: Code: Starting probable prime test of 10^500+961 10^500+961 is not prime, although base 3-Fermat PSP!! Time : 32.815 ms. but 10^500+961 has been certified prime using Primo! Nugget Last fiddled with by nuggetprime on 2011-02-18 at 16:34

2011-02-18, 17:51	#3
nuggetprime Mar 2007 Austria 2·151 Posts	Normally,LLR outputs when it can't prove a number prime: Code: Starting probable prime test of 2^21954+77899 2^21954+77899 is base 3-Strong Fermat PRP! Time : 1.728 sec. Starting Lucas sequence 2^21954+77899 is Lucas PRP, Starting Frobenius test sequence 2^21954+77899 is Frobenius PRP! (P = 4, Q = 2, D = 8) Time : 6.928 sec. But for 10^500+961 it doesn't run a Lucas or Frobenius sequence and instead says the number is not prime. So I think it really is a bug. Last fiddled with by nuggetprime on 2011-02-18 at 17:53

2011-02-28, 21:14	#6
Jean Penné May 2004 FRANCE 1062₈ Posts	The two bugs on LLR 3.8.5 are fixed! Hi, These two bugs are now fixed : - For 10^500+961, it is really a bug of the strong Fermat PRP code in the Llr.c file. It will be fixed in the Development version ; here is the correct behaviour : Starting probable prime test of 10^500+961 Using all-complex FFT length 192, a = 3 10^500+961 is base 3-Strong Fermat PRP! Time : 121.052 ms. Starting Lucas sequence Using all-complex FFT length 192, P = 5, Q = 3 10^500+961 is strong-Fermat and Lucas PRP, Starting Frobenius test sequence Using all-complex FFT length 192, Q = 3 10^500+961 is strong-Fermat, Lucas and Frobenius PRP! (P = 5, Q = 3, D = 13) Time : 72.780 ms. For 510^19737+3, it is a gwnum problem : gwnum chooses a full-complex 4K FFT, which seems to be too small, and causes a segmentation fault after a few iterations... And the test works if I force the program to choose the third next larger FFT! Here is the result, using the uncorrected LLR on Linux : ~/llr385src/linuxllr $ ./llr -a3 -oVerbose=1 -oLucasPRPtest=1 -oFFT_Increment=3 -d -q"510^19737+3" Starting Lucas sequence 510^19737+3 is Lucas PRP, Starting Frobenius test sequence 510^19737+3 is Frobenius PRP! (P = 4, Q = 2, D = 8) Time : 127.685 sec. The chosen FFT is then Zero padded 10K... Note : The -oLucasPRPtest=1 is necessary here, to skip the Fermat test which reset the FFT increment at its completion... This drawback will be corrected in the Development version. I shall release it soon... I shall also warn George about this gwnum problem. Best Regards, Jean

2011-02-23, 12:31	#5
nuggetprime Mar 2007 Austria 12E₁₆ Posts	BUMPed. Also forwarded to Jean Penne.

2011-03-01, 22:16	#10
rogue "Mark" Apr 2003 Between here and the 1820₁₆ Posts	I was able to reproduce this on Windows (in LLR). The problem is triggered by this line: gwfftmul (gwdata, tmp2, tmp4); /* Compute srandom / in gwmul_carefully. Both tmp2 and tmp4 are good values.

2011-03-02, 01:20	#11
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 67×109 Posts	Ugh, I cannot reproduce in Prime95 using my QA code that calls every gwnum routine. I did download and compile the LLR source, but don't know how to use it. Can you upload an input file that exhibits the problem? Thanks.