The Cubic Frobenius probabilistic primality test

The Miller–Rabin test asks whether a random unit modulo $N$ behaves as it would if $N$ were prime. The cubic Frobenius test asks the same question in a rank-three algebra. Its prime-case identity is $z^N=\tau(z)$, where a cubic residue calculation selects one of two nonidentity conjugations.

This overview explains the test, the determinant-norm unit screen, an exact product formula for squarefree inputs, and the bound $\rho_{N,q}<N^{-3/2}$ when $N$ is a product of two distinct odd primes. It also reports what large computations do—and do not—suggest beyond the proved semiprime case. The work is preliminary and has not been peer reviewed.

Four ways into the story

I use abf as a short project label, not as a claim that the name has become standard. The descriptive name is the cubic Frobenius unit test.

From Fermat liars to algebra liars

For an odd integer $N$, the Fermat congruence

$$a^{N-1}\equiv1\pmod N$$

holds for every unit $a$ when $N$ is prime. A composite may nevertheless pass for some choices of $a$; these are the Fermat liars. Miller–Rabin strengthens the congruence and has a celebrated uniform bound: at most one quarter of the eligible bases are strong liars for any odd composite $N$ [Rabin; Monier].

Frobenius tests replace the scalar ring $\mathbf Z/N\mathbf Z$ by a polynomial quotient algebra and replace the identity map by a Frobenius conjugation. This idea has a substantial history, including Atkin’s normal cubics and Grantham’s general framework for Frobenius pseudoprimes [Atkin; Grantham]. The present construction fixes a particularly explicit cyclic cubic family and randomizes the element of the algebra, rather than the polynomial.

The central question is therefore familiar:

For a fixed composite $N$, what proportion of random algebra units imitate the prime-case Frobenius identity?

An exact answer is more informative than an isolated experiment. It reveals which arithmetic coincidences make an input deceptive and where a uniform bound could be sharp.

The cubic algebra and its conjugations

Choose a prime

$$q=t^2+t+7, \qquad a=2t+1,$$

so that $4q-27=a^2$. The first possibilities are $q=7,13,19,37,79,97,\ldots$. Put

$$f_q(X)=X^3-qX-q, \qquad A_N=(\mathbf Z/N\mathbf Z)[X]/(f_q),$$

and let $\alpha=[X]$. Since $f_q$ is monic, every element has a unique form

$$z=\ell\alpha^2+m\alpha+n, \qquad \ell,m,n\in\mathbf Z/N\mathbf Z.$$

When $N$ is composite, $A_N$ is generally not a field. It is an algebra over the commutative ring $\mathbf Z/N\mathbf Z$, and a free module of rank three. That distinction is useful rather than troublesome: the Chinese remainder theorem lets us read the algebra one prime factor of $N$ at a time.

The discriminant

$$\operatorname{disc}(f_q)=q^2(4q-27)=(qa)^2$$

is a square. Consequently, away from primes dividing $2aq$, the reduction of $f_q$ is either irreducible or splits completely; the linear-times-quadratic pattern does not occur. Moreover, the other two roots are explicit quadratic polynomials in $\alpha$. For example,

$$P_+(X)=\frac{6X^2-(a+9)X-4q}{2a}, \qquad P_-(X)=\frac{-6X^2+(9-a)X+4q}{2a}.$$

Substitution $\sigma(\alpha)=P_+(\alpha)$ defines a $(\mathbf Z/N\mathbf Z)$-algebra automorphism of order three, with $\sigma^2(\alpha)=P_-(\alpha)$. Thus there are two nonidentity conjugations, $\sigma$ and $\sigma^2$, and a prime input must tell us which one is its Frobenius.

Which conjugation does a prime obey?

Set $h=(q-1)/3$. The cubic character

$$\chi_q(N)\equiv N^h\pmod q$$

takes values among the three cube roots of unity modulo $q$:

$$1, \qquad s_1\equiv\frac{-a-3}{6}\pmod q, \qquad s_2\equiv\frac{a-3}{6}\pmod q.$$

Call $q$ admissible for $N$ when

$$\gcd(N,2aq)=1 \qquad\text{and}\qquad \chi_q(N)\ne1.$$

The explicit Frobenius-selection theorem says that, for prime $N$, $\chi_q(N)=s_1$ selects $\sigma^2$, while $\chi_q(N)=s_2$ selects $\sigma$ [Bernier, companion manuscript]. Write the selected map as $\tau_{N,q}$. Then every prime input satisfies

$$\label{eq:primeidentity} z^N=\tau_{N,q}(z) \qquad (z\in A_N).$$

The extension from $\alpha$ to an arbitrary element is elementary, but worth writing out. Every element of $A_N$ has a unique expression

$$z=\ell\alpha^2+m\alpha+n, \qquad \ell,m,n\in\mathbf F_N.$$

