Singleton / Complex / General Tests -- Trinomiality Preservation

[paulunderwood]

Singleton Case - 2 Selfridges
If n = 3 mod 4 then (x+2)^(n+1)==5 (mod n, x^2+1), which has been verified to 2^50.

Complex Case - Double Test - Two Parameters
Only for n==3 mod 4.
Let CT(t,n) = gcd(t^3-t,n)==1 && Mod(t,n)^(n-1)==1 && Mod(Mod(x+t),x^2+1)^(n+1)==t^2+1;
and CT2(t,t2,n) = CT(t) && CT(t2,n) && gcd((t*t2)^2-1,n)==1 && gcd(t^2-t2^2,n)==1;
This test is 2*(1+3) Selfridges.

General Case - Double Test - Three Parameters
Let {GT(t,a,n) = kronecker(a^2-4,n)==1 && gcd((t^3-t)*(a+2*t)*(a-2*t)*(a*t-2)*(a*t+2),n)==1 &&
Mod(t,n)^(n-1)==1 && Mod(Mod(x+t,n),x^2-a*x+1)^(n+1)=(t+a)*t+1;}
and GT2(t,t2,a,n) = GT(t,a) && GT(t2,a) && gcd((t*t2)^2-1,n)==1 && gcd(t^2-t2^2,n)==1;
This is also 2*(1+3) Selfridges,

[paulunderwood]

[Side note: gcd(t^3-t,n)==1 might not be required in the above tests.]

I'll try to convey my thinking here.

Let A be the matrix [a,-1;1,0] and its characteristic function be X(A).

Note that the probable prime tests Fermat-t is the same as Fermat-(-t), Fermat(1/t) and Fermat-(-1/t). So let T be one of these,

Essentially I am taking Fermat-T and testing (A+T)^(n+1) over X(A) is the determinant of (A+T) i.e 1+(a+T)*T.

The later is the same as as taking a n+1 power x over x^2-(a+2*T)*x+(a+T)*T+1. It is important to preserve trinomiality of this and not let it degenerate into an Euler PRP test of the determinant. So I take gcd(a+2*T,n)==1 (for all cases of T).

Finally, I observe that two such Fermat+Frobenius tests and the required GCDs seems sufficient (not to fool).

[paulunderwood]

Originally Posted by paulunderwood

[Side note: gcd(t^3-t,n)==1 might not be required in the above tests.]

With the counterexample [n, a, t, t2, gcd((t*t2)^2-1,n), gcd(t^2-t2^2,n)] = [5983, 5514, 5512, 5982, 1, 1] it is advisable to take the above GCD giving a non-degenerative Fermat PRP-t test. For this "counterexample" gcd(5982^2-1,5983) = 5983.

[paulunderwood]

If t = 2 and t2 = 3 then the above general test is:

{
tst_2_3(n,a)=
kronecker(a^2-4,n)==-1&&
gcd(210,n)==1&&
gcd(a+4,n)==1&&
gcd(a+6,n)==1&&
Mod(2,n)^(n-1)==1&&
Mod(3,n)^(n-1)==1&&
Mod(Mod(x+2,n),x^2-a*x+1)^(n+1)==5+2*a&&
Mod(Mod(x+3,n),x^2-a*x+1)^(n+1)==10+3*a;
}

I am testing the "general test" every way I can think of. Can you find a counterexample?



Dropping a Selfridge can be done by letting t = 2 and t2 = 4 such that the test is

{
tst_2_4(n,a)=
kronecker(a^2-4,n)==-1&&
gcd(210,n)==1&&
gcd(a+4,n)==1&&
gcd(a+8,n)==1&&
Mod(2,n)^(n-1)==1&&
Mod(Mod(x+2,n),x^2-a*x+1)^(n+1)==5+2*a&&
Mod(Mod(x+4,n),x^2-a*x+1)^(n+1)==17+4*a;
}

Furthermore, the Frobenius tests can each be done in 2 Selfridges (by my published method), making the tst_2_4(n,a) cost 1+2+2 Selfridges.

