Can PFGW run the strong Lucas primality test?

[sweety439]

Can PFGW run the strong Lucas primality test, with parameters (P, Q) defined by Selfridge's Method A (see https://oeis.org/A217255 and http://ntheory.org/pseudoprimes.html)? I have used PFGW to verified that all these numbers (these numbers are minimal primes (start with b+1) base b, assuming their primality) are strong probable primes to bases 2, 3, 5, 7, 11, 13, 17, 19, 23, and trial factored to 10^11:

b index of this minimal prime in base b (assuming the primality of all probable primes in base b) base-b form of the unproven probable prime algebraic ((a*b^n+c)/d) form of the unproven probable prime
11 1068 5(7^62668) (57×11^62668−7)/10
13 3194 C(5^23755)C (149×13^23756+79)/12
13 3195 8(0^32017)111 8×13^32020+183
16 2344 D0(B^17804) (3131×16^17804−11)/15
16 2345 D(B^32234) (206×16^32234−11)/15
22 8003 B(K^22001)5 (251×22^22002−335)/21
30 2618 I(0^24608)D 18×30^24609+13

(all other minimal primes (start with b+1) in bases 11, 13, 16, 22, 30 (as well as all minimal primes (start with b+1) in bases 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 24) have been proven to be primes, see this post)

However, only run strong tests is still dangerous, since there are many numbers which are strong pseudoprimes to first few prime bases, see https://oeis.org/A014233, most numbers are of the form (n+1)*(2*n+1) (with n+1, 2*n+1 both primes) or (n+1)*(3*n+1) (with n+1, 3*n+1 both primes), these numbers are == 1 (mod m) for many small m, however, if we combine these primality tests with strong Lucas primality test, with parameters (P, Q) defined by Selfridge's Method A (as well as trial factoring), then a number that passes all these tests is very likely to be prime, thus I want to run strong Lucas primality test (with parameters (P, Q) defined by Selfridge's Method A) for these numbers, however, how to run these tests in PFGW?

[paulunderwood]

No. PFGW does not run a strong Lucas PRP test. It could if you altered the source code. If you really want to strong Lucas test these numbers you could run the GMP program I wrote

[sweety439]

Originally Posted by paulunderwood

No. PFGW does not run a strong Lucas PRP test. It could if you altered the source code. If you really want to strong Lucas test these numbers you could run the GMP program I wrote

So can you run the strong Lucas PRP test (with parameters (P, Q) defined by Selfridge's Method A) for these seven numbers?

[mathwiz]

Originally Posted by sweety439

So can you run the strong Lucas PRP test (with parameters (P, Q) defined by Selfridge's Method A) for these seven numbers?

He literally gave you the source code to do what you want. Stop asking others to run tests on particular numbers for you.

[sweety439]

Originally Posted by mathwiz

He literally gave you the source code to do what you want. Stop asking others to run tests on particular numbers for you.

OK, I will run it myself.

[paulunderwood]

Originally Posted by sweety439

So can you run the strong Lucas PRP test (with parameters (P, Q) defined by Selfridge's Method A) for these seven numbers?

Not really. I can run with (P,1) with min P: Jacobi(P^2-4,n)==-1. Will that do for you sir?

Here are the results as they come in:

echo 'print((57*11^62668-7)/10)' | gp -q | ./gmp_miller-rabin_strong-lucas 0 1
Passed strong Lucas PRP test over x^2-4*x+1.

echo 'print((149*13^23756+79)/12)' | gp -q | ./gmp_miller-rabin_strong-lucas 0 1
Passed strong Lucas PRP test over x^2-9*x+1.

echo 'print(8*13^32020+183)' | gp -q | ./gmp_miller-rabin_strong-lucas 0 1
Passed strong Lucas PRP test over x^2-5*x+1.

echo 'print((3131*16^17804-11)/15)' | gp -q | ./gmp_miller-rabin_strong-lucas 0 1
Passed strong Lucas PRP test over x^2-3*x+1.

echo 'print((206*16^32234-11)/15)' | gp -q | ./gmp_miller-rabin_strong-lucas 0 1
Passed strong Lucas PRP test over x^2-3*x+1.

echo 'print((251*22^22002-335)/21)' | gp -q | ./gmp_miller-rabin_strong-lucas 0 1
Passed strong Lucas PRP test over x^2-4*x+1.

echo 'print(18*30^24609+13)' | gp -q | ./gmp_miller-rabin_strong-lucas 0 1
Passed strong Lucas PRP test over x^2-3*x+1.

Completed

[sweety439]

How to do trial factoring to 10^16? I found that many large numbers in PRP top are trial factoring (or sieving) to 2^64

However, when I use PFGW to do trial factoring to 10^16, I get:

C:\Users\user\OneDrive\桌面\minimal>pfgw.exe -f -e10000000000000000 k.txt
PFGW Version 3.3.6.20100908.Win_Stable [GWNUM 25.14]

WARNING, trial factoring past 2^48 is NOT tested, and may not work correctly
trial factoring to 10000000000000000
F: (57*11^62668-7)/10 59392/3091341693

(I do not know how to sieve the sequences like (57*11^n-7)/10, since srsieve cannot handle sequences (a*b^n+c)/d with d > 1, I only found that (57*11^62668-7)/10 is the smallest prime or PRP of the form (57*11^n-7)/10 with n >= 1, without use srsieve, I use PFGW directly for (57*11^n-7)/10 for all even n)

(also, does the "Probable prime" box in the "Primality proving" box of factordb use the strong test? I already checked all prime bases <= 61 to all these seven PRPs in factordb)

[paulunderwood]

Originally Posted by sweety439

How to do trial factoring to 10^16? I found that many large numbers in PRP top are trial factoring (or sieving) to 2^64

However, when I use PFGW to do trial factoring to 10^16, I get:

C:\Users\user\OneDrive\桌面\minimal>pfgw.exe -f -e10000000000000000 k.txt
PFGW Version 3.3.6.20100908.Win_Stable [GWNUM 25.14]

WARNING, trial factoring past 2^48 is NOT tested, and may not work correctly
trial factoring to 10000000000000000
F: (57*11^62668-7)/10 59392/3091341693

(I do not know how to sieve the sequences like (57*11^n-7)/10, since srsieve cannot handle sequences (a*b^n+c)/d with d > 1, I only found that (57*11^62668-7)/10 is the smallest prime or PRP of the form (57*11^n-7)/10 with n >= 1, without use srsieve, I use PFGW directly for (57*11^n-7)/10 for all even n)

(also, does the "Probable prime" box in the "Primality proving" box of factordb use the strong test? I already checked all prime bases <= 61 to all these seven PRPs in factordb)

10^16? Are you kidding? How many primes is that? Assuming PFGW can do one division per computer cycle -- which it can't -- how long would it take?

FactorDB does a Fermat PRP.

I will post the results of 10 strong Fermat and 10 strong Lucas tests here soon. Note: one of each has never been fooled in nearly 40 years since it was devised.

[charybdis]

Originally Posted by sweety439

How to do trial factoring to 10^16? I found that many large numbers in PRP top are trial factoring (or sieving) to 2^64

The ones that are factored to huge limits like that have special forms that restrict the possibilities for factors. For example, any prime dividing (17^1990523-1)/16 would have to be 1 mod 1990523.
Your number (57*11^62668-7)/10 has no such restrictions.

[paulunderwood]

As promised:

echo 'print((57*11^62668-7)/10)' | gp -q | ./gmp_miller-rabin_strong-lucas 10 10
Passed Miller-Rabin PRP test with base 2.
Passed Miller-Rabin PRP test with base 3.
Passed Miller-Rabin PRP test with base 5.
Passed Miller-Rabin PRP test with base 7.
Passed Miller-Rabin PRP test with base 11.
Passed Miller-Rabin PRP test with base 13.
Passed Miller-Rabin PRP test with base 17.
Passed Miller-Rabin PRP test with base 19.
Passed Miller-Rabin PRP test with base 23.
Passed Miller-Rabin PRP test with base 29.
Passed strong Lucas PRP test over x^2-4*x+1.
Passed strong Lucas PRP test over x^2-6*x+1.
Passed strong Lucas PRP test over x^2-8*x+1.
Passed strong Lucas PRP test over x^2-11*x+1.
Passed strong Lucas PRP test over x^2-12*x+1.
Passed strong Lucas PRP test over x^2-14*x+1.
Passed strong Lucas PRP test over x^2-15*x+1.
Passed strong Lucas PRP test over x^2-16*x+1.
Passed strong Lucas PRP test over x^2-17*x+1.
Passed strong Lucas PRP test over x^2-20*x+1.
Testing completed.

[sweety439]

Originally Posted by paulunderwood

As promised:

The original minimal prime problem, and I generalized this problem to other bases, but I only consider the primes > base, i.e. found all primes > b such that there is no shorter subsequence of its digits in a given base b that form a prime > b, and by the theorem that there are no infinite antichains for the subsequence ordering, there must be only finitely many such primes, e.g. in decimal (base 10), there are 77 such primes: {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027}

My article for bases 2 <= b <= 16

My data for these primes in GitHub

All primes in the minimal set of the primes > b in base b for bases b = 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 24 are proven primes, i.e. not merely probable primes, and thus bases 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 24 have "minimal prime > base theorem", and there are 8 unproven PRPs in the minimal set of the primes > b in base b for bases b = 11, 13, 16, 22, 30, including a recently found PRP

b index of this minimal prime in base b (assuming the primality of all probable primes in base b) base-b form of the unproven probable prime algebraic ((a*b^n+c)/d) form of the unproven probable prime
11 1068 5(7^62668) (57×11^62668−7)/10
13 3194 C(5^23755)C (149×13^23756+79)/12
13 3195 8(0^32017)111 8×13^32020+183
16 2344 D0(B^17804) (3131×16^17804−11)/15
16 2345 D(B^32234) (206×16^32234−11)/15
16 2346 (4^72785)DD (4×16^72787+2291)/15
22 8003 B(K^22001)5 (251×22^22002−335)/21
30 2618 I(0^24608)D 18×30^24609+13

Can you run the strong tests for all these 8 PRPs with all prime bases b <= 61? (as you say, factordb only run the Fermat tests), also you were already run the strong Lucas test (with parameters (P, Q) defined by Selfridge's Method A) for all these numbers except the recently found PRP (4×16^72787+2291)/15, can you also run the strong Lucas test (with parameters (P, Q) defined by Selfridge's Method A) for (4×16^72787+2291)/15?

Originally Posted by charybdis

The ones that are factored to huge limits like that have special forms that restrict the possibilities for factors. For example, any prime dividing (17^1990523-1)/16 would have to be 1 mod 1990523.
Your number (57*11^62668-7)/10 has no such restrictions.

OK, for large numbers of the form (a*b^n+c)/d, only GFNs and GRUs (see my post in my blog) has such restrictions (however, GFNs b^(2^n)+1 with even b can be proven prime using N-1 test, and GRU in base 2 (Mersenne primes, of the form 2^n-1) can be proven prime using N+1 test, thus such trial factoring are only used for GFNs (b^(2^n)+1)/2 with odd b and GRUs (b^n-1)/(b-1) with b>2), thus, what is the usual trial factoring limit of such large PRPs? And can you do trial factoring for all these 8 PRPs to this limit?