mersenneforum.org Can PFGW run the strong Lucas primality test?
 Register FAQ Search Today's Posts Mark Forums Read

 2022-06-24, 13:08 #1 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 3,467 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) 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? Last fiddled with by sweety439 on 2022-06-24 at 13:11
 2022-06-24, 13:28 #2 paulunderwood     Sep 2002 Database er0rr 23×17×31 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 2022-06-24 at 13:28
2022-06-24, 13:52   #3
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

3,467 Posts

Quote:
 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?

2022-06-24, 13:58   #4
mathwiz

Mar 2019

281 Posts

Quote:
 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.

2022-06-24, 14:02   #5
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

D8B16 Posts

Quote:
 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.

2022-06-24, 14:04   #6
paulunderwood

Sep 2002
Database er0rr

23×17×31 Posts

Quote:
 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:

Code:
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

Last fiddled with by paulunderwood on 2022-06-24 at 15:53

 2022-07-06, 15:42 #7 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 3,467 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^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)
2022-07-06, 17:12   #8
paulunderwood

Sep 2002
Database er0rr

10000011110002 Posts

Quote:
 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: 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^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.

Last fiddled with by paulunderwood on 2022-07-06 at 17:13

2022-07-06, 20:30   #9
charybdis

Apr 2020

24·47 Posts

Quote:
 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.

2022-07-07, 01:36   #10
paulunderwood

Sep 2002
Database er0rr

23·17·31 Posts

As promised:

Quote:
 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.

2022-07-07, 03:44   #11
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

3,467 Posts

Quote:
 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

Code:
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?

Quote:
 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 5 2019-03-21 16:36 a1call PARI/GP 11 2018-08-26 09:39 Trilo Miscellaneous Math 25 2018-03-11 23:20 Mr. P-1 Math 6 2009-05-31 20:03 CMOSMIKE Math 5 2002-09-06 18:46

All times are UTC. The time now is 14:35.

Thu Jul 7 14:35:07 UTC 2022 up 9:22, 0 users, load averages: 0.92, 1.15, 1.22