In 1980, Baillie and Wagstaff proposed a novel primality test consisting of a strong Fermat base $2$ test and a standard or strong Lucas test (Baillie and Wagstaff, 1980). This test has come to be known as the Baillie-PSW test after the names of its creators, and is now commonly included in software for mathematics, including the Pari/gp calculator and the GNU Multiprecision library. The empirical strength of the test can be understood intuitively by thinking of strong Fermat pseudoprimes and Lucas pseudoprimes as being “almost disjoint” sets of numbers. A base $2$ pseudoprime is a composite number $N$ such that $2^{N-1}\equiv 1 \pmod N$. A base $2$ strong pseudoprime is a composite number that passes the Miller-Rabin test to base $2$. The base $2$ strong pseudoprimes are a proper subset of the base $2$ pseudoprimes.
Early work on primality tests based on recurrent sequences of degree three tended to focus on Perrin sequences and more generally on sequences whose characteristic polynomial has a discriminant which is a non-square (Adams and Shanks, 1982). A.O.L. Atkin in 1998 proposed a combination test consisting of a Miller-Rabin test, a Lucas-like test, and a cubic test. Crucially, Atkin’s cubic polynomials are normal ones, that is their Galois group over $\mathbb{Q}$ is abelian. Paraphrasing Atkin, using normal cubics, one can cheaply ensure that the cubic would be irreducible modulo $N$ (the test number) in case $N$ were prime. (Atkin, 1998)
In May 2025, Laurent and Underwood proposed a cubic primality test with a single parameter where the cubics have a square discriminant (Laurent and Underwood, 2025). At about the same time, I posted to my blog Python code for a cubic test that uses the same family of cubic polynomials as in the preprint by Laurent and Underwood (href: https://dbernier.ca/2025/04/26/numbers-game-python-code-for-beta-testers/ ). Although the cubic polynomials are identical, the tests are different.
In July 2025, I uploaded to ResearchGate a paper that proposes a cubic primality test that uses the same polynomials as Laurent and Underwood, and where one computes explicitly $\alpha^N$, $\alpha$ being a root of a cubic polynomial that depends on the test number $N$. This “experimental value” is then compared to the value one finds for $\alpha^N$ assuming $N$ is prime.
In a blog post in December 2025, I proposed a randomized version of this cubic test, where given a test number $N$, one tries random $q<Q_{Max}$ from the set of odd primes of the form $m^2 + m + 7 \text{ such that } m \geq 0$ until one finds a so-called valid pair $(N,q)$, assuming $N$ passes a fast screening test. In this note, we report our findings for the randomized test, which involved running the randomized test with $Q_{Max} = 1,000,000$ on Fermat pseudoprimes to base $2$, on ~$10$ million odd numbers from $3$ to $20,000,000$ and on about $2.4$ million Lucas pseudoprimes.
We repeat here the screening that is done in the randomized cubic test before calling a pair $(N,q)$ valid. N must be odd and greater or equal to $3$, and can be neither a perfect square nor a perfect cube. The candidate values of $q$ are the odd primes below $1$ million for which $4q-27$ is a perfect square. These form a sequence of $192$ terms beginning with $7, 13, 19, 37, …$ and ending with $999007$ (see the OEIS sequence at https://oeis.org/A005471 ). For the pair $(N,q)$ to be valid, we require in addition that $\gcd(N,q) = 1$, $\gcd(N,a) = 1$ and $c \not\equiv 1 \pmod q$, where $a := \sqrt{4q-27}$ and $c \equiv N^{\frac{q-1}{3}} \pmod q$.
Once a valid pair (N,q) is found, one can proceed with the test. Let $f = x^3 – qx – q$ and let $R_N$ be the ring $(\mathbb{Z}/N\mathbb{Z})[x]/(f)$. Let $\alpha$ denote the equivalence class of the indeterminate $x$ in $R_{N}$. Then form
$$
\beta = C_2 \alpha^2 + C_1 \alpha + C_0 \text{ where}
$$
$C_2 = 3q/d$,
$C_1 = -(d+9q)/(2d)$ and
$C_0 = -2q^2/d \pmod N$ where $d:= aq$ is the square root of the discriminant of $f$.
(Note that division by $d$ and $2d$ are well-defined, since $N$ is coprime to both $2$ and $d$.)
Let $s_1 = (-a-3)/6 \pmod q$ and let $s_2 = (a-3)/6 \pmod q$ be the two primitive cube roots of unity mod $q$.
The “predicted” Frobenius of $\alpha$ is $\beta$ if $c \equiv s_2 \pmod q$, and it is $\gamma := -(\alpha + \beta)$ otherwise.
If the computed Frobenius of $\alpha$, $\alpha^N$, matches the “predicted” one, $N$ is declared probably prime; otherwise, $N$ is declared composite.
The Fermat pseudoprimes to base $2$ below $2^{64}$ are available in tables of Feitsma (cf.: https://www.cecm.sfu.ca/Pseudoprimes/). For the first $10$ million pseudoprimes to base $2$ from those tables, the randomized cubic test achieves zero false-positives. More precisely, for every valid pair $(N,q)$ with $N$ among the first $10$ million base $2$ pseudoprimes and $q<1,000,000$, the Frobenius check fails (i.e., $\alpha^N$ does not match the predicted conjugate in $R_N$). We estimated the number of valid pairs $(N,q)$ with $N$ in the first $10$ million base $2$ pseudoprimes from analysis of a sample of the first $100,000$ base $2$ pseudoprimes. The sample mean of valid pairs per value of $N$ was $119.7$ . We get an estimate of $1.2$ billion valid pairs $(N,q)$ with $N$ in the first $10$ million pseudoprimes and $q<1,000,000$. A histogram of the number of valid pairs per value of $N$ appears below. All except a tiny fraction of the pair counts range between $70$ and $150$ valid pairs per $N$. There were no cases of partial matches with $2$ of $3$ coefficients matching between the “predicted” and the computed Frobenius of $\alpha$. There were $9$ instances of valid pairs $(N,q)$ with $1$ of $3$ coefficients being a match. These $1/3$ partial matches appear in the table below.
| N | q | mask | matched term |
|---|---|---|---|
| 341 | 20887 | 2 | $\alpha$ |
| 341 | 288913 | 2 | $\alpha$ |
| 341 | 771769 | 2 | $\alpha$ |
| 645 | 49069 | 1 | $1$ |
| 645 | 750829 | 1 | $1$ |
| 645 | 991027 | 1 | $1$ |
| 3277 | 709 | 1 | $1$ |
| 3277 | 97039 | 2 | $\alpha$ |
| 13981 | 607 | 4 | $\alpha^2$ |
For the first $10$ million odd numbers below $20$ million, the randomized cubic test achieves zero false-positives. As was the case with the Fermat pseudoprimes, there are no instances here of composites with $2/3$ coefficient matches. For the composites, the proportion of valid pairs with $1/3$ partial matches is estimated from random sampling at ~1 in $900,000$. (Note: the sampling was done by selecting an odd composite at random in $[3, 20000000]$ and a random $q$ from the $192$ possible choices.)
Finally, we subjected an initial segment of the Lucas pseudoprimes (when using Selfridge’s Method A of Lucas parameter selection), to our test. The Lucas pseudoprimes below $10^{15}$, computed by Dana Jacobsen, are available from https://ntheory.org/pseudoprimes.html. There are approximately $2.4$ million Lucas pseudoprimes below $10^{15}$, and none are pseudoprimes to the randomized cubic test. There were no cases of $2/3$ partial matches between the coefficients of the “predicted” and the computed Frobenius of $\alpha$. There were $2$ cases of $1/3$ partial matches, namely $(N,q)=(323, 711499)$ and $(N,q)=(16211, 4297)$.
These findings are encouraging for potential use of the randomized cubic test in combination with a Miller-Rabin test to base $2$. With the Miller-Rabin base $2$ test acting as a filter, the combination with the randomized cubic test yields a deterministic test for inputs below $5.8 \times 10^{16}$ (Note: the $10,000,000\text{th}$ base $2$ pseudoprime is $58,036,840,105,130,209$. The deterministic label is asserted only for the value $Q_{Max}=1,000,000$) Moreover, partial matches of $2/3$ are non-existent in this range. Of the $9$ partial matches of $1$ coefficient out of $3$ among the first $10,000,000$ base $2$ pseudoprimes, only two valid pairs pass the Miller-Rabin filter, namely $(N,q)=(3277, 709)$ and $(N,q)=(3277,97039)$. For use as a standalone test, the results so far are consistent with good potential as a randomized test in multi-round combinations. The fact that none of the Lucas pseudoprimes below $10^{15}$ pass the randomized cubic test is consistent with the notion that Lucas pseudoprimes and pseudoprimes to the randomized cubic test are uncorrelated.
References
Research Articles
- Adams, W., & Shanks, D. (1982). Strong primality tests that are not sufficient. Mathematics of Computation, 39(159), 255-300.
- Atkin, A. O. L. (1998). Intelligent primality test offer. In D. A. Buell & J. T. Teitelbaum (Eds.), Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkin, 1-11. American Mathematical Society.
- Baillie, R., & Wagstaff, S. S. (1980). Lucas pseudoprimes. Mathematics of Computation, 35(152), 1391-1417.
- Laurent, P., & Underwood, P. (2025). A Cubic Composite Test. arXiv preprint arXiv:2505.02167 [math.NT].
- Williams, H. C. (1987). Characterizing pseudoprimes for third-order linear recurrences. Mathematics of Computation, 48(177), 393-411.
Author’s Publications
- Bernier, D. (April 2025). Numbers game: Python code for beta testers. D. Bernier’s Blog.
- Bernier, D. (July 2025). A Cubic Primality Test Based on Explicit Frobenius Computation. ResearchGate.
- Bernier, D. (December 20, 2025). Implementation of the randomized cubic primality test in Python. D. Bernier’s Blog.
Data Sources and Tools
- Feitsma, J. Tables of Fermat pseudoprimes.
- Jacobsen, D. Pseudoprime Statistics, Tables, and Data.
- OEIS Foundation Inc. Sequence A005471: Primes p such that 4p-27 is a square. The On-Line Encyclopedia of Integer Sequences.
