A Cubic Primality Test Based on Explicit Frobenius Computation. According to this document from July 10, 2025, the core idea is to build a primality test by explicitly computing the Frobenius action in a cubic extension and comparing it to a predicted conjugate. The randomized version below keeps the same mathematics, but replaces “search for a suitable parameter” by “pick a suitable parameter at random and repeat”.
Fix an odd integer $N\ge 3$ to be tested. We work in the quotient ring
$$
R_N := (\mathbb{Z}/N\mathbb{Z})[x]\big/\bigl(f(x)\bigr),
\qquad
f(x)=x^3-qx-q,
$$
and we write $\alpha:=x \bmod (f,N)$ for the residue class of $x$ in $R_N$. When $N$ is prime and $f$ is irreducible modulo $N$, adjoining $\alpha$ produces a cubic extension of $\mathbb{F}_N$ in which the Frobenius map $\sigma(y)=y^N$ permutes the three roots of $f$ cyclically.
A key design choice is to insist that the discriminant of $f$ is a square. For $f(x)=x^3-qx-q$ one has
$$
\mathrm{Disc}(f)=4q^3-27q^2=q^2(4q-27).
$$
In the paper, this “square discriminant” condition is used to force the splitting field over $\mathbb{Q}$ to be an abelian (cyclic of order $3$) extension, which is exactly the setting that Atkin called “normal cubics”.
In my current implementation I take $q$ from the parametric family
$$
q = m^2+m+7,
$$
restricted to those $m$ for which $q$ is prime and $q\leq Q_{Max}$, where $Q_{Max}$ is some medium-sized parameter. This has the convenient identity
$$
4q-27 = 4(m^2+m+7)-27 = (2m+1)^2,
$$
so a square root of $4q-27$ is available as
$$
a := 2m+1.
$$
Then a square root of the discriminant is
$$
d := \sqrt{\mathrm{Disc}(f)} = \sqrt{4q^3-27q^2} = aq,
$$
at least as a formal expression; in computations we reduce everything modulo $N$ and require $d$ to be invertible modulo $N$.
The test has two conceptual phases.
Phase A: cheap sifting.
We immediately reject (or skip, in profiling runs) trivial composites: even $N$, perfect cubes, and (in the current randomized experiments) perfect squares. The square sieve is an added practical refinement motivated by the empirical observation that “partial matches” of the cubic Frobenius condition tend to concentrate on squares; eliminating squares up front keeps the search for genuine “liars” focused on more informative composites.
Phase B: one randomized Frobenius round.
Pick a random prime parameter $q=m^2+m+7$ from a precomputed pool. A round is declared valid only if $\gcd(N,q)=1$ and $\gcd(N,a)=1$, so that $d=aq$ is invertible modulo $N$ (this mirrors the paper’s instruction to check $\gcd(d,N)$ before continuing).
Next comes the irreducibility/cubic-residue screen. The paper notes that instead of finding a prime $p\equiv N\pmod q$ and testing irreducibility modulo $p$, one may be able to use the cubic residue symbol condition
$$
c := N^{(q-1)/3} \pmod q
$$
and require $c\not\equiv 1 \pmod q$ (and $c\not\equiv 0$, which is already excluded by $\gcd(N,q)=1$).
In practice, I keep only those $q$ for which this screen passes; otherwise the round is discarded and we sample a new $q$.
Now we predict which conjugate should equal $\alpha^N$. The paper defines
$$
s_1=\frac{-a-3}{6}\pmod q,\qquad s_2=\frac{a-3}{6}\pmod q,
$$
and states the Cubic Residue Conjecture: if $c\equiv s_1\pmod q$ then $\alpha^N=\gamma$, and if $c\equiv s_2\pmod q$ then $\alpha^N=\beta$.
To make this prediction concrete, we explicitly build $\beta$ (and hence $\gamma$) as quadratic polynomials in $\alpha$ using the coefficients from Section 4:
$$
C_2 = \frac{3q}{d},\qquad
C_1 = -\frac{d+9q}{2d},\qquad
C_0 = -\frac{2q^2}{d}\quad\text{in }\mathbb{Z}/N\mathbb{Z},
$$
then
$$
\beta = C_2\alpha^2 + C_1\alpha + C_0\in R_N,\qquad
\gamma = -(\alpha+\beta)\in R_N.
$$
We choose “predicted Frobenius” to be $\beta$ if $c\equiv s_2\pmod q$, and otherwise $\gamma$ (since we already enforced $c\not\equiv 1$).
Finally, we compute the actual Frobenius image
$$
\mathrm{frob} := \alpha^N \in R_N,
$$
write it as $\mathrm{frob}=c_0+c_1\alpha+c_2\alpha^2$, and accept the round if $\mathrm{frob}$ equals the predicted element in $R_N$ (coefficientwise modulo $N$).
The randomized cubic test repeats Phase B until it has accumulated $K$ valid rounds. If all $K$ rounds pass, we declare $N$ a “probable prime” for this test. If any valid round fails, $N$ is declared composite. The hope, supported by the paper’s data and by subsequent large-scale scans, is that for composite $N$ the probability of surviving many valid rounds is extremely small, while true primes behave deterministically and pass.
