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.
[/CODE]but 10^500+961 has been certified prime using Primo!

Nugget

[QUOTE=nuggetprime;252928]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.
[/CODE]but 10^500+961 has been certified prime using Primo![/QUOTE]

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

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.
[/CODE]
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.

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
[/CODE]
"Speicherzugriffsfehler" means that it SEGV'ed here,trying to compute the Lucas sequence.

BUMPed.
Also forwarded to Jean Penne.

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

[QUOTE=Jean Penné;254001]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...[/QUOTE]

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.

[QUOTE=Jean Penné;254001]

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! [/QUOTE]

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

Proble with c!=1 and IBDWT...
 

[QUOTE=Prime95;254015]What system is this? A PRP test using 32-bit Windows Prime95 on a Core 2 works using a 4K FFT.[/QUOTE]

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

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.

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.