View Single Post
Old 2021-05-07, 10:24   #1
paulunderwood's Avatar
Sep 2002
Database er0rr

72468 Posts
Cool Divertimento -- Four Lucas Tests

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.

Last fiddled with by paulunderwood on 2021-05-15 at 04:09
paulunderwood is online now   Reply With Quote