The test considers numbers (greater than 1) coprime to 30 in a given range. If the test number is denoted by $n$, we assume $n$ is prime and try to prove by contradiction that it is composite, i.e. that it fails one or more of the five congruences described in an earlier blog post (https://atomic-temporary-23414054.wpcomstaging.com/2024/11/13/a-perrin-like-primality-test-with-three-congruences/).
The first step is polynomial selection. We have a list of 23 cubic polynomials $f_{i}$ of the form $x^3 – rx – s$, and we test the polynomials in succession for irreducibility over $F_{n}$. Irreducibility of $f_{i}$ over $F_{n}$ is determined by looking at residue classes. For example, for the polynomial $f_{9} = x^3 -7x -7$, the residue class modulo 7 is examined. The polynomial $f_{9}$ is irreducible over $F_{n}$ when $n \equiv 2,3,4,5 \pmod 7$. Once the polynomial $f = x^3 – rx -s$ is selected, the sequence $V_k(r,s) \pmod n$ can be computed. We recall the definition of $V_k(r,s)$: $V_0(r,s)=3$, $V_1(r,s)=0$, $V_2(r,s)= 2r$ and $V_n(r,s) = rV_{n-2}(r,s) + sV_{n-3}(r,s) \text { for } k>2$. This allows the recurrence relation to be put in matrix form, as can be done for the Fibonacci sequence (https://en.wikipedia.org/wiki/Fibonacci_sequence).
The congruences are then:
(1) $V_n \equiv 0 \pmod n$
(2) $V_{n+1} \equiv -r \pmod n$
(3) $V_{n+2} \equiv \frac{-3s+\sqrt\Delta}{2} \text { or } V_{n+2} \equiv \frac{-3s-\sqrt\Delta}{2} \pmod n$
(4) $V_{n^2+1} \equiv -r \pmod n$
(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$
We recall that $\Delta$ is the discriminant of $f$ and that $\Delta = 4r^3-27s^2$. If $n$ is prime, then it will satisfy all five congruences. Therefore, if $n$ fails to satisfy one or more of the congruences, then $n$ is composite.
Occasionally, a number $n$ is such that none of the 23 polynomials is irreducible, because it fails to belong to the appropriate residue classes for each polynomial. This usually means that $n$ is in fact composite, although rarely $n$ will be a prime. This is an issue that needs further attention.
The job at Google Cloud Compute has passed $10^{12}$. No pseudoprimes were found. All 5 conditions passed is a test result of 1,1,1,1,1 or type 31. All type 31s are prime. No prime gets a test result of 0 through 30. All composites get a test result of either 0, 1, 2, 4, 8 or 16. This means that among the composites tested (the ones coprime to 30), none pass two or more of the 5 conditions.
Processing block 1013: 1012000000000 to 1013000000000
Type 0: 232055044329
Type 1: 15
Type 2: 112
Type 3: 0
Type 4: 2
Type 5: 0
Type 6: 0
Type 7: 0
Type 8: 9
Type 9: 0
Type 10: 0
Type 11: 0
Type 12: 0
Type 13: 0
Type 14: 0
Type 15: 0
Type 16: 15
Type 17: 0
Type 18: 0
Type 19: 0
Type 20: 0
Type 21: 0
Type 22: 0
Type 23: 0
Type 24: 0
Type 25: 0
Type 26: 0
Type 27: 0
Type 28: 0
Type 29: 0
Type 30: 0
Type 31: 38078286611
Type 31 primes: 38078286611
primesieve cumulative prime count excluding 2, 3, 5: 38078286611