LLR Version 3.8.14 released (deprecated)

[IBethune]

Jean is currently away until 26th April, so he will probably not reply until then. I'll drop him an email so he's aware though.

Cheers

- Iain

[rogue]

Here are the results on my Mac (non-AVX):

./pfgw32 -V  -q"55459*2^159718+1"
PFGW Version 3.7.9.32BIT.20141125.Mac_Dev [GWNUM 28.6]

Special modular reduction using all-complex Pentium4 type-0 FFT length 12K, Pass1=48, Pass2=256 on 55459*2^159718+1                                    
Detected in MAXERR>0.45 (round off check) in prp_using_gwnum                                    
Iteration: 29697/159733 ERROR: ROUND OFF 0.5>0.45                                    
PFGW will automatically rerun the test with -a1                                    
Special modular reduction using all-complex type-1 FFT length 16K, Pass1=64, Pass2=256 on 55459*2^159718+1                                    
55459*2^159718+1 is composite: RES64: [B74B8609EBA5C47A] (43.1098s+0.0003s)   

                                 
./pfgw64 -V  -q"55459*2^159718+1"
PFGW Version 3.7.9.64BIT.20141125.Mac_Dev [GWNUM 28.6]

Special modular reduction using all-complex Pentium4 type-0 FFT length 12K, Pass1=48, Pass2=256 on 55459*2^159718+1                                    
55459*2^159718+1 is composite: RES64: [B74B8609EBA5C47A] (30.5987s+0.0003s)

Note that 32-bit pfgw catches the problem and reruns automatically with -a1. That makes me feel better. 64-bit pfgw returns the correct result and does not trigger the round off error.

[Batalov]

I found a truly unusual bug/feature in LLR. It is of a "gotcha" nature (i.e. you will never expect it).
Don't take it too hard; it is a bit whimsical but gave me a reason to scratch the top of my head.
I am pretty sure that it will be very easy to fix.

Try this input for the program

ABC ($a*$b^$c$d)/$e
1 30720 10771 -1 30719
1 30720 10789 -1 30719

(these are GRUs - Generalized Repunit candidates; I need a few of them for vertain tests)
Surprisingly, LLR starts very slowly and goes on for hours. Why is that? That's because it is testing not these numbers; it tests
(30720^118481-1)/30719 and (30720^118679-1)/30719 ! (that is - much larger numbers).
My hunch is that somehow it tries to reduce the base while raising the power (harmonize the number?).
It happens not just to this value of b but to any b divisible by 256, it seems (?).

PFGW happily takes the same input and processes it correctly. I prefer using LLR on similar PRPs, because LLR cleverly runs a special FFT (based on the numerator) and applies gcd with N after the last iteration; PFGW acts upon N and uses Generic modular reduction which is ~2 times slower. I've been using LLR for decimal repunits and near-repunits for quite some time now, but of course because the base was always 10, I've never encountered this bug before.

Note that the bug only shows up for ($a*$b^$c$d)/$e form. For $a*$b^$c$d header on the same file (even though these are definitely composites), the correct FFT size is chosen and the tests are fast.

[axn]

Originally Posted by Batalov

That's because it is testing not these numbers; it tests
(30720^118481-1)/30719 and (30720^118679-1)/30719 ! (that is - much larger numbers).
My hunch is that somehow it tries to reduce the base while raising the power (harmonize the number?).
It happens not just to this value of b but to any b divisible by 256, it seems (?).

Looking at the code, this will happen if the power of 2 part of the base > the remaining part of the base. In this case 30720 = 15*256 and 256 > 15. Relevant snippet is in LLR.c, process_num function. The fix for this is straightforward:

			if ((b_2up > b_else) && (!((format == ABCC) || (format == ABCK)))) {

should be changed to exclude all non-applicable formats.

[Batalov]

Here is an interesting composite strong-Fermat PSP; might be good for tests of different implementations:

(40216^11719-1)/40215 is base 3-Strong Fermat PRP! (53955 decimal digits) Time : 28.225 sec.
(40216^11719-1)/40215 is strong-Fermat PSP, but composite!! (P = 5, Q = 2), Lucas RES64: BEC0BFB78ED4A644 Time : 86.767 sec.

There is nothing trivially* wrong with this number. 40216 = 2^3 * 11 * 457, no threes in it.

Actually, with PFGW, it is a PRP in many bases, as well as by N+1/N-1 tests. Looks like another bug.

__________________
*For example, all (19683^p-1)/19682 are strong-Fermat PSP, but it is hardly surprising because 19683 is simply a power of 3, and these are classic false hitters.)

