# Thread: Primality Tests

1. 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:

2.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•