It’s a test that any prime number passes, but that only a few composite numbers pass. The test is made up of three congruences that are proved using basic Galois Theory. The setup is an irreducible polynomial $f$ over $\mathbb F_{p}$ with $f = X^3 – rX – s$, and $r>0$ $s>0$. Additionally, we require the discriminant $\Delta$ of $f$ to be a square. In practice, we need several (up to 22 or more) cubic polynomials to get a minuscule chance that none of these is irreducible over $\mathbb F_p$. Initially it may be easier, in order to understand the test, to assume that $p$ is prime. Following Edouard Lucas ( https://en.wikipedia.org/wiki/Lucas_sequence ), we define for $k>=0$ $$V_{k} = \alpha^k + \beta^k + \gamma^k$$ , where $\alpha$, $\beta$ and $\gamma$ are the roots of $f$ in a splitting field of $f$ over $\mathbb F_{p}$. The $V_{k}$ are symmetric polynomials in three variables, and the Fundamental theorem of symmetric polynomials (cf. https://en.wikipedia.org/wiki/Elementary_symmetric_polynomial) guarantees that every symmetric polynomial can be expressed in terms of the elementary symmetric polynomials. This means that every $V_{k}$ can be expressed in terms of the elementary symmetric polynomials in $\alpha$, $\beta$ and $\gamma$. Special cases are (1) $V_{p} = V_{1} = 0$ in $\mathbb F_{p}$, and (2) $V_{p+1} = -r$ in $\mathbb F_{p}$. These follow from basic properties of the Frobenius automorphism $ \sigma(x) = x^p$ on $\mathbb F_{p^{3}}$ (cf. https://en.wikipedia.org/wiki/Frobenius_endomorphism ) The third relation is (3) $V_{p+2} = (-3s + \sqrt\Delta)/2$ or $V_{p+2} = (-3s-\sqrt\Delta)/2$ where $\Delta$ is the discriminant of $f$.(cf. User Aryaman Maithani’s answer to my question at Mathematics Stack Exchange: https://math.stackexchange.com/questions/4993773/how-does-one-compute-the-value-of-alphap2-betap2-gammap2-in). These three equations can also be viewed as congruences modulo $p$ if we are dealing with integers. The $V_{k}$ can be computed modulo $p$ using linear recurrence relations, as in the blog post: https://dbernier.ca/2024/11/13/a-perrin-like-primality-test-with-three-congruences/.
In case $p$ is composite, we can follow the same algorithmic procedure as if $p$ is prime. In particular, the “irreducibility” of $f$ over $\mathbb F_{p}$ is checked via table lookup. This is permissible because the irreducibility character of a fixed polynomial $f$ over $\mathbb F_{p}$ is periodic in the $p$ variable (cf. User leoli1’s answer to my question at Mathematics Stack Exchange: https://math.stackexchange.com/questions/4995484/irreducibility-of-cubic-polynomials-over-finite-fields-f-p). It occurs to me that in case a composite does not pass the test, we have a “proof by contradiction” starting from the hypothesis that the input number is prime: we’ve proved the input number cannot be prime.
There are two issues with the cubic Frobenius primality test that arise in practice. The first is prime numbers such that every polynomial on the list factors over $\mathbb F_{p}$. This issue can be addressed by adding some new cubic polynomials. The second is the appearance of composites that pass all three conditions. Here, one can change the ordering of the polynomials, but the risk of encountering pseudoprimes remains. So far, up to 1,000,000,000,000 no pseudoprimes have been found for the three conditions.
Here is the list of the 23 polynomials currently in use:
$$ f_{1} = X^3 – 7X – 7$$
$$ f_{2} = X^3 – 3X – 1$$
$$ f_{3} = X^3 – 37X – 37$$
$$ f_{4} = X^3 – 13X -13$$
$$ f_{5} = X^3 – 61X – 183$$
$$ f_{6} = X^3 – 97X – 97$$
$$ f_{7} = X^3 – 79X – 79$$
$$ f_{8} = X^3 – 19X – 19$$
$$ f_{9} = X^3 – 139X – 139$$
$$ f_{10} = X^3 – 163X – 163$$
$$ f_{11} = X^3 – 67X – 201$$
$$ f_{12} = X^3 – 103X – 309$$
$$ f_{13} = X^3 – 241X – 1205$$
$$ f_{14} = X^3 – 271X – 813$$
$$ f_{15} = X^3 – 199X – 995$$
$$ f_{16} = X^3 – 379X – 1895$$
$$ f_{17} = X^3 – 337X – 2359$$
$$ f_{18} = X^3 – 421X – 2947$$
$$ f_{19} = X^3 – 409X – 2045$$
$$ f_{20} = X^3 – 463X – 3241$$
$$ f_{21} = X^3 – 349X – 349$$
$$ f_{22} = X^3 – 523X – 1569$$
$$ f_{23} = X^3 – 1087X – 7609$$
david@HPLaptop:~/mar31/nov08_threads$ gcc -O3 isfrob3select22a.c -lm -lpthread
david@HPLaptop:~/mar31/nov08_threads$ time ./a.out
Total primes found between 0 and 1000000000000: 37607911994
[75455517493, 75875964949, 96098943851, 180399753253, 209258080793, 242933710447, 260689808933, 272572599473, 318998948003, 429825582341, 433929229397, 603561499003, 663529975597, 688868185517, 703855003697, 801039617461, 803730342043, 841356510931, 846621827297, 859271263271, 897471164143, 923879902373, 964327354271, 975041739251]
// 24 missing primes
? 37607911994+24
%1301 = 37607912018 // count of probable primes, plus 24 missing primes
primepi(10^12) = 37607912018 // conclusion: no pseudoprimes below 10^12
bernierd121@instance-20241109-155454:~$
[1]+ Done nohup ./a.out > data4
bernierd121@instance-20241109-155454:~$
bernierd121@instance-20241109-155454:~$ cat data4
Total primes found between 0 and 200000000000: 8007105059 // Correct
bernierd121@instance-20241109-155454:~$ ^C
bernierd121@instance-20241109-155454:~$ ^C
bernierd121@instance-20241109-155454:~$
Current job:
bernierd121@instance-20241109-155454:~$ gcc -O3 isfrob3select81a.c -lpthread -lm
bernierd121@instance-20241109-155454:~$ nohup ./a.out > data5 &
[1] 22793
bernierd121@instance-20241109-155454:~$ nohup: ignoring input and redirecting stderr to stdout
bernierd121@instance-20241109-155454:~$
========================== below: added Nov 12, 9:30am============================
bernierd121@instance-20241109-155454:~$ cat data89 \\ from program isfrob3select89a.c
Total primes found between 2000000000000 and 3000000000000: 35038402564 \\ matches primesieve result
// from Kim Wallisch's primesieve peogram:
david@HPLaptop:~/mar31/nov11/games$ primesieve 2000000000000 3000000000000 -c
Sieve size = 256 KiB
Threads = 20
100%
Seconds: 59.866
Primes: 35038402564
====================== below added Nov 12 at 3:20 pm ========================
david@HPLaptop:~/mar31/nov11$ gcc -o test_poly -O3 isfrob3_test_poly1a.c -lpthread -lm
david@HPLaptop:~/mar31/nov11$ time ./test_poly
Total primes found between 1000000 and 3000000000000: 0 \\ there are no missing primes from 1e12 to 3e12
real 1349m15.076s
user 20874m45.905s
sys 0m5.958s
=================== below added Nov 13 at 9:30 pm ==========================
bernierd121@instance-20241109-155454:~$ cat data91
4905352160983 might be a missing prime \\ composite
Total primes found between 3000000000000 and 5000000000000: 68951362946 \\ Correct
\\ primesieve:
david@HPLaptop:~$ primesieve 3000000000000 5000000000000 -c
Sieve size = 256 KiB
Threads = 20
100%
Seconds: 112.670
Primes: 68951362946
============================ below added Nov 14 at 9:00 am =======================
david@HPLaptop:~/mar31/nov14$ gcc -O3 isfrob3select96a.c -lpthread -lm
david@HPLaptop:~/mar31/nov14$ ./a.out
5021050770919 is a missing prime
Total primes found between 5000000000000 and 5030000000000: 1025878273
Total missing primes between 5000000000000 and 5030000000000: 1
Grand total of primes found and missing primes between 5000000000000 and 5030000000000: 1025878274 \\ Correct!
david@HPLaptop:~/mar31/nov14$ primesieve 5000000000000 5030000000000 -c
Sieve size = 256 KiB
Threads = 20
100%
Seconds: 2.724
Primes: 1025878274
============================== below added Nov 15 10:05 am ==================
bernierd121@instance-20241109-155454:~$ cat data95
7429504365109 might be a missing prime \\ Composite
7430323546619 might be a missing prime \\ Composite
Total primes found between 7000000000000 and 9000000000000: 67322665304 \\ No adjustment needed : MATCH with PRIMESIEVE!!!
\\ primesieve result:
david@HPLaptop:~/mar31/nov14$ primesieve 7000000000000 9000000000000 -c
Sieve size = 256 KiB
Threads = 20
100%
Seconds: 131.415
Primes: 67322665304
========================= below added Nov 15 11:55 am ===============
david@HPLaptop:~/mar31/nov13$ gcc -O3 isfrob3select93a.c -lpthread -lm
david@HPLaptop:~/mar31/nov13$ time ./a.out
5020419343087 might be a missing prime \\ Composite
5021050770919 might be a missing prime \\ Prime
Total primes found between 5000000000000 and 7000000000000: 67986027154
Grand Total of primes found and missing primes: 67986027155 \\ Matches Primesieve!!!
real 2534m32.083s
user 39787m37.665s
sys 19m41.357s
\\ Primesieve
david@HPLaptop:~/mar31/nov14$ primesieve 5000000000000 7000000000000 -c
Sieve size = 256 KiB
Threads = 20
100%
Seconds: 73.245
Primes: 67986027155
============================= below added Nov 16 5:20am ======================
bernierd121@instance-20241109-155454:~$ cat data97
Total primes found between 9000000000000 and 10000000000000: 33465182731
Total missing primes between 9000000000000 and 10000000000000: 0
Grand total of primes found and missing primes between 9000000000000 and 10000000000000: 33465182731 \\ matches primesieve!
\\ primesieve
david@HPLaptop:~/mar31/nov14$ primesieve 9000000000000 10000000000000 -c
Sieve size = 256 KiB
Threads = 20
100%
Seconds: 34.450
Primes: 33465182731
====================== below added Nov 16 10:30 pm ==================
bernierd121@instance-20241109-155454:~$ cat data99
Total primes found between 10000000000000 and 11000000000000: 33353349498
Total missing primes between 10000000000000 and 11000000000000: 0
Grand total of primes found and missing primes between 10000000000000 and 11000000000000: 33353349498 \\ Correct
\\ primesieve
$ primesieve 10000000000000 11000000000000 -c
Sieve size = 256 KiB
Threads = 20
100%
Seconds: 70.610
Primes: 33353349498
===================== below added Nov 18 9:10 am ========================
bernierd121@instance-20241109-155454:~$ cat data103
13555896771509 is a missing prime
Total primes found between 13000000000000 and 15000000000000: 66073860520
Total missing primes between 13000000000000 and 15000000000000: 1
Grand total of primes found and missing primes between 13000000000000 and 15000000000000: 66073860521 \\ Matches primesieve!
\\ primesieve
david@HPLaptop:~$ primesieve 13000000000000 15000000000000 -c
Sieve size = 256 KiB
Threads = 20
100%
Seconds: 165.132
Primes: 66073860521
========================== below added Nov 18 3:20 pm ======================
david@HPLaptop:~/mar31/nov15$ time ./a.out
11166607436291 is a missing prime
Total primes found between 11000000000000 and 13000000000000: 66412724273
Total missing primes between 11000000000000 and 13000000000000: 1
Grand total of primes found and missing primes between 11000000000000 and 13000000000000: 66412724274 \\ Correct!
real 2953m14.610s
user 40547m17.623s
sys 18m52.624s
david@HPLaptop:~/mar31/nov15$ primesieve 11000000000000 13000000000000 -c
Sieve size = 256 KiB
Threads = 20
100%
Seconds: 74.325
Primes: 66412724274
1 comment
Comments are closed.