mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > sweety439

Reply
 
Thread Tools
Old 2022-06-24, 13:08   #1
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72×73 Posts
Default 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
sweety439 is online now   Reply With Quote
Old 2022-06-24, 13:28   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

109C16 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2022-06-24, 13:52   #3
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72×73 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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?
sweety439 is online now   Reply With Quote
Old 2022-06-24, 13:58   #4
mathwiz
 
Mar 2019

5·59 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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.
mathwiz is offline   Reply With Quote
Old 2022-06-24, 14:02   #5
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72·73 Posts
Default

Quote:
Originally Posted by mathwiz View Post
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.
sweety439 is online now   Reply With Quote
Old 2022-06-24, 14:04   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22·1,063 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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
paulunderwood is offline   Reply With Quote
Old 2022-07-06, 15:42   #7
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

357710 Posts
Default

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)
sweety439 is online now   Reply With Quote
Old 2022-07-06, 17:12   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22·1,063 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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
paulunderwood is offline   Reply With Quote
Old 2022-07-06, 20:30   #9
charybdis
 
charybdis's Avatar
 
Apr 2020

5·163 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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.
charybdis is offline   Reply With Quote
Old 2022-07-07, 01:36   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22·1,063 Posts
Default

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.
paulunderwood is offline   Reply With Quote
Old 2022-07-07, 03:44   #11
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72×73 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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 View Post
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?
sweety439 is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucas Primality Test a1call Miscellaneous Math 5 2019-03-21 16:36
Lucas Primality Test in Pari GP a1call PARI/GP 11 2018-08-26 09:39
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
The Lucas Primality Test Mr. P-1 Math 6 2009-05-31 20:03
Lucas-Lehmer primality test CMOSMIKE Math 5 2002-09-06 18:46

All times are UTC. The time now is 21:50.


Tue Aug 16 21:50:33 UTC 2022 up 40 days, 16:37, 1 user, load averages: 1.90, 1.33, 1.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