[paulunderwood]

Originally Posted by Batalov

might be good for tests of different implementations:

This is PRP according to my Ruby program and passes Pari's ispseudoprime()

[axn]

Originally Posted by Batalov

Here is an interesting composite strong-Fermat PSP

Large composite PRPs are much rarer than primes. As I have said in the other thread, a PRP test which is later overruled by a primality test, we should suspect the primality test as faulty.

Originally Posted by Batalov

Actually, with PFGW, it is a PRP in many bases, as well as by N+1/N-1 tests.

FWIW, the current factorization of N-1 in factordb stands at 6.8% (if a PRP482 and PRP1632 are proven), with an additional 0.3% easily accessible if a C159 (SNFS166) is factored. Still way short of a proof, but I guess a more thorough PRP test can be done using this.

[ATH]

Even with ErrorCheck=1:

(40216^11719-1)/40215 is base 3-Strong Fermat PRP! (53955 decimal digits) Time : 23.958 sec.
(40216^11719-1)/40215 is strong-Fermat PSP, but composite!! (P = 5, Q = 2), Lucas RES64: BEC0BFB78ED4A644 Time : 68.024 sec.

But with BPSW=1 and ErrorCheck=1:

(40216^11719-1)/40215 is base 2-Strong Fermat PRP! (53955 decimal digits) Time : 22.471 sec.
(40216^11719-1)/40215 is strong-Fermat, BPSW and Frobenius PRP! (P = 1, Q = -4, D = 17) Time : 91.620 sec.

Prime 95:

UID: athath/xps, 40216^11719-1/40215 is a probable prime (2-PRP)! We4: 5B8E5B8E,00000000
UID: athath/xps, 40216^11719-1/40215 is a probable prime! We4: 5B8E5B8E,00000000
UID: athath/xps, 40216^11719-1/40215 is a probable prime (5-PRP)! We4: 5B8E5B8E,00000000
UID: athath/xps, 40216^11719-1/40215 is a probable prime (7-PRP)! We4: 5B8E5B8E,00000000
UID: athath/xps, 40216^11719-1/40215 is a probable prime (11-PRP)! We4: 5B8E5B8E,00000000
UID: athath/xps, 40216^11719-1/40215 is a probable prime (13-PRP)! We4: 5B8E5B8E,00000000
UID: athath/xps, 40216^11719-1/40215 is a probable prime (17-PRP)! We4: 5B8E5B8E,00000000
UID: athath/xps, 40216^11719-1/40215 is a probable prime (19-PRP)! We4: 5B8E5B8E,00000000

[Batalov]

Originally Posted by axn

Large composite PRPs are much rarer than primes. As I have said in the other thread, a PRP test which is later overruled by a primality test, we should suspect the primality test as faulty.

That's exactly right.
In this particular size range (53-54K decimal digits), I've mined ~170 GRU PRPs with the intent to find 1-2 provable ones, and three more failed the second test and one passed second test and failed third (LLR runs three tests: sPRP Fermat, Lucas PRP and Frobenius PRP).
Here are the artifacts (I can release them because I've run the ECM campaign on their cylotomic N-1 cofactors, and will not pursue them likely; but someone might get luckier than me):

(40216^11719-1)/40215 is strong-Fermat PSP, but composite!! (P = 5, Q = 2), Lucas RES64: BEC0BFB78ED4A644  Time : 86.767 sec.
(48591^11329-1)/48590 is strong-Fermat and Lucas PSP (P = 7, Q = 4), but composite!!. Frobenius RES64: 40E9023023389690  Time : 110.794 sec.
(50322^11317-1)/50321 is strong-Fermat PSP, but composite!! (P = 5, Q = 2), Lucas RES64: F21F95D6F87D6D1B  Time : 81.442 sec.
(57042^11491-1)/57041 is strong-Fermat PSP, but composite!! (P = 5, Q = 2), Lucas RES64: 4CC3D7F332318CCE  Time : 98.488 sec.
(57352^11491-1)/57351 is strong-Fermat PSP, but composite!! (P = 5, Q = 2), Lucas RES64: 35EED4E3D5D92268  Time : 89.354 sec.

They are good contenders for the GRU Top20 category, if one can ECM and prove a couple Phi() cofactors.

[paulunderwood]

FWIW: All 5 pass my Ruby fu_prp test

[ATH]

For some reason (48591^11329-1)/48590 fails 2-PRP in Prime 95:
(with PRPBase=2 in Prime.txt and worktodo.txt: PRP=1,48591,11329,-1,"48590")

(48591^11329-1)/48590 is strong-Fermat, BPSW and Frobenius PRP! (P = 1, Q = 3, D = -11)  Time : 173.881 sec.
UID: athath/xps, 48591^11329-1/48590 is not prime.  RES64: A0748118119C4B49. We4: 58825882,00000000
UID: athath/xps, 48591^11329-1/48590 is a probable prime! We4: 58825882,00000000
UID: athath/xps, 48591^11329-1/48590 is a probable prime (5-PRP)! We4: 58825882,00000000
UID: athath/xps, 48591^11329-1/48590 is a probable prime (7-PRP)! We4: 58825882,00000000
UID: athath/xps, 48591^11329-1/48590 is a probable prime (11-PRP)! We4: 58825882,00000000
UID: athath/xps, 48591^11329-1/48590 is a probable prime (13-PRP)! We4: 58825882,00000000
UID: athath/xps, 48591^11329-1/48590 is a probable prime (17-PRP)! We4: 58825882,00000000
UID: athath/xps, 48591^11329-1/48590 is a probable prime (19-PRP)! We4: 58825882,00000000

(50322^11317-1)/50321 is strong-Fermat, BPSW and Frobenius PRP! (P = 1, Q = 3, D = -11)  Time : 175.995 sec.
UID: athath/xps, 50322^11317-1/50321 is a probable prime (2-PRP)! We4: 586A586A,00000000
UID: athath/xps, 50322^11317-1/50321 is a probable prime! We4: 586A586A,00000000
UID: athath/xps, 50322^11317-1/50321 is a probable prime (5-PRP)! We4: 586A586A,00000000
UID: athath/xps, 50322^11317-1/50321 is a probable prime (7-PRP)! We4: 586A586A,00000000
UID: athath/xps, 50322^11317-1/50321 is a probable prime (11-PRP)! We4: 586A586A,00000000
UID: athath/xps, 50322^11317-1/50321 is a probable prime (13-PRP)! We4: 586A586A,00000000
UID: athath/xps, 50322^11317-1/50321 is a probable prime (17-PRP)! We4: 586A586A,00000000
UID: athath/xps, 50322^11317-1/50321 is a probable prime (19-PRP)! We4: 586A586A,00000000

(57042^11491-1)/57041 is strong-Fermat, BPSW and Frobenius PRP! (P = 1, Q = 4, D = -15)  Time : 167.904 sec.
UID: athath/xps, 57042^11491-1/57041 is a probable prime (2-PRP)! We4: 59C659C6,00000000
UID: athath/xps, 57042^11491-1/57041 is a probable prime! We4: 59C659C6,00000000
UID: athath/xps, 57042^11491-1/57041 is a probable prime (5-PRP)! We4: 59C659C6,00000000
UID: athath/xps, 57042^11491-1/57041 is a probable prime (7-PRP)! We4: 59C659C6,00000000
UID: athath/xps, 57042^11491-1/57041 is a probable prime (11-PRP)! We4: 59C659C6,00000000
UID: athath/xps, 57042^11491-1/57041 is a probable prime (13-PRP)! We4: 59C659C6,00000000
UID: athath/xps, 57042^11491-1/57041 is a probable prime (17-PRP)! We4: 59C659C6,00000000
UID: athath/xps, 57042^11491-1/57041 is a probable prime (19-PRP)! We4: 59C659C6,00000000

(57352^11491-1)/57351 is strong-Fermat, BPSW and Frobenius PRP! (P = 1, Q = 4, D = -15)  Time : 165.694 sec.
UID: athath/xps, 57352^11491-1/57351 is a probable prime (2-PRP)! We4: 59C659C6,00000000
UID: athath/xps, 57352^11491-1/57351 is a probable prime! We4: 59C659C6,00000000
UID: athath/xps, 57352^11491-1/57351 is a probable prime (5-PRP)! We4: 59C659C6,00000000
UID: athath/xps, 57352^11491-1/57351 is a probable prime (7-PRP)! We4: 59C659C6,00000000
UID: athath/xps, 57352^11491-1/57351 is a probable prime (11-PRP)! We4: 59C659C6,00000000
UID: athath/xps, 57352^11491-1/57351 is a probable prime (13-PRP)! We4: 59C659C6,00000000
UID: athath/xps, 57352^11491-1/57351 is a probable prime (17-PRP)! We4: 59C659C6,00000000
UID: athath/xps, 57352^11491-1/57351 is a probable prime (19-PRP)! We4: 59C659C6,00000000