Divertimento -- Four Lucas Tests

[paulunderwood]

Based on the Frobenius tests over:

x^2-a*x+a==0 with kronecker(a^2-4*a,n)==-1
x^2-a*x-a==0 with kronecker(a^2+4*a,n)==-1

which can be transformed into

a^((n-1)/2)==kronecker(a,n) (mod n)
x^((n+1)/2)==kronecker(a,n) (mod n, x^2-(a-2)*x+1)
x^((n+1)/2)==kronecker(-a,n) (mod n, x^2+(a+2)*x+1)

I have tested up to n<10^6 with gcd(a^2-1,n)==1 without finding a counterexample pseudoprime.

[paulunderwood]

• kronecker(a^2-4*a,n)==-1
• kronecker(a^2+4*a,n)==-1
• a^((n-1)/2)==kronecker(a,n) (mod n)
• x^((n+1)/2)==kronecker(a,n) (mod n, x^2-(a-2)*x+1)
• x^((n+1)/2)==kronecker(-a,n) (mod n, x^2+(a+2)*x+1)
• gcd(a^2-1,n)==1

Those n below 4*10^6 requiring gcd(a^2-1,n) are so few I can list them here:

[5777, 1854, 5777]                                                            
[17261, 420, 421]                                                             
[17261, 843, 421]
[17261, 3790, 421]
[17261, 5053, 421]
[113573, 48910, 113573]
[120581, 2942, 2941]
[120581, 5881, 2941]
[120581, 21453, 2941]
[120581, 26468, 2941]
[120581, 30276, 2941]
[120581, 35291, 2941]
[120581, 50863, 2941]
[120581, 59686, 2941]
[1033997, 317611, 1033997]
[1729331, 422433, 13201]
[1842581, 269647, 44941]
[1842581, 449411, 44941]
[1842581, 539291, 44941]
[1842581, 584232, 44941]
[3774377, 1256294, 3774377]
[3900797, 1544479, 3900797]

[paulunderwood]

Let's turn the above into Pari/GP code:

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

In the example above, I did not trivially test tst(n,1).

If I do test tst(n,1) and a gcd(a^2-1,n) is required I can loop over the rest of the a's (up to (n-1)/2 because of symmetry) and check for gcd(a^2-1,n).

What I see for such a is that GCD(gcd(a_i^2-1,n),gcd(a_j^2-1,n)) is always greater than 1 (so far). Furthermore, all gcd(a^2-1,n) have so far been 1 mod 4.

[paulunderwood]

tst(10627*148793, 479362525) fools!

[paulunderwood]

With my observations about GCDs, I now have a new quest to fool:

tstab(n,a,b)=tst(n,a)&&tst(n,b)&&gcd(a^2-b^2,n)==1;

[paulunderwood]

I have not yet found a counterexample to the previous test.

I now propose a more general test:

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

or

{tst1(n,P,Q)=kronecker(P^2-4*Q,n)==-1&&Mod(Mod(x,n),x^-P*x+Q)^(n+1)==Q;}

{tst2(n,P,Q)=tst1(n,P,Q)&&tst1(n,P,-Q);}

{tst4(n,P,Q_i,Q_j)=tst2(n,P,Q_i)&&tst2(n,P,Q_j)&&gcd(Q_i^2-Q_j^2,n)==1;}

[paulunderwood]

Originally Posted by paulunderwood

I
{tst1(n,P,Q)=kronecker(P^2-4*Q,n)==-1&&Mod(Mod(x,n),x^-P*x+Q)^(n+1)==Q;}

{tst2(n,P,Q)=tst1(n,P,Q)&&tst1(n,P,-Q);}

{tst4(n,P,Q_i,Q_j)=tst2(n,P,Q_i)&&tst2(n,P,Q_j)&&gcd(Q_i^2-Q_j^2,n)==1;}

tst4(9809, 577, 27, 171) fails, but if I add the remedy gcd(P,n)==1 all is good.

[paulunderwood]

What is wrong with this argument?

Let:
x^2-P*x+Q=0
y^2-P*y-Q=0
s^2-P*s+R=0
t^2-P*t-R=0

Then:
x^2+y^2-P*(x+y)=0
s^2+t^2-P*(s+t)=0

Or
P=(x^2+y^2)/(x+y)=(s^2+t^2)/(s+t)

That is since gcd(P,n)=1:
(x^2+y^2)*(s+t)=(s^2+t^2)*(x+y)

And the the following must be true since gcd(x^2+y^2, x+y) is either 1 or 2:
x+y=s+t

And so:
x^2+y^2=(x+y)^2-2*x*y=s^2+t^2=(s+t)^2-2*s*t

So that:x*y=s*t

If a prime p divides x it must divide s or t

Wlog then:
x^2-P*x+Q==x^2-P*x+R

I.e:
p divides Q-R, but a condition is that gcd(Q^2-R^2,n)=1.

QED

[paulunderwood]

Well that was a lot of BS maths.

Originally Posted by paulunderwood

Let:
x^2-P*x+Q=0
y^2-P*y-Q=0
s^2-P*s+R=0
t^2-P*t-R=0

I have tested (with strong kroneckers and gcd(P,n)==1 and gcd(Q^2-R^2,n)==1) for Q=1 up to n < 10^6 and for all Q for n up to 1.8*10^4 with Pari/GP. When I get some free time I will convert to my own C library

[paulunderwood]

[n,P,Q,R]=[1162349, 2335, 1, 2234] fools tst4().

I have now revised the test; I insist that gcd(Q^2-1,n)==1 and gcd(R^2-1,n)==1 as well.

{tst1(n,P,Q)=kronecker(P^2-4*Q,n)==-1&&gcd(Q^2-1,n)==1&&
Mod(Mod(x,n),x^-P*x+Q)^(n+1)==Q;}

{tst2(n,P,Q)=tst1(n,P,Q)&&tst1(n,P,-Q);}

{tst4(n,P,Q,Rj)=tst2(n,P,Q)&&tst2(n,P,R)&&gcd(Q^2-R^2,n)==1;}

[paulunderwood]

Here I test over

x^2-x+2^r where kronecker(1-4*2^r,n)==-1
x^2-x-2^r where kronecker(1+4*2^r,n)==-1

If r is even this is the same as:

2^(n-1)==1 (mod n)
x^((n+1)/2)==1 (mod n, x^2-(1/2^r-2)*x+1)
x^((n+1)/2)==kronecker(-1,n) (mod n, x^2+(1/2^r+2)*x+1)

if r is odd:

2^((n-1)/2)==kronecker(2,n) (mod n)
x^((n+1)/2)==kronecker(2,n) (mod n, x^2-(1/2^r-2)*x+1)
x^((n+1)/2)==kronecker(-2,n) (mod n, x^2+(1/2^r+2)*x+1)

If r==0 we have:

x^((n+1)/2)==kronecker(-1,n) (mod n, x^2+3*x+1) where kronecker(5,n)==-1 and kronecker(-3,n)==-1.

and this has pseudoprimes: [5777, ... ] and consequently checking gcd(2^(2*r)-1,n)==1 is wise.

To make the Lucas PRP tests more efficient we can instead calculate over x^2-x+-1/2^r and use small r.