Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

Difference between revisions of "Pocklington's theorem"

From Prime-Wiki
Jump to: navigation, search
(restored)
 
(Adding to new subcategory)
 
(One intermediate revision by one other user not shown)
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]]
*[http://homepage2.nifty.com/m_kamada/math/pock.htm 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.
+
*[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:Deterministic primality tests]]

Latest revision as of 01:15, 11 August 2024

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

Let [math]\displaystyle{ 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]\displaystyle{ a^{n-1}\,\equiv\,1\,\pmod{n} }[/math] and [math]\displaystyle{ gcd(a^{(N-1)/q}-1,N) = 1 }[/math], then each prime factor q of N has the form [math]\displaystyle{ 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]\displaystyle{ N = fr + 1 }[/math], where [math]\displaystyle{ 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]\displaystyle{ x_p^{N-1}\,\equiv\,1\,\pmod{N} }[/math]
[math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ f^3 \gt n }[/math], Selfridge's test can be used to prove primality. If [math]\displaystyle{ f^{10} \gt n^3 }[/math], the Konyagin-Pomerance Test can be used. If [math]\displaystyle{ 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]\displaystyle{ f^4 \lt n }[/math], there is no known algorithm which enhances Pocklington's theorem.

External links