I’m continuing my evaluation of Khashin’s Frobenius Primality Test from his 2013 preprint at the URL https://arxiv.org/abs/1307.7920. To make it easier to assess the accuracy of this test, I assume that in a first round, one conducts a Fermat base 2 test, which will detect all composites that are not base 2 pseudoprimes. In round 2, one conducts the Khashin Frobenius test. For an odd integer n>1 that is not a perfect square, one finds the smallest odd c>1 such that Jacobi(c,n)= -1. One checks whether the following congruence holds: (1+sqrt(c))^n == 1-sqrt(c) (mod n). If it does not, then n is composite. If it does, then n is declared a probable prime. In his preprint, Khashin requires c to be an odd prime, but in my tests I’ve found that it seems to be enough to require that c be odd. It’s enough to evaluate the two-round test on Fermat base 2 pseudoprimes, which are available in files from Jan Feitsma for the pseudoprimes below 2^64 from http://www.cecm.sfu.ca/Pseudoprimes/. I implemented the two-round Khashin Frobenius test in C, and tested the pseudoprimes to 2^64 using this test. No composites passed this two-round test.
In previous testing, I found the composite n=589 with c = 317 where Jacobi(c,n)=-1 and (1+sqrt(c))^n == 1-sqrt(c) (mod n). c=317 is the smallest value for which I know of a composite n that passes the Frobenius test for c, assuming Jacobi(c,n)=-1. So I’m currently testing the admissible c (ie c odd with Jacobi(c,n)=-1) in the range 3 to 335. Currently I’ve passed n=2.6e+17 with no c giving a false positive. The testing of the admissible cs from 3 to 335 up to n=2^64 has concluded. There were no false positives: none of the Fermat base 2 pseudoprimes passed a Khashin Frobenius test for an admissible c in the prescribed range.
Continued Evaluation of a Frobenius Primality Test
