# Difference between revisions of "Pocklington's theorem"

(restored) |
(update M.Kamada website) |
||

Line 19: | Line 19: | ||

==External links== | ==External links== | ||

*[[Wikipedia:Pocklington_primality_test#Pocklington_criterion|Pocklington primality test]] | *[[Wikipedia:Pocklington_primality_test#Pocklington_criterion|Pocklington primality test]] | ||

− | *[ | + | *[https://stdkmd.net/nrr/pock/ Primality proving program based on Pocklington's theorem] by Makoto Kamada. It includes a program written in C language that proves primality of numbers of several thousand digits using this theorem. |

[[Category:Primality tests]] | [[Category:Primality tests]] |

## Latest revision as of 19:51, 30 August 2019

The **Pocklington's theorem** invented by H. C. Pocklington in 1914, which is a primality test for the number *N*, states:

- Let [math]N-1 = q^k\,R[/math] where
*q*is a prime which does not divide*R*. If there is an integer*a*such that [math]a^{n-1}\,\equiv\,1\,\pmod{n}[/math] and [math]gcd(a^{(N-1)/q}-1,N) = 1[/math], then each prime factor*q*of*N*has the form [math]q^kr+1[/math].

From the previous theorem it can be deduced a primality test when only a partial factorization of N-1 is known:

Let [math]N = fr + 1[/math], where [math]0\,\lt \,r\,\le \,f+1[/math]. The value *N* is prime if, for every prime divisor *p* of *f*, there is an integer *x_p* such that:

- [math]x_p^{N-1}\,\equiv\,1\,\pmod{N}[/math]
- [math]gcd(x_p^{(N-1)/p}\,-1,\,N) = 1[/math]

If *f < r*, Pocklington's theorem does not return a primality proof, but there is still some hope of proving primality. The theorem implies that every factor *p* of *N* satisfies

- [math]p \equiv 1 \pmod{f}[/math]

There are several algorithms which can be used to finish the proof, provided *f* is big enough. If [math]f^3 \gt n[/math], Selfridge's test can be used to prove primality. If [math]f^{10} \gt n^3[/math], the Konyagin-Pomerance Test can be used. If [math]f^4 \gt n[/math], there is a polynomial-time algorithm, due to Coppersmith and Howgrave-Graham for carrying out a complete search for divisors congruent to *1 modulo f*.

Each of these algorithms is more complicated than the last, so it is best to use the simplest one which will work for the value of *f* you have. For [math]f^4 \lt n[/math], there is no known algorithm which enhances Pocklington's theorem.

## External links

- Pocklington primality test
- Primality proving program based on Pocklington's theorem by Makoto Kamada. It includes a program written in C language that proves primality of numbers of several thousand digits using this theorem.