Given an odd number n>=3, non-square and an odd number c such that Jacobi(c,n)=-1 and 1<c<n/2,
Khashin’s Frobenius primality test checks whether the congruence (1+sqrt(c))^n == 1-sqrt(c) (modulo n)
holds.
This congruence holds whenever n is a prime number, thanks to properties of the Frobenius
automorphism map x |-> x^p where p is prime and x is in F_p^2, the field with p^2 elements.
The congruence occasionally holds when n is a composite number, in which case we say that the
pair (n,c) is a false positive. For an integer x we can look at the total number t(x) of
candidates (n,c) for the Frobenius test with n<x odd, non-square, and odd c with 1<c<n/2 and
Jacobi(c,n)=-1, together with the number fp(x) of candidates with n composite for which the
Frobenius test returns a false result of “prime”. Then we call fp(x)/t(x) the average false
positive rate for n<x.
In general, false positives are quite rare with the first few being:
n=5719 with c=1685, n=8149 with c=2277, n=9017 with c=2537 and n=9809 with c=1179.
For x = 20000, 40000, … 660000 I had the average false positive rate fp(x)/t(x) calculated,
and then did a least squares fit for the linear model: log(y) = a log(x) + b. Here x takes on
the 33 values 20000, 40000, … 660000 and y takes on the corresponding values fp(x)/t(x). The
least squares fit gives the relation log(y) = -0.8429 log(x) -6.0754 . This corresponds to
y = 0.0023 x^(-0.84).
This means that if we were to apply Khashin’s Frobenius test to the
smallest c such that the pair (n,c) is a candidate for the Frobenius test, we would expect
in case n is composite to get a false positive with probability 0.0023 n^(-0.84). Using calculus,
one can approximate the expected number of false positives in testing all odd non-square n up to
some bound 10^k through an integral, which results in the following table:
k Expected false positives for n<10^k
3 0.021706
4 0.031375
5 0.045350
6 0.065551
7 0.094750
8 0.136955
9 0.197960
10 0.286140
11 0.413597
12 0.597830
13 0.864128
14 1.249044
15 1.805418
16 2.609624
17 3.772054
18 5.452276
19 7.880937
20 11.391420
An updated formula for the approximate average false positive rate is given by fp(x)/t(x) ~= 0.0481*x^(-1.09). A second update gives fp(x)/t(x) ~= 0.0834*x^(-1.13). A third update gives fp(x)/t(x) ~= 0.181*x^(-1.19).
The plot of the average false positive rate fp(x)/t(x), as well as an updated plot, are reproduced below.
