|
Probable Prime Tests:
Trinomial Test
Define F(a,m,r) = am-ar-1
where
a,m,r in N
a > 1
m > 2
m>r>0
except F(2,m,m-1)
Conjecture: If aF=a modulo F then F is prime
If aF=a modulo F then
amF-arF-1 = 0 modulo F.
The roots satisfy: sum(rootsk) =
sum(rootsFk) modulo F for all k.
(symmetric pseudoprime)
For the specific example F(a,3,1) = a3-a-1
the roots satisfy: sum(rootsF) = 0 modulo F
(Perrin pseudoprime.)
What is the probability of a Perrin pseudoprime?
What is the probability that composite n satisfies
an=a modulo n? (Click here for answer)
How many tests are expected to refute the conjecture?
If you find a counterexample, please let me know.
8 Aug 2001: f=a3-a-1 tested for all a less than
1.4*10^9 with 15 Miller Rabin rounds.
17 Nov 2001: f=a3-a-1 proved for all a less than
10^8.
14 Mar 2002: f=a3+a-1 proved for all a less than
10^8.
20 Sep 2002: f=a3-a-1 tested for all a less than
10^10+2 with 5 Miller Rabin rounds (527,345,506 PrPs.)
01 Jan 2003: f=a3-a-1 tested for all a less than
10^11 with 5 Miller Rabin rounds (4,772,369,646 PrPs.)
01 Jan 2003: f=a3-a-1 tested for all a from
10^11 to 223,490,000,000 with 5 Miller Rabin rounds by
Michael Angel.
Quadratic Test
05 Jun 2005: f=a2-2 tested with 5 Miller-Rabin
rounds for a base-a PSP ; none found for all odd a from 3
to 10^11 (3,809,286,968 PRPs.)
26 Apr 2006: f=a2-2 further tested by Carlos
Eduardo to a=344,360,000,003 (12,480,999,468 PRPs.)
29 Mar 2015: tested with (L+2)^(f+1)==5 (mod f, L^2+1) for
odd a < 10^13 (320,120,182,301 PRPs.)
Unifying Test
For integers a>1, s>=0, all r>0, all t>0, odd
and irreducible {a^s\times\prod{(a^r-1)^t}}-1 is a-PRP,
except for the cases a^2-a-1 and a-2 and a-1 and -1.
FLT-type Conjecture
There are no non-zero integer solutions to
A*x^n+B*y^n=C*z^n where |A|+|B|+|C|<=n and x,y,z are
distinct.
5-Selfridge Q=-5 and Q=5 Lucas Test
N>5 and any P such that gcd(P,n)==1 and
KroneckerSymbol(P^2-4*5,N)==-1 and
KroneckerSymbol(P^2+4*5,N)==-1 and
L^(N+1)==5 (mod N, L^2-P*L+5) and L^(N+1)==-5 (mod N,
L^2-P*L-5).
6-Selfridge A-2 and A+2 Fermat-Lucas Test
N>5 coprime to 30, any A such that
JacobiSymbol((A-2)^2-4,N)==-1 and
JacobiSymbol((A+2)^2-4,N)==-1, test
(A-2)^N==A-2 (mod N) and (A+2)^N==A+2 (mod N) and
L^(N+1)==1 (mod N, L^2-(A-2)*L+1) and
L^(N+1)==1 (mod N, L^2-(A+2)*L+1).
Verified for N < 2*10^8 and for Carmichael numbers <
2^32.
6-Selfridge A-1 and A+1 Fermat-Lucas Test
N>5 coprime tp 210*A, any A such that
JacobiSymbol((A-1)^2-4,N)==-1 and
JacobiSymbol((A+1)^2-4,N)==-1, test
(A-1)^N==A-1 (mod N) and (A+1)^N==A+1 (mod N) and
L^(N+1)==1 (mod N, L^2-(A-1)*L+1) and
L^(N+1)==1 (mod N, L^2-(A+1)*L+1).
Verified for N < 2*10^8 and for Carmichael numbers <
2^32.
Derived 5-Selfridge A-2 and A+2 Fermat-Lucas
Test
N>5 coprime to 30, find A such that
JacobiSymbol((A-2)^2-4,N)==-1 and
JacobiSymbol((A+2)^2-4,N)==-1, test
4^N==4 (mod N)
L^(N+1)==1 (mod N, L^2-(A-2)*L+1) and
L^(N+1)==1 (mod N, L^2-(A+2)*L+1).
Counterexample: N=105809903; A=15164718
Derived 5-Selfridge A-1 and A+1 Fermat-Lucas
Test
N>5 coprime to 210*A find x such that
JacobiSymbol((A-1)^2-4,N)==-1 and
JacobiSymbol((A+1)^2-4,N)==-1, test
2^N==2 (mod N) and
L^(N+1)==1 (mod N, L^2-(A-1)*L+1) and
L^(N+1)==1 (mod N, L^2-(A+1)*L+1).
Counterexample: N=2499327041; A=20003797
1st 2.X-Selfridge Composite Test Algorithm
For N>5 coprime to 30, find the minimal integer x>0
where JacobiSymbol(x^2-4,N)==-1 and perform the probable
prime test
(x*L-3)^(N+1)==9-2*x^2 (mod N, L^2-x*L+1). Verified for N
< 2.481*10^12.
2nd 2.X-Selfridge Composite Test Algorithm
For N find minimal integer x>=0 where
KroneckerSymbol(x^2-4,N)==-1 and perform the probable prime
test (L+2)^(N+1)==2*x+5 (mod N, L^2-x*L+1). Verified for
odd N < 2^50.
L-2 and L+2 Test
N>1, for any integer x such that
KoneckerSymbol(x^2-4,N)==-1, test
(L-2)^(N+1)==5-2*x (mod N, L^2-x*L+1) and
(L+2)^(N+1)==5+2*x (mod N, L^2-x*L+1)
Verified for odd N < 10^8.
5-Selfridge Fermat-Euler-Lucas Test
N>5 coprime to 30, for any integer x:
gcd(x^3-x,N)==1 and JacobiSymbol(x^2-4,N)==-1, test
(x-2)^((N-1)/2)==JacobiSymbol(x-2,N) (mod N) (Euler)
and
(x+2)^((N-1)/2)==JacobiSymbol(x+2,N) (mod N) (Euler)
and
x^(N-1)==1 (mod N) (Fermat) and L^(N+1)==1 (mod N,
L^2-x*L+1) (Lucas)
Verified for N< 2.6*10^7 and Carmichael numbers <
2^32.
Quartic Test for L+x^2-2
N coprime to 210, any x indivisible by n
and JacobiSymbol(x^2-4,N)==-1 and
gcd((x^3-x)*(x^2-2)*(x^2-3),N)==1, test
(L+x^2-2)^N==-L^3+(x^2-2)*L+x^2-2 (mod N,
(L^2-x*L+1)*(L^2+x*L+1)).
Verified for N < 10^8.
Quartic Test for L+x+1
Odd N>5, for any x such that
N does not divide x and JacobiSymbol(x^2-4,N)==-1 and
gcd(x^2+x,N)==1, test
(L+x+1)^N==-L^3+(x^2-2)*L+x+1 (mod N,
(L^2-x*L+1)*(L^2+x*L+1)).
Verified for N < 10^8.
Quartic Test for L+x^2-1
Odd N>7, for any x such that
N does not divide x and JacobiSymbol(x^2-4,N)==-1 and
gcd(x^3-x,N)==1, test
(L+x^2-1)^N==-L^3+(x^2-2)*L+x^2-1 (mod N,
(L^2-x*L+1)*(L^2+x*L+1)).
Verified for N < 2.6*10^7. Counterexample:
N=62164241, x=2290208.
Quartic Test for L+x^2
Odd N>7, for any x such that
N does not divide x and JacobiSymbol(x^2-4,N)==-1 and
gcd(x^2-1,N)==1, test
(L+x^2)^N==-L^3+(x^2-2)*L+x^2 (mod N,
(L^2-x*L+1)*(L^2+x*L+1)).
Verified for N < 10^8.
x and 2*x or x^2 or x+2 Double Quadratic Test
N coprime to 30, for any x such that
JacobiSymbol(x^2-4,N)==-1 and gcd(x^3-x,N)==1, test
(L+x)^(N+1)==1+2*x^2 (mod N, L^2-x*L+1) and
(L+A)^(N+1)==1+A^2+x*A (mod N, L^2-x*L+1)
where A = 2*x or x^2 or x+2. Verified for N < 10^8.
L-1 and L+1 Test
N odd, for any a such that gcd(a,N)==1 and
JacobiSymbol((a+1)^2-4),N)==-1 and
JacobiSymbol((a-1)^2-4,N)==-1, test
(L-1)^(N+1)==1-a (Mod N, L^2-(a+1)*L+1) and
(L+1)^(N+1)==1+a (Mod N, L^2-(a-1)*L+1).
Verified for N < 2*10^8 and for Carmichael numbers <
2^32.
Quad Test
N coprime to 6, for any x, a and b such that
gcd(a*b*x,N)==1 and gcd(a^2-b^2,N)==1 and
JacobiSymbol(x^2-4,N)==-1, test
(L+a)^(N+1)==1+a^2+x*a and (L-a)^(N+1)==1+a^2-x*a and
(L+b)^(N+1)==1+b^2+x*b and (L-b)^(N+1)==1+b^2-x*b
all (mod N, L^2-x*L+1). Verified for N < 1.4*10^5.
Fermat+Lucas+Frobenius Test
N coprime to 30, for any x such that
gcd(x^3-x,N)==1 and JacobiSymbol(x^2-4,N)==-1 test
(2*x)^(N-1)==1 (mod N) and L^(N+1)==1 (mod N, L^2-x*L+1)
and
(L+x)^(N+1)==2*x^2+1 (mod N, L^2-x*L+1). Verified for N
< 10^8.
Double Fermat+Frobenius Test
N coprime to 30, for any x and y such that
gcd(x^3-x,N)==1 and JacobiSymbol(x^2-4,N)==-1 and
gcd(y^3-y,N)==1 and JacobiSymbol(y^2-4,N)==-1 and
gcd(x^2-y^2,n)==1 test
(2*x)^(N-1)==1 (mod N) and (L+x)^(N+1)==2*x^2+1 (mod N,
L^2-x*L+1) and
(2*y)^(N-1)==1 (mod N) and (L+y)^(N+1)==2*y^2+1 (mod N,
L^2-y*L+1) and
Verified for N < 10^8.
a^2+k Test
For n=a^2+k coprime to 6 and n>42 where k>0 and
a>1 and gcd(k^3-k,n*a)==1 find
x such that gcd(x,n)==1 and jacobiSymbol(x^2-4,n)==-1 and
test:
(L+a)^(n+1)==a^2+1+a*x (mod n, L^2-x*L+1) and
(L-a)^(n+1)==a^2+1-a*x (mod n, L^2-x*L+1). Verified for
n< 1.3*10^6.
Counterexample: [n, a, k, x]=[1432999, 641, 1022118,
381129]
Q only Test
For n coprime to 6 and n>5 find Q : gcd(Q+1,n)==1 and
jacobiSymbol(Q,n)==-1 and jacobiSymbol(Q-4,n)==1 and
jacobiSymbol(Q+4,n)==1 and test:
Q^((n-1)/2)==-1 (mod n) and x^((n+1)/2)==-1 (mod n,
x^2-(Q-2)*x+1) and
x^((n+1)/2)==-jacobiSymbol(-1,n) (mod n, x^2+(Q+2)*x+1).
Verified for n < 2.3*10^7
David's counterexamples: {[[1581223211, 1093877615],
[13078382623, 6926732822], [21577464971, 6280410804],
[33816027671, 12420727435], [56004757043, 39375517400],
[65963127163, 38771733269], [89249862731, 63319378549],
[92225622499, 91249250716], [97457318983, 76930744545]]}
2*x+1 and 2*x-1 Test
For odd n, find a such that jacobiSymbol(a^2-4,n)==-1 and
test
(2*x+1)^(n+1)==5+2*a (mod n, x^2-a*x+1) and
(2*x-1)^(n+1)==5-2*a (mod n, x^2-a*x+1).
Double Parameter Test
For n coprime to 30 find a and b:
jacobiSymbol(a^2-4,n)==-1 and gcd(b^2-4,n)==1 and
gcd(a^2-b^2,n)==1 and
gcd((a^3-a)*(b^3-b),n)==1 and gcd(a^3-a,b^3-b)==6 and
test:
(b*x+1)^(n+1)==1+b^2+a*b (mod n, x^2-a*x+1) and
(b*x-1)^(n+1)==1+b^2-a*b (mod n, x^2-a*x+1)
David's counterexamples:
{[[107752185411149, 83669262602538, 19154350998482],
[159132028928489, 38034692864164, 56837927663062],
[2544844174968929, 2391864938130562, 575637140842943],
[1484926074920009, 1014048410273000, 421042641324018],
[2333564831617769, 191389787226297, 210732564557270],
[11149098312734969, 3776761935674103,
1265100831985174],
[8353109377649009, 2445829862238038, 3451336874803033],
[4627936813857689, 2353076244593330, 2940176822193232],
[5099517882159749, 3276100765569083, 2684765653980526],
[7308466463154149, 6633660182802507, 5895989769974006]]}
x-Q and x+Q Test
n coprime to 6, find Q: gcd(Q^2-1,n)==1 and
jacobiSymbol(1-4*Q,n)==-1 and test
(x-Q)^(n+1)==Q^2 and (x+Q)^(n+1)==(Q+1)^2-1 both (mod n,
x^2-x+Q).
Verified for n < 1.8*10^7.
5 Selfridge Q Test
n coprime to 6, find Q: gcd(Q^2-1,n)==1 and
jacobiSymbol(1-4*Q,n)==-1 and
jacobiSymbol(Q,n)==-1 and test Q^((n-1)/2)==-1 (mod n)
and x^((n+1)/2)==-1 (mod n, x^2-(1-2*Q)/Q*x+1) and
x^((n+1)/2)==jacobiSymbol(2+Q,n) (mod n,
x^2-(5-2*Q)/(2+Q)*x+1).
Verified for n < 5*10^6. Counterexample: n=5073799
and Q=2484110.
David's counterexamples: {[[76537243, 62685438],
[156524443, 1148764], [486819343, 352255858], [724361923,
38713830], [1001493799, 859390320], [7445895763,
916298043], [15728383999, 4890179599]]}
Complex test
For n, test (2+x*I)^n == 2+x*I^((n+1)/2) (mod n, x^2+I)
Claim: pseudoprimes exist only for n == 1 mod 8.
Further complex test
To test n, with integer k such that gcd(k,n)==1,
test (2+x)^n == 2+x^(n%(2*k)) (mod n, x^k+1).
Claim: pseudoprimes exist only for n == 1 mod 2*k.
Base x+1 test
To test n, with integer k (>3) such that gcd(k,n)==1
and
n%(2*k)!=1 and n%(2*k)!=2*k-1 test the following:
(x+1)^n == x^(n%(2*k))+1 (mod n, x^k+1)
2.X-Selfridge Composite Test Algorithm Revisited
For N find integer 0<=x<=ceil(N^0.25) where
KroneckerSymbol(x^2-4,N)==-1
and perform the probable prime test (L+2)^(N+1)==2*x+5 (mod
N, L^2-x*L+1).
Verified for odd N < 10^12.
8 Selfridge test
For odd N>6 find a such that gcd(a^3+a,N)==1 and
JacobiSymbol((a*I)^2-4,N)==-1
and perform the probable prime test:
(x+1)^(N+1)==2+a*I mod(N, x^2-a*I*x+1) if N==1 mod 4;
(x+1)^(N+1)==2-a*I*x mod(N, x^2-a*I*x+1) if N==3 mod 4
Verified for N < 10^6. (Note: if a is small this test is
8 selfridges.)
Counterexample: [n,a]=[1037623, 134383]
2 Selfridge Baillie-PSW test
For non-square odd N find minimal a>2 such that
JacobiSymbol(a^2-4,N)==-1
and perform the probable prime test:
(2*x)^((N+1)/2)==JacobiSymbol(2*(a+2),N)*2 mod(N,
x^2-a*x+1)
Verified for N < 2^64
6^r test
For non-square N with gcd(210,N)==1 and let b=6 and a=6^r
(any r),
where gcd(a^3-a,N)==1 and JacobiSymbol(a^2-4,N)==-1. Then
test:
(b*x)^((N+1)/2)==b*JacobiSymbol(b*(a+2),N) (mod N,
x^2-a*x+1)
Verified for N < 1.5*10^14
A Quadratic Frobenius Composite Test with One Free
Parameter
Please see this
paper.
2^r tests
For non-square n find a=2^r where gcd(6,n)==1,
kronecker(a^2+-4,n)==-1,
gcd(a^2+-1,n)==1 and gcd(a^2+-2,n)==1 and then test
(a^2+-4)^((n-1)/2) == -1 (Mod n) and :-
if "+" case: (2*x)^(n+1) == -4 (Mod n, x^2-a*x-1)
if "-" case: (2*x)^((n+1)/2) == 2*kronecker(2*(a+2),n) (Mod
n, x^2-a*x+1)
Both verified for n < 5*10^12.
Two Parameter test
For any non-square n find a=2^r and b:
b%n!=0 and gcd(a^2-b,n)==1 and gcd(a^2-2*b,n)==1
and kronecker(a^2-4*b,n)==-1 and test:
(a^2-4*b)^((n-1)/2)==-1 (mod n) and
(2*x)^(n+1)==4*b (mod n, x^2-a*x+b)
Verified for n <= 4502485
Euler-Frobenius Test
For non-square n find b such that Jacobi(1-b,n)==-1
and gcd(4-b,n)==1 and gcd(4-2*b,n)==-1 and then test:
(1-b)^((n-1)/2)==-1 (mod n)
x^(n+1)==b (mod n, x^2-2*x+b)
Verified for n < 10^6
[n,b] = [79786523, 2982537] is a counterexample
Euler-Frobenius 2^r Version
For non-square odd n find a=2^r such that
gcd(a-2,n)==1 and gcd(a-4,n)==1 and
kronecker(1-a,n)==-1
and test (1-a)^((n-1)/2)==-1 (mod n) and
x^(n+1)==a (mod n, x^2-2*x+a)
Verified for n < 9*10^7
Euler-Frobenius 2^r Variant
For non-square odd n find a=2^r such that
gcd(a-2,n)==1 and gcd(a-4,n)==1 and
kronecker(1-a,n)==-1
and test (1-a)^((n-1)/2)==-1 (mod n) and
2^(n-1)==1 (mod n) and
x^(n+1)==1 (mod n, x^2-(4/a-2)*x+1)
Verified for n < 10^13
x^2-y Test
For odd non-square n find any y=2^r such that
gcd(r-1,n-1)==1 and kronecker(y,n)==-1 and test
2^(n-1)==1 (mod n) and
y^((n-1)/2)==-1 (mod n) and
(x+1)^(n+1)==-y+1 (mod n, x^2-y)
Verified for n < 10^12
Simple Euler-Frobenius Test
For odd n find a < sqrt(n) such that jacobi(a,n)==-1
and test a^((n-1)/2)==-1 (mod n) and
(x+1)^n==-x+1 (mod n, x^2-a)
Reduced Domain Test
Paper
(£100 Prize)
Lucas(n,12^r,-12) Test
For any n and r with gcd(6,n) and
kronecker(144^r+48,n)==-1
test x^(n+1)==-12 (mod n, x^2-12^r*x-12).
Lucas(n,3^r,-3) Test
For any n with gcd(6,n)==1 and kronecker(9^r+12,n)==-1 and
gcd(r-1,n-1)
test x^(n+1)==-3 (mod n, x^2-3^r*x-3).
Paper.
Lucas(n,2^r,-2) Test
For any n with gcd(6,n)==1 and kronecker(9^r+8,n)==-1 and
gcd(2*r-1,n-1)
test x^(n+1)==-2 (mod n, x^2-2^r*x-2).
TPPPE test
{ kill(x);TPPPE(n)=my(k=2,X=x);
while(X==x,k++;X=Mod(Mod(x,n),x^k-x-1)^n);
gcd(polcoef(lift(lift(X)),k-1),n)==1&&X^k-X-1==0; }
Cubic Test
{kill(x);TPPPC(n)=my(k=0,X=x);
while(X==x||gcd(a,n)!=1||gcd(4*a-27,n)!=1||gcd(2*a-1,n)!=1||Mod(n,a)^((a-1)/gcd(a-1,3))==1,k++;a=7+k*(k-1);X=Mod(Mod(x,n),x^3-a*x-a)^n);
gcd(polcoef(lift(lift(X)),0),n)==1&&X^3-a*X-a==0;}
Paper
here
General Test
Paper here
|