Because $N$ is prime here, the coefficients satisfy $\ell^N=\ell$, $m^N=m$, and $n^N=n$. The freshman’s dream and the identity $\alpha^N=\tau_{N,q}(\alpha)$ therefore give

$$\begin{aligned} z^N &=\bigl(\ell\alpha^2+m\alpha+n\bigr)^N \\ &=\ell^N\alpha^{2N}+m^N\alpha^N+n^N \\ &=\ell\bigl(\alpha^N\bigr)^2+m\alpha^N+n \\ &=\ell\,\tau_{N,q}(\alpha)^2 +m\,\tau_{N,q}(\alpha)+n \\ &=\tau_{N,q}\bigl(\ell\alpha^2+m\alpha+n\bigr) =\tau_{N,q}(z). \end{aligned}$$

In the penultimate line we used the fact that $\tau_{N,q}$ is an $\mathbf F_N$-algebra automorphism: it fixes the coefficients and preserves addition and multiplication. Thus, once the correct image of the single generator $\alpha$ is known, the identity follows for every element of the algebra. For composite $N$, exponentiation by $N$ is still a homomorphism on the multiplicative unit group, but it is not generally a ring homomorphism. Equation (1) can then hold only accidentally.

One randomized unit round

Why sample only units? Because the passing elements then form a subgroup. Multiplication by $z$ is a linear endomorphism $M_z:A_N\to A_N$ of the free rank-three module. Define

$$\operatorname{Nm}(z)=\det(M_z)\in\mathbf Z/N\mathbf Z.$$

The adjugate identity gives the clean criterion

$$\label{eq:unitscreen} z\in A_N^\times \quad\Longleftrightarrow\quad \gcd\bigl(\operatorname{Nm}(z),N\bigr)=1.$$

Thus a round is concrete:

1. Choose an admissible $q$ (the computations below use the least one) and determine $\tau_{N,q}$.

2. Choose $\ell,m,n$ uniformly modulo $N$ and put $z=\ell\alpha^2+m\alpha+n$.

3. Compute $g=\gcd(\operatorname{Nm}(z),N)$. If $1<g<N$, a factor has been found. If $g=N$, discard $z$ and resample. If $g=1$, the retained element is uniform in $A_N^\times$.

4. Compute $z^N$ and $\tau_{N,q}(z)$. A mismatch proves that $N$ is composite; a match passes this round.

The unit liars are

$$H_{N,q}=\{z\in A_N^\times:z^N=\tau_{N,q}(z)\}.$$

Because $A_N^\times$ is abelian, $H_{N,q}$ is the kernel of $z\mapsto z^N\tau_{N,q}(z)^{-1}$. Its relative size

$$\rho_{N,q}=\frac{|H_{N,q}|}{|A_N^\times|}$$

is exactly the error probability of one uniformly sampled unit round. Repeating independent rounds raises this probability to the corresponding power.

The arithmetic cost is $O(\log N)$ multiplications in a three-dimensional algebra, plus small-parameter work and gcds. This is a larger constant than one Miller–Rabin round. The point of the present work is therefore not a premature claim of practical superiority, but a structural and quantitative analysis of a new randomized parameter space.

The exact squarefree formula

Suppose $N$ is squarefree. At each prime $p\mid N$, the local algebra is one of

$$A_p\simeq \begin{cases} \mathbf F_p\times\mathbf F_p\times\mathbf F_p,& f_q\text{ splits modulo }p,\\ \mathbf F_{p^3},& f_q\text{ is irreducible modulo }p. \end{cases}$$

Call the cases split and inert. At an inert prime, the selected conjugation restricts to $z\mapsto z^{p^{u_p}}$ for a unique $u_p\in\{1,2\}$. The exact formula is

$$\label{eq:exactformula} \boxed{ \rho_{N,q} = \prod_{\substack{p\mid N\\p\ \mathrm{split}}} \frac{\gcd(N^3-1,p-1)}{(p-1)^3} \prod_{\substack{p\mid N\\p\ \mathrm{inert}}} \frac{\gcd\!\left(|N-p^{u_p}|,p^3-1\right)}{p^3-1}. }$$

The proof is a compact local calculation. The Chinese remainder theorem decomposes $A_N^\times$ into its prime components. In the inert case, $\mathbf F_{p^3}^\times$ is cyclic and the local equation is $z^{N-p^{u_p}}=1$, giving the second gcd. In the split case, $\tau$ cyclically permutes three copies of $\mathbf F_p^\times$; three linked equations reduce to $x^{N^3-1}=1$, giving the first gcd. Multiplying the local counts proves the displayed product formula.

This is the cubic analogue of what makes Monier’s formula so useful for Miller–Rabin: the probability is no longer a black box. It is a finite product whose unusually large factors can be studied one at a time.