[paulunderwood]

For the 1+2+2 Selfridges tst_2_4(n,a) it will be nice to write some GMP code against Feitsma's list of Fermat 2-PRPs n < 2^64 -- I will have to see how far I can get.

<placeholder for code>

[paulunderwood]

[n, a, t, t2]=[8473, 2043, 140, 1252] gives a counterexample, but fear not, I have added gcd(a+t,n)==1 (to GT()) to stop degeneration of the determinant t*(t+a)+1 into unity, and gcd(t*a+1,n)==1 for a possibility of T.

Fixing the last practical test, tst_2_4 is now:

{
tst_2_4(n,a)=
kronecker(a^2-4,n)==-1&&
gcd(210,n)==1&&
gcd(a+2,n)==1&&gcd(2*a+1,n)==1&&
gcd(a+4,n)==1&&gcd(4*a+1,n)==1&&
gcd(a+8,n)==1&&gcd(8*a+1,n)==1&&
Mod(2,n)^(n-1)==1&&
Mod(Mod(x+2,n),x^2-a*x+1)^(n+1)==2*a+5&&
Mod(Mod(x+4,n),x^2-a*x+1)^(n+1)==4*a+17;
}

[paulunderwood]

[n, t, t2]=[415681338623, 2106331569, 9028142873] is a counterexample to the complex test (CT above). Hmm. I will try to find one for which gcd(a^3-a,n)==1.

Well that did not take long to fool: [n, a, t, t2]=[166827943, 3, 26368204, 65867518].

Next up, just test [n,a,2,4]. This is however 2 sub-tests with one parameter

[paulunderwood]

Let the matrix A=[a,-1;1,0] with kronecker(a^2-4,n)==-1 && gcd(a^3-a,n)==1.

The latest test (LT) is A^n+t^n == (A+t)^n mod n.

with the following GCDs:-
gcd(t^3-t,n)==1
gcd(a+t,n)==1
gcd(a+2*t,n)==1
gcd(a*t+1,n)==1

[paulunderwood]

{tst(n,a)=gcd(a^3-a,n)==1&&kronecker(a^2-4,n)==-1&&Mod(Mod(x,n),x^2-a*x+1)^(n+1)==1;}

{tst1(n,a,t)=gcd(t^2-1,n)==1&&gcd(a+t,n)==1&&gcd(a*t+1,n)==1&&
Mod(t,n)^(n-1)==1&&Mod(Mod(x+t,n),x^2-a*x+1)^(n+1)==(a+t)*t+1;}

{tst2(n,a,t,t2)=gcd(t^2-t2^2,n)==1&&gcd((t*t2)^2-1,n)==1&&
tst(n,a)&&tst1(n,a,t)&&tst1(n,a,t2);}

This tst2 looks pretty sound. Can any one fool it?

It is based on A^n+t^n == (A+t)^n mod n and A^n+t2^n == (A+t2)^n mod n with the incumbent GCDs

Edit: I added in gcd(a^3-a,n)==1. Otherwise tst will be trivially degenerate into cyclotomy and the counterexample in post #7 would fool it!

[paulunderwood]

Consider the semi-prime n=p*q. From A^n+t^n == (A+t)^n mod n we have both:

A^p+t^p == (A+t)^p mod q
A^q+t^q == (A+t)^q mod p

So in trying to construct a counterexample we might do:

p = k*(q-1)+1
q = l*(p-1)+1

Making the substitution we get:

p = k*l*(p-1)+1 which implies k*l == 1 which means p = q.

If this construction method does not work, can it be extended to more prime factors?

Why do I get the counterexample [n, a, t, t2]=[415681338623, 0, 2106331569, 9028142873] when gcd(a^3-a,n)>1?

Why are two sub-tests needed, one for t and one for t2?

[Nick]

Originally Posted by paulunderwood

Consider the semi-prime n=p*q. From A^n+t^n == (A+t)^n mod n we have ...

For that formula, you need n to be prime not just semi-prime (or I have misunderstood what you mean!)