Tutorial on 3 Common Primality Tests

[mathbalarka]

Here are three $n-1$ primality test I would like to describe in this thread. The first one works for the 60% of the cases, the second is usually used when the first fails and the third if first and second both fails.

Pocklington's Test

Suppose q divides n - 1 and \(\displaystyle q > \sqrt{n}-1\). If there exists an \(\displaystyle a\) such that \(\displaystyle a^{n-1} = 1 \pmod{n}\) and \(\displaystyle \mathrm{gcd}(a^{(n-1)/q} - 1, n)\) then n is a certified prime.

There is a generalization of Pocklington which uses a factor of n - 1 and covers more prime numbers, but I never needed it so I wouldn't post it now.

Brillhart-Lehmer-Selfridge Test

Suppose \(\displaystyle n - 1 = F \cdot R\) and there exists an \(\displaystyle a\) such that \(\displaystyle a^{n-1} = 1 \pmod{n}\) and \(\displaystyle \mathrm{gcd}(a^{(n-1)/q} - 1, n)\) for each prime q dividing F where \(\displaystyle n^{1/3} \le F < \sqrt{n}\). If n can be expressed in base F as \(\displaystyle c_2 F^2 + c_1 F + 1\) where both of the co-efficients are in the interval \(\displaystyle [0, F-1]\) then n is a certified prime if and only if \(\displaystyle c_1 ^2 - 4 c_2\) is not a perfect square.

Konyagin-Pomerance Test

Suppose \(\displaystyle n - 1 = F \cdot R\) and there exists an \(\displaystyle a\) such that \(\displaystyle a^{n-1} = 1 \pmod{n}\) and \(\displaystyle \mathrm{gcd}(a^{(n-1)/q} - 1, n)\) for each prime q dividing F where \(\displaystyle n^{3/10} \le F < n^{1/3}\). If n can be expressed in base F as \(\displaystyle c_3 F^3 + c_2 F^2 + c_1 F + 1\) and let \(\displaystyle c_4 = c_3 F + c_2\) then n is a certified prime if and only if \(\displaystyle (c_1 + t \cdot F)^2 + 4t - 4 c_4\) is not a perfect square and the polynomial \(\displaystyle v x^3 + (u \cdot F - c_1 v) x^2 + (c_4 v - d \cdot F + u) x - d\) over \(\displaystyle \mathbb{Z}[x]\) has no rational root a such that a * F + 1 is a non-trivial factor of n where \(\displaystyle u/v\) is a continued fraction convergent to \(\displaystyle c_1 /F\) such that v is maximal subject to \(\displaystyle v < F^2 / \sqrt{n}\) and \(\displaystyle d = \left \lfloor c_4 ^2 /F + 0.5 \right \rfloor\).

 

[Nono713]

re: Commentary for "Primality Tests"

Of course, the last two algorithms presented by Mathbalarka require the knowledge of factors of $n - 1$, which puts them in the "special purpose" category. I messed around with Pocklington's myself a few months ago, quite an interesting algorithm, and I didn't know group theory at the time I tried to find out how it worked (fun fun fun).

Of course the "gold standard" in terms of speed/accuracy is Miller-Rabin, for general-purpose primality testing (knowledge of the factorization of $n - 1$ allows one to certify primality rather easily, as noted by Mathbalarka). The AKS algorithm makes it possible to do so even without such knowledge, and is actually getting quite practical with the recent algorithmic improvements uncovered, but is still pretty unpopular.​

 

[mathbalarka]

re: Commentary for "Primality Tests"

First things first, I want to thank MarkFL for creating a commentary thread for the topic I made.

Now, for Bacterius :

Yes, the last two algorithms are for special purposes but still are useful if Pocklington fails because of the bounds on the factors issues. Miller-Rabin isn't very handy for manual calculations because of the large congruences. And I doubt whether AKS can be done manually. However, currently the best algorithm for general-purpose primality test are ECPP and fastECPP. I even considered about adding the algorithms in my post since there are a few cases where it can be manually used!

Balarka
.