mersenneforum.org Yet another LLR bug
 Register FAQ Search Today's Posts Mark Forums Read

 2011-02-18, 16:33 #1 nuggetprime     Mar 2007 Austria 2×151 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:12   #2
rogue

"Mark"
Apr 2003
Between here and the

142418 Posts

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.

 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-18, 17:57 #4 nuggetprime     Mar 2007 Austria 2·151 Posts Another problem 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.
 2011-02-23, 12:31 #5 nuggetprime     Mar 2007 Austria 2×151 Posts BUMPed. Also forwarded to Jean Penne.
 2011-02-28, 21:14 #6 Jean Penné     May 2004 FRANCE 3·193 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 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
2011-02-28, 21:52   #7
rogue

"Mark"
Apr 2003
Between here and the

5×13×97 Posts

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.

2011-02-28, 23:37   #8
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

3×5×499 Posts

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.

2011-03-01, 21:10   #9
Jean Penné

May 2004
FRANCE

3×193 Posts
Proble with c!=1 and IBDWT...

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,

-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

 2011-03-01, 22:16 #10 rogue     "Mark" Apr 2003 Between here and the 5·13·97 Posts 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.
 2011-03-02, 01:20 #11 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 748510 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.