Introduction
Primality testing is of fundamental importance to number theory. For numbers $n$ up to about a million,
high-school level methods such as trial division by the integers $d$ such that $d \leq \sqrt n$ are simple
and effective. However, they are no match even for $30$-digit numbers.
Let us consider the $32$-digit number
$n = 10000000000000000000000000000033$.
One formulation of Fermat’s Little Theorem
is that if $p$ is a prime and $a$ is a number not divisible by $p$, then $a^{p-1} – 1$ is divisible by $p$.
This is written in congruence notation as: $a^{p-1} \equiv 1 \pmod p$.
For odd $p$, $a=2$ is allowable in Fermat’s Little Theorem.
For our number $n$, even with a number theory calculator, $n$ is too large to directly form the power $2^{n-1}$.
However, we can do calculations “modulo $n$”, that is where one keeps track only of remainders upon division by $n$. Suffice it to say that Pari/gp reports that $n$ “passes” Fermat’s Little Theorem with $a=2$:
? Mod(2,n)^(n-1)
Mod(1, 10000000000000000000000000000033)
(the remainder of $2^{n-1}$ divided by $n$ is $1$)
This provides moderately good evidence that $n$ might be prime, but again $n$ might in fact be composite!
The pros and cons of using Fermat’s Little Theorem as a primality test are discussed on the Wikipedia page on the Fermat primality test, as well as related pages.
Some primality tests can be better understood using the language of finite fields. In the following section, the level will be more demanding, say requiring a full undergraduate course in abstract algebra for mathematics majors.
Cubic Fields
Let $n$ be a number to be tested for primality. We will be making use of the properties of finite fields defined by
$\mathbb{F}_{l}[x]/(f)$, where $l$ is prime and $f$ is a monic irreducible polynomial of degree $3$ over $\mathbb{F}_{l}$.
We may assume that $n>1$ is not a perfect power, and that it is not divisible by small primes. The cubic polynomials we will use are of the form
$f = x^3-cx-c$,
where $c$ is a positive integer such that the discriminant of $f$ is a perfect square. In other words, $4c^3 -27c^2$ is a perfect square. These integers form the OEIS sequence $A027692$, and may be obtained as the values of $m^2+m+7$ for $m\geq 0$. To better understand the test, we assume for now that $n$ is prime. We are interested in the $c$ for which $f$ is irreducible over $\mathbb{F}_{n}$, so that we may form the finite field with $n^3$ elements by taking $$K=\mathbb{Z}/n\mathbb{Z}[x]/(f)$$. We will address later how to select $c$ so that $f$ is irreducible modulo $n$.
We are now ready to study the identities that hold in the field $K$. Denoting by $\alpha$ the class of the indeterminate $x$ in $K$, then $f(\alpha)=0$ in $K$. The Frobenius automorphism $\sigma$ is defined on $K$ by
$\sigma(s)=s^n$,
$n$ being the characteristic of $K$.
The Frobenius map permutes the three roots of $f$ in $K$ without fixed points. Without loss of generality, we define $\beta := \alpha^n$ and $\gamma := \beta^n$. Then $\alpha$, $\beta$ and $\gamma$ are the three distinct roots of $f$ in $K$.
From Vieta’s formulas, one obtains the identities:
$s_{1} = \alpha + \beta + \gamma = 0$
$s_{2} = \alpha \beta + \alpha \gamma + \beta \gamma = -c$
$s_{3} = \alpha \beta \gamma = c$
We call the $s_{1}$ identity the trace criterion, the $s_{2}$ identity the $s_{2}$-criterion, and the $s_{3}$ identity the norm criterion. The trace criterion gets its name from the field trace in Galois Theory, and the norm criterion gets its name from the field norm.
The computations of $s_{1}$, $s_{2}$ and $s_{3}$ involve polynomial algebra and calculations in $\mathbb{F}_{n}$. Each computation yields a unique element of the finite field $\mathbb{F}_{n}$.
We said earlier that the Frobenius map permutes the three roots of $f$ in $K$ without fixed points. This is due to the Galois group of $K$ over $\mathbb{F}_{n}$ being the cyclic group $C_{3}$ (cf. OEIS entry $A027692$). This Galois group is abelian because the discriminant of $f$ is a perfect square.
Choosing a $c$ such that $f=x^3-cx-c$ is irreducible over $\mathbb{F}_{n}$ can be done using a cubic analog of the quadratic reciprocity law of Gauss. These higher reciprocity laws are part of Class Field Theory. The conductor of the extension field $L=\mathbb{Q}[x]/(f)$ over $\mathbb{Q}$ can be thought of as a positive integer $N$ that regulates the splitting behavior of the prime ideals of $\mathbb{Z}$ in the ring of integers of $L$. In particular, if $q$ is a prime and conditions (1) and (2) below hold, then condition (3) holds:
$(1)\quad q \equiv n \pmod N$
$(2)\quad f \text{ is irreducible over } \mathbb{F}_q$
$(3)\quad f \text{ is irreducible over } \mathbb{F}_n$.
In the range of m under consideration (see below), one always has $N | c$.
( Proof using Pari/gp:
? a(m)=m^2+m+7
? for(m=0,10000,p=a(m);f=x^3-p*x-p;Q = bnfinit(y);
cond=rnfconductor(Q, f)[1];c1=cond[1];
N=c1[1,1];rem=(p%N);if(!(rem==0),print(“p=”,p,” N=”,N)))
?
)
For this reason, (1) may be replaced by the stronger condition (1′) while keeping (2) and (3):
(1′)$\quad q \equiv n \pmod c$
(2′)$\quad f \text{ is irreducible over } \mathbb{F}_q$
(3′)$\quad f \text{ is irreducible over } \mathbb{F}_n$
In practice we search for a prime $q$ such that (1′) and (2′) hold. We may assume that $\gcd(n,c)=1$, otherwise $n$ has a small divisor.
Let $q$ the first prime in the arithmetic progression $r, r+c, r+2c, r+3c, \dots$ where $r$ is the remainder of dividing $n$ by $c$. Condition (1′) is automatic.
In case $f$ is not irreducible over $\mathbb{F}_q$, we go to the next value of $c$ in the sequence of the $m^2 + m + 7$.
We continue the search for $q$ either until we have found one satisfying (1′) and (2′) or until $m = 1000$.
When our search for $q$ is successful, then conditions (1′) and (2′) imply (3′), and $f$ is irreducible over $\mathbb{F}_n$.
To complete our discussion of the test, we need to say something about the case of composite $n$. We first check if $n$ is a perfect power; if so, we return the value zero, about which we will say more shortly. Secondly, we do trial division by small primes, e.g. the primes up to $200$. For numbers divisible by small primes, we return the value zero also. For the remaining composites, we proceed as if $n$ were prime, that is we search for $c$ from the sequence of the $m^2 + m + 7 \quad, (m\geq 0)$, and search for a prime $q$ such that (1′) and (2′) hold. The condition (2′) might be related to cubic residuosity. We can’t give a bound on the size of $c$, however in millions of tries, we haven’t encountered the bound $m = 1000$.
With respect to the Vieta formulas, the satisfaction or non-satisfaction of the trace, norm, and $s_2$ criteria is encoded as:
4 * s2_passed + 2 * norm_passed + trace_passed, where passed
criteria result in a 1 and failed criteria result in a 0.
The range of return values for the combination test is therefore $0$ to $7$ inclusively.
The computations of $s_1$, $s_2$, and $s_3$ (Vieta’s formulas) in $\mathbb{Z}/n\mathbb{Z}[x]/(f)$ can be rendered more accessible by working with 3×3 matrices over $\mathbb{Z}/n\mathbb{Z}$
(see Cohen, A Course in Computational Algebraic Number Theory, Chapter 4). Given $n$ and $c$, we define the matrix $A$ over $\mathbb{Z}/n\mathbb{Z}$ by
$A = \begin{pmatrix}
0 & 0 & c \\
1 & 0 & c \\
0 & 1 & 0
\end{pmatrix}
$
[Note that in the C code implementation, $c$ is replaced by the least non-negative number congruent to $c$ modulo $n$.]
It is the companion matrix of $f = x^3-cx-c \text{ in } \mathrm{Mat}_{3}(\mathbb{Z}/n\mathbb{Z})$.
Then $s_1$ through $s_3$ may be replaced by $s_1’$ through $s_3’$:
(s1′)$\quad A + A^n + A^{n^2} = 0$
(s2′)$\quad A^{n+1} + A^{n^2+1} + A^{n^2+n} + cI = 0$
(s3′)$\quad A^{1+n+n^2}-cI=0$
where $I$ is the identity matrix in $\mathrm{Mat}_{3}(\mathbb{Z}/n\mathbb{Z})$.
We now give an example using the matrix formulation for $n = 41$. The first candidate $c$ is $7$. The first prime in the sequence $6, 13, 20, \dots$ is $13$, so $q=13$ in (1′). Next, is $x^3-7x-7$ irreducible over $\mathbb{F}_{13}$ ?
No, because $1$ is a root of $x^3-7x-7 \pmod {13}$. The next choice of $c$ is $c=9$. We first check $\gcd(n,c)=\gcd(41,9)=1$. The first prime
in the sequence $5, 14, 23, \dots$ is $5$, so $q=5$ in (1′). Next, is $x^3- 9x-9$ irreducible over $\mathbb{F}_5$ ?
The answer is yes.
We next check that $41$ is not a perfect power, which isn’t difficult. We now form the matrix $A$ in $\mathrm{Mat}_{3}(\mathbb{Z}/41\mathbb{Z})$:
$A = \begin{pmatrix}
0 & 0 & 9 \\
1 & 0 & 9 \\
0 & 1 & 0
\end{pmatrix}
$
Condition (s1′) is that $A + A^n + A^{n^2} = 0 \text{ in } \mathrm{Mat}_{3}(\mathbb{Z}/41\mathbb{Z})$,
which checks out.
Condition (s2′) is that $A^{n+1} + A^{n^2+1} + A^{n^2+n} + 9I = 0$,
which also checks out.
Condition (s3′) is that $A^{1+n+n^2}-9I = 0$,
which also checks out.
So the return value of $n=41$ in the Vieta combination test is: $4+2+1 = 7$.
The Vieta combination test was implemented in the C programming language with the help of Manus AI. A trial run up to $n = 10^{10}$ was carried out. The output is copied below:
Vieta Combined Test (Trace/Norm/S2 – Corrected S2) up to n=10000000000…
Finished testing up to 10000000000.
Total OMP time: 6134.69 seconds
— Results Summary —
Value Key: 4s2 + 2norm + trace (1=pass, 0=fail)
Result 7 (Pass All (T+N+S2)): 455052511 total passers
Total numbers passing at least one test: 455052511
Total composite passers (any test): 0
According to Wikipedia, the number of primes up to $10^{10}$ is $455052511$ which matches the total passers with a result of $7$. It’s encouraging that no composites up to $10^{10}$ (which are neither perfect powers nor divisible by small primes) passed even one of the three criteria.
This algorithm (or minor variants) were used to compute tables of passers (for each of the three criteria, separately) for ranges up to $20$ billion. All recorded passers turned out to be prime and all primes were passers. We continue to monitor the quality of the output.
