A promising primality test is Sergei Khashin’s Frobenius test, as described in a 2013 arxiv preprint of his, Counterexamples for Frobenius primality test, available from the url https://arxiv.org/abs/1307.7920. The idea of the Frobenius test originated with Jon Grantham, see for example his 1998 article A Probable Prime Test With High Confidence available from the url https://arxiv.org/abs/1903.06823. For an odd integer n>1 that is not a perfect square, one considers quadratic non-residues c of n and the ring extension of Z_n given by adjoining a square root of c (mod n) to Z_n thus obtaining the ring Z_n[sqrt(c)]. When n is prime, the ring Z_n[sqrt(c)] is isomorphic to the finite field with n^2 elements. In that case (denoting n by p) the map phi: F_{p^2}->F_{p^2} x |-> x^p is an important object called the Frobenius automorphism (see eg Wikipedia at the url https://en.wikipedia.org/wiki/Frobenius_endomorphism ). Basic Galois Theory then shows that phi(1+sqrt(c)) = phi(1) + phi(sqrt(c)) = 1^p + (sqrt(c))^p = 1 – sqrt(c) , given that -sqrt(c) is a conjugate to sqrt(c) . So one has the congruence
(1+sqrt(c))^p == 1-sqrt(c) if p is prime. One can use this fact to conduct a primality test on n. Given n as above, one considers in succession the odd non-square positive integers c starting with 3 and identifies the smallest such c that verifies Jacobi(c,n)=-1. The Jacobi symbol Jacobi(c,n) contains information about the quadratic residuosity or non-residuosity of c modulo n. If Jacobi(c,n) = -1, then c is not a square in the ring Z_n. However, if Jacobi(c,n)=1 it can still happen that c is not a square in Z_n (cf. Wikipedia at the url https://en.wikipedia.org/wiki/Jacobi_symbol ). Having found the smallest c with Jacobi(c,n)=-1, one checks whether the congruence: (1+sqrt(c))^n == 1-sqrt(c) (modulo n) holds. If it does not, then n is composite, and if it does then n is declared a probable prime.
Khashin in his 2013 preprint also requires c to be a prime number, although in my experience this seems to change very little while disallowing some small composite numbers such as 15, 21, 27, 33, and so on. Starting with c=3 has the advantage that a base 2 Fermat test is done for free while conducting the Frobenius test: If n passes the c=3 Frobenius test, this means that (1+sqrt(3))^n == 1-sqrt(3). Upon taking conjugates, one obtains (1-sqrt(3))^n == 1+sqrt(3). Combining the last two congruences: (-2)^n == -2 (mod n). One can divide both sides by (-1)^n== -1, and then by 2 to obtain: 2^(n-1) == 1 (mod n), and we see that n would pass the Fermat base 2 test. It follows that if n fails the Fermat base 2 test, it will fail the Frobenius test with parameter c=3, at least if Jacobi(3,n)=-1. If Jacobi(3,n)=1, it may be advisable to conduct a preliminary base 2 Fermat test, as it’s fast and eliminates a large percentage of composites. Also, the numbers that are composite and pass the Fermat base 2 test, generally known as base 2 pseudoprimes, are easily available, including tables from Jan Feitsma at the url http://www.cecm.sfu.ca/Pseudoprimes/ .
I downloaded Feitsma’s table of Fermat base 2 pseudoprimes below 2^64 and used it to evaluate the Frobenius test described above. Numbers n in the table were read in succession and, when Jacobi(3,n)=-1 was true, the Frobenius test with c=3 was done. This took about two hours, and no false positives were found. (composites passing as primes). Consistent with the above and to further challenge the Frobenius test, I’m presently skipping the parameter value c=3 and starting at c=5, otherwise doing as above on pseudoprimes to base 2. Currently, about 60% of the job has been completed with no false positives, with the largest c used being 139. I plan to test many more smaller bases, say in the range 7-315, on the base 2 pseudoprimes below 2^50 or about 10^15.
In addition, I’ve been computing statistics of average false positive rates for the test numbers n up to some limit x, where the parameter c is allowed to range from 3 to n/2. These show that, in the tested range, the false positive rate decreases significantly as the upper limit increases, with a false positive rate least-squares fit f(x)=C x^(-1.24). Heuristically, this suggests that in the case of false positives, log(c)/log(n) may be bounded below, ie there could exist a B>0 such that c > n^B for all “liars” c for the Frobenius test.
