Pocklington's algorithm is a technique for solving a congruence of the form
x 2 ≡ a ( mod p ) , {\displaystyle x^{2}\equiv a{\pmod {p}},}
where x and a are integers and a is a quadratic residue. The algorithm is one of the first efficient methods to solve such a congruence. It was described by H.C. Pocklington in 1917.
The algorithm (Note: all ≡ {\displaystyle \equiv } are taken to mean ( mod p ) {\displaystyle {\pmod {p}}} , unless indicated otherwise.) Inputs:
p, an odd prime a, an integer which is a quadratic residue ( mod p ) {\displaystyle {\pmod {p}}} . Outputs:
x, an integer satisfying x 2 ≡ a {\displaystyle x^{2}\equiv a} . Note that if x is a solution, −x is a solution as well and since p is odd, x ≠ − x {\displaystyle x\neq -x} . So there is always a second solution when one is found.
Solution method Pocklington separates 3 different cases for p: The first case, if p = 4 m + 3 {\displaystyle p=4m+3} , with m ∈ N {\displaystyle m\in \mathbb {N} } , the solution is x ≡ ± a m + 1 {\displaystyle x\equiv \pm a^{m+1}} . The second case, if p = 8 m + 5 {\displaystyle p=8m+5} , with m ∈ N {\displaystyle m\in \mathbb {N} } and
a 2 m + 1 ≡ 1 {\displaystyle a^{2m+1}\equiv 1} , the solution is x ≡ ± a m + 1 {\displaystyle x\equiv \pm a^{m+1}} .
a 2 m + 1 ≡ − 1 {\displaystyle a^{2m+1}\equiv -1} , 2 is a (quadratic) non-residue so 4 2 m + 1 ≡ − 1 {\displaystyle 4^{2m+1}\equiv -1} . This means that ( 4 a ) 2 m + 1 ≡ 1 {\displaystyle (4a)^{2m+1}\equiv 1} so y ≡ ± ( 4 a ) m + 1 {\displaystyle y\equiv \pm (4a)^{m+1}} is a solution of y 2 ≡ 4 a {\displaystyle y^{2}\equiv 4a} . Hence x ≡ ± y / 2 {\displaystyle x\equiv \pm y/2} or, if y is odd, x ≡ ± ( p + y ) / 2 {\displaystyle x\equiv \pm (p+y)/2} . The third case, if p = 8 m + 1 {\displaystyle p=8m+1} , put D ≡ − a {\displaystyle D\equiv -a} , so the equation to solve becomes x 2 + D ≡ 0 {\displaystyle x^{2}+D\equiv 0} . Now find by trial and error t 1 {\displaystyle t_{1}} and u 1 {\displaystyle u_{1}} so that N = t 1 2 − D u 1 2 {\displaystyle N=t_{1}^{2}-Du_{1}^{2}} is a quadratic non-residue. Furthermore, let
… excerpt ends here. Continue reading the full article.
