# Primality Tests

#### mathbalarka

##### Well-known member
MHB Math Helper
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: