20220624, 13:08  #1 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
7^{2}×73 Posts 
Can PFGW run the strong Lucas primality test?
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:
Code:
b index of this minimal prime in base b (assuming the primality of all probable primes in base b) baseb 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 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? Last fiddled with by sweety439 on 20220624 at 13:11 
20220624, 13:28  #2 
Sep 2002
Database er0rr
109C_{16} Posts 
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
Last fiddled with by paulunderwood on 20220624 at 13:28 
20220624, 13:52  #3  
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
7^{2}×73 Posts 
Quote:


20220624, 13:58  #4 
Mar 2019
5·59 Posts 

20220624, 14:02  #5 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
7^{2}·73 Posts 

20220624, 14:04  #6  
Sep 2002
Database er0rr
2^{2}·1,063 Posts 
Quote:
Here are the results as they come in: Code:
echo 'print((57*11^626687)/10)'  gp q  ./gmp_millerrabin_stronglucas 0 1 Passed strong Lucas PRP test over x^24*x+1. echo 'print((149*13^23756+79)/12)'  gp q  ./gmp_millerrabin_stronglucas 0 1 Passed strong Lucas PRP test over x^29*x+1. echo 'print(8*13^32020+183)'  gp q  ./gmp_millerrabin_stronglucas 0 1 Passed strong Lucas PRP test over x^25*x+1. echo 'print((3131*16^1780411)/15)'  gp q  ./gmp_millerrabin_stronglucas 0 1 Passed strong Lucas PRP test over x^23*x+1. echo 'print((206*16^3223411)/15)'  gp q  ./gmp_millerrabin_stronglucas 0 1 Passed strong Lucas PRP test over x^23*x+1. echo 'print((251*22^22002335)/21)'  gp q  ./gmp_millerrabin_stronglucas 0 1 Passed strong Lucas PRP test over x^24*x+1. echo 'print(18*30^24609+13)'  gp q  ./gmp_millerrabin_stronglucas 0 1 Passed strong Lucas PRP test over x^23*x+1. Last fiddled with by paulunderwood on 20220624 at 15:53 

20220706, 15:42  #7 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
3577_{10} Posts 
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: Code:
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^626687)/10 59392/3091341693 (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) 
20220706, 17:12  #8  
Sep 2002
Database er0rr
2^{2}·1,063 Posts 
Quote:
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. Last fiddled with by paulunderwood on 20220706 at 17:13 

20220706, 20:30  #9  
Apr 2020
5·163 Posts 
Quote:
Your number (57*11^626687)/10 has no such restrictions. 

20220707, 01:36  #10  
Sep 2002
Database er0rr
2^{2}·1,063 Posts 
As promised:
Quote:


20220707, 03:44  #11  
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
7^{2}×73 Posts 
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 Code:
b index of this minimal prime in base b (assuming the primality of all probable primes in base b) baseb 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 Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Lucas Primality Test  a1call  Miscellaneous Math  5  20190321 16:36 
Lucas Primality Test in Pari GP  a1call  PARI/GP  11  20180826 09:39 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
The Lucas Primality Test  Mr. P1  Math  6  20090531 20:03 
LucasLehmer primality test  CMOSMIKE  Math  5  20020906 18:46 