The star witness: squarefree semiprimes

The cleanest theorem occurs when $N=pr$ with $p\ne r$ odd primes.

Thus one cubic unit round rejects a squarefree semiprime with probability greater than $1-N^{-3/2}$. The statement is uniform in the admissible parameter $q$, not merely valid for the least choice used in experiments.

This is not dimension counting. Although $A_N$ has about $N^3$ elements, the two local kernels can be enlarged by common divisors coming from cross-prime congruences. The theorem is a gcd-clash statement: the two primes cannot simultaneously donate enough local resonance to reach the $N^{-3/2}$ boundary.

The exponent is conditionally sharp. If admissible primes satisfy

$$r=p^3+p-1,$$

then $\rho_{pr,q}(pr)^{3/2}\to1^-$ along any unbounded such family. No infinitude is claimed; simultaneous primality here is a Bateman–Horn type problem. The small instance

$$N=2443=7\cdot349,\qquad q=937$$

already gives

$$\rho_{2443,937}^{-1}=124294, \qquad \rho_{2443,937}\,2443^{3/2}=0.971482621\ldots.$$

The comparison with Miller–Rabin should be read correctly. The classical $1/4$ bound applies to every odd composite and comes with decades of implementation experience. The $N^{-3/2}$ bound is far smaller but presently proved only for squarefree semiprimes, and a cubic round is more expensive. The mathematical novelty is the decaying, essentially sharp bound in this specific family.

What the computations say

For a consistent census, let $q_{\min}(N)$ be the least admissible prime $q=t^2+t+7$, and write

$$E(N)=-\frac{\log\rho_{N,q_{\min}(N)}}{\log N}.$$

Then $\rho=N^{-E}$, so a smaller $E$ means a more deceptive composite. The semiprime theorem says $E>3/2$ for every squarefree semiprime and every admissible $q$.

An exhaustive exact-formula census of all $36{,}410{,}418{,}784$ odd squarefree composites through $10^{11}$ found a smaller value once more prime factors were allowed:

$$\begin{aligned} N&=4{,}928{,}864{,}721 =3\cdot11\cdot61\cdot149\cdot16433,\\ q_{\min}&=7,\\ \rho_{N,7}&=\frac{1}{855{,}135{,}194{,}823},\\ E(N)&=1.231027170\ldots. \end{aligned}$$

Figure 1 shows the full distribution. The bulk is far to the right of the displayed record; the logarithmic vertical axis is essential. This computation is evidence, not a theorem. In particular, it does not prove $E(N)>1$, even for squarefree $N$.

Separate exact computations on Carmichael numbers through $10^{24}$ are also informative because Carmichael numbers inherit all the $p-1$ divisibility supplied by Korselt’s criterion. The smallest observed exponent in that census was

$$E(739{,}243{,}849{,}201)=1.354882088\ldots.$$

This suggests that the difficult cases are structured rather than random. It does not rule out a future example below $1$, and it does not replace a proof.

What remains open

The exact formula turns broad questions into arithmetic ones.

1. Can a composite fool every unit? The extreme event $\rho_{N,q}=1$ would be a cubic analogue of Carmichael behavior for this selected Frobenius congruence. No example is known.

2. Can $E(N)<1$? Equivalently, can $\rho_{N,q}>1/N$? Current data show a substantial margin but no general theorem.

3. What happens at fixed $\omega(N)$? The semiprime case is understood sharply. Even a positive asymptotic lower bound for $E$ at each fixed number of prime factors would be meaningful progress.

4. What changes at prime powers? Squarefreeness turns $A_N$ into a product of finite fields. Nonsquarefree inputs introduce congruence subgroups and a genuine lifting problem in finite local rings.

5. Where does the test belong computationally? A useful implementation should be benchmarked inside a conservative pipeline, alongside established tests, with reproducible random sampling and adversarial test sets. The mathematics does not yet justify replacing Miller–Rabin or Baillie–PSW.

To me, the conceptual question is broader than one algorithm:

How much finite-field structure can a composite modulus imitate before arithmetic compatibility forces the imitation to collapse?

The cubic algebra makes that question concrete. Its units can be sampled, its liars form a group, and—in the squarefree case—their proportion can be written down exactly.

Code, paper, and status

The preprint, companion manuscript, and source archive are available at Zenodo record 21705261. A single-threaded C/GMP reference implementation and an exact-guided tally demonstration are at github.com/mariotrevi/cubic-frobenius-unit-test.

This is a preliminary research project. The public implementation is a readable reference, not a certified cryptographic library. AI systems used under the names Fable, ChatGPT, and Kimi K3 contributed substantially to discussion, exposition, code review, and cross-checking. The author revised the material and takes responsibility for the statements and computations presented here.

References