Welcome to our community

Be a part of something great, join today!

Primality Tests

mathbalarka

Well-known member
MHB Math Helper
Mar 22, 2013
573
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\).

Comments and questions should be posted here:

http://mathhelpboards.com/commentary-threads-53/commentary-primality-tests-4210.html
 
Last edited: