The Perrin sequence is defined by $P(0)=3$, $P(1)=0$, $P(2)=2$ and the recurrence relation $P(n) = P(n-2) + P(n-3)$ for $n\gt 2$. The Perrin sequence has the property that, if $n$ is prime then $n|P(n)$. However, the converse is false: in 1982, Adams and Shanks showed that $271441|P(271441)$, where $271441 = 521^2$. In contrast to the fixed recurrence relation approach used by Adams and Shanks, my test selects the recurrence relation dynamically based on the input number $ n $. This means that the choice of the recurrence relation depends on the arithmetic properties of $ n $, allowing the test to adapt to the input rather than relying on a single, pre-determined recurrence relation. For integers $r \text{ and } s \gt 0$, we define a generalized Perrin sequence with parameters $r \text{ and } s$, denoted $V_n(r,s)$, by $V_0(r,s) = 3$, $V_1(r,s) = 0$, $V_2(r,s) = 2r$ and the recurrence relation $V_n(r,s) = r V_{n-2}(r,s) + s V_{n-3}$ for $n\gt 2$. The Perrin sequence is then obtained by setting $r=1 \text{, } s=1$. The characteristic equation of the sequence $V_n(r,s)$ is then $f = x^3 -rx -s = 0$. The discriminant $\Delta$ of the characteristic equation is then given by $\Delta = 4r^3 – 27s^2$. If $n$ is prime, we require the polynomial $f$ to be irreducible over $\mathbb{F}_{n}$ and introduce the field $K$ as the splitting field of $f$ over $\mathbb{Q}$. $K$ will be an abelian extension of $\mathbb{Q}$ if $\Delta$ is a perfect square.[See this Mathematics Stack Exchange posting: https://math.stackexchange.com/questions/2017810/galois-group-of-the-irreducible-cubic-equation-x3-3×1] We therefore require $\Delta$ to be a perfect square in $\mathbb{N}$. When $K$ is an abelian extension, class field theory shows that the irreducibility character of $f$ over $\mathbb{F}_{n}$ is periodic in $n$, in particular that if $p \equiv q \pmod N$, then $f$ is irreducible over $\mathbb{F}_{p}$ iff $f$ is irreducible over $\mathbb{F}_{q}$, where $p$ and $q$ are primes and $N$ is the conductor of $K$ [ref.: Mathematics Stack Exchange, https://math.stackexchange.com/questions/4995484/irreducibility-of-cubic-polynomials-over-finite-fields-f-p ].
As is the case with the Perrin sequence, the column vector $(V_k, V_{k-1},V_{k-2})^T$ can be obtained through matrix computations as: $M^{k-2} v_3$ where $v_3$ is the column vector $(V_2,V_1,V_0)^T$, and $M$ is the 3×3 matrix
Powers of $M$ modulo $n$ can be computed efficiently using the exponentiation by squaring algorithm (cf.: https://en.wikipedia.org/wiki/Exponentiation_by_squaring ). Galois theory allows one to obtain five congruences that must hold when $n$ is prime. These congruences are:
Congruence (1) $V_n \equiv 0 \pmod n$
Congruence (2) $V_{n+1} \equiv -r \pmod n$
Congruence (3) $V_{n+2} \equiv \frac{-3s + \sqrt\Delta}{2} \text{ or } V_{n+2} \equiv \frac{-3s – \sqrt\Delta}{2} \pmod n$ .
Note: we have a fourth congruence similar to Congruence (2) and a fifth one similar to Congruence (3):
Congruence (4) $V_{n^2+1} \equiv -r \pmod n$
Congruence (5) $V_{n^2+2} \equiv \frac{-3s + \sqrt\Delta}{2} \text{ or } V_{n^2+2} \equiv \frac{-3s – \sqrt\Delta}{2} \pmod n$
Congruence (1) is the same as the one in the Perrin probable prime test, although the recurrent sequences are different. We require that $f$ be irreducible over $\mathbb{F}_{n}$ (in case $n$ is prime) so that the splitting field of $f$ over $\mathbb{F}_{n}$ has degree 3 or more.
To show congruences (1), (2) and (3), given $f$ irreducible over $F_{n}$, we define
$$
A_{k} = \alpha^k + \beta^k + \gamma^k
$$
where $\alpha$, $\beta$ and $\gamma$ are the roots of $f$ in the splitting field $E$ of $f$ over $\mathbb{F}_{n}$. Then one can show that
$ A_k \equiv V_k \pmod{n} \text { for all } k \geq 0 $ . To do this, one checks that $A_{k}$ and $V_{k}$ have the same values modulo $n$ for $k=0 \cdots 2$ and that they satisfy the same recurrence relation. To derive Congruences (1), (2), (3), (4) and (5) one needs to delve into Galois theory. We shall also require Vieta’s formulas.(https://en.wikipedia.org/wiki/Vieta%27s_formulas) The polynomial $f$ is separable if $n \gt 3$ because the formal derivative $f’$ is non-zero and $f$ is irreducible. For now, we’ll accept that the Frobenius automorphism of $E$ defined by $\sigma(x) = x^n$ permutes the roots of $f$ cyclically and that, without loss of generality, $\sigma(\alpha)=\beta$, $\sigma(\beta)=\gamma$ and $\sigma(\gamma)=\alpha$. Then $$A_{n} = \alpha^n + \beta^n + \gamma^n = \beta + \gamma + \alpha = c_{1} = 0$$ where $c_{1}$ is the coefficient of $x^2$ in $f$. This establishes Congruence (1). We now calculate $A_{n+1}$: $$ A_{n+1} = \alpha^{n+1} + \beta^{n+1} +\gamma^{n+1}= \alpha^n \alpha+\beta^n \beta + \gamma^n \gamma = \beta \alpha + \gamma \beta + \alpha \gamma = c_2 = -r \pmod n$$ where $c_2$ is the coefficient of $x$ in $f$, which is: $-r \pmod n$. This establishes Congruence (2). For Congruence (3), the reader is referred to the answer of user Aryaman Maithani at this Mathematics Stack Exchange page: https://math.stackexchange.com/questions/4993773/how-does-one-compute-the-value-of-alphap2-betap2-gammap2-in.
The fact that the irreducibility character of $f$ over $\mathbb{F}_{n}$ is periodic in $n$, and that if $p \equiv q \pmod N$ then $f$ is irreducible over $\mathbb{F}_{p}$ iff $f$ is irreducible over $\mathbb{F}_{q}$ allows one to determine the irreducibility character of $f$ by table lookup, by congruence class modulo the conductor $N$ of the field extension $K$. Specifically, if $a$ is coprime to $N$, then by Dirichlet’s theorem on arithmetic progressions, there is a prime $p$ of the form $p = a + kN$ for some positive integer $k$. Then the irreducibility character of $f$ for $a$ modulo $N$ can be defined by the irreducibility character of $f$ for $\mathbb{F}_{p}$, which can be determined by standard functions in mathematical software (e.g. in PARI/gp, one can use the function polisirreducible). This allows for the contruction of an irreducibility character table with index the residue classes modulo $N$.
Currently, a list of 23 polynomials $f_1$, $f_2$, … $f_{23}$ is used in implementations of the test in PARI/gp and in the C programming language. Given the input number $n$, the algorithm proceeds in the same way whether $n$ is prime or composite. The polynomials $f_{i}$ are tried in succession, by order of increasing discriminant, starting with $f_1$. The pseudo-irreducibility of $f_i$ over $\mathbb{F}_{n}$ is determined by table lookup into the table for polynomial $f_i$. We write “pseudo-irreducibility” since $\mathbb{Z}/(n\mathbb{Z})$ may not be a field, nor an integral domain. Among the $\phi(N)$ residue classes of numbers coprime to $N$, very close to 2/3 of these correspond to numbers where $f_i$ is irreducible and 1/3 correspond to numbers where $f_i$ is not irreducible. It is straightforward to find and add new polynomials to the 23 on the list.
The data on probable prime counts from $1 \text{ to } 9 \times 10^{12}$ indicates that the test has no pseudoprimes in this range. In more detail, probable primes are counted and certain numbers for which none of the 23 polynomials is pseudo-irreducible are printed. The numbers that are printed exclude the class of numbers that are perfect cubes: for some reason, some perfect cubes are such that none of the 23 polynomials is pseudo-irreducible. We can exclude perfect cubes from being printed since they are composite. The remainder are either composite numbers which are not examined by the 23-polynomial test, or primes which are not examined by the 23-polynomial test. In case no unexamined prime numbers are printed, it is simple to interpret the probable primes count. If it agrees with the count given by recognized software such as Kim Walisch’s primesieve (https://github.com/kimwalisch/primesieve), then the test has no pseudoprimes in the range tested. If it exceeds the recognized count by a positive number $M$, then the test has $M$ pseudoprimes in the range tested. Technically, an omission of one genuine prime could be cancelled by the inclusion of a pseudoprime. If a prime $p$ is such that $f$ is irreducible over $\mathbb{F}_{p}$ and the test uses $f$, there aren’t supposed to be omissions, unless we overlooked something.
The code for the implementation in C has been updated since this post was first written. Currently, every number that satisfies all five congruences is individually tested for primality using the GMP library function mpz_probab_prime_p, which uses both the Baillie-PSW test and the Miller-Rabin test. A count is kept of numbers that satisfy all conditions and are prime. This number can then be compared with the count of numbers satisfying all five conditions. The results of an ongoing test run are discussed in this blog post: https://atomic-temporary-23414054.wpcomstaging.com/2024/11/30/cubic-frobenius-test-statistics-to-1012/.
Bibliography
- Adams, W. W., & Shanks, D. (1982)
“Strong primality tests that are not sufficient.”
Mathematics of Computation, 39(159), 255–300.
Link to paper - Baillie, R., & Wagstaff, S. S. (1980)
“Lucas pseudoprimes.”
Mathematics of Computation, 35(152), 1391–1417.
Link to paper - Cohen, H. (1993)
A Course in Computational Algebraic Number Theory.
Springer-Verlag.
Link to book - Caldwell, C. K. (2024)
The Prime Pages.
https://t5k.org/
Latest Pari/gp script:
isfrob3select(n) =
{
if(((n%2)==0)&&(n>2), return(0));
my(conductors = [7, 9, 13, 19, 37, 61, 67, 79, 97, 103, 139, 163, 199, 241, 271, 337, 349, 379, 409, 421, 463, 523, 1087],
r_values = [7, 3, 13, 19, 37, 61, 67, 79, 97, 103, 139, 163, 199, 241, 271, 337, 349, 379, 409, 421, 463, 523, 1087],
s_values = [7, 1, 13, 19, 37, 183, 201, 79, 97, 309, 139, 163, 199, 1205, 813, 2359, 349, 1895, 2045, 2947, 3241, 1569, 7609],
rootDs = vector(#conductors, i, sqrtint(4 * r_values[i]^3 - 27 * s_values[i]^2)));
for (i = 1, #conductors,
my(N = conductors[i], r = r_values[i], s = s_values[i], rootD = rootDs[i]);
if((gcd(n, N) > 1) && (n > r), return(0));
my(witness = nextprime(n % N));
if (polisirreducible(Mod(1, witness)*X^3 - Mod(r, witness)*X - Mod(s, witness)),
my(M = matrix(3, 3), v3 = matrix(3, 1));
M[1, 1] = Mod(0, n); M[1, 2] = Mod(r, n); M[1, 3] = Mod(s, n);
M[2, 1] = Mod(1, n); M[2, 2] = M[1, 1]; M[2, 3] = M[1, 1];
M[3, 1] = M[1, 1]; M[3, 2] = Mod(1, n); M[3, 3] = M[1, 1];
v3[1, 1] = Mod(2*r, n); v3[2, 1] = Mod(0, n); v3[3, 1] = Mod(3, n);
my(Mpp = Mod(M, n)^n, output = Mpp * v3);
if ((output[2, 1] == Mod(-r, n)) && (output[3, 1] == Mod(0, n)) &&
((output[1, 1] == Mod((-3*s + rootD)/2, n)) ||
(output[1, 1] == Mod((-3*s - rootD)/2, n))),
return(1));
)
);
return(0);
}
1 comment
Comments are closed.