Pocklington's algorithm is a technique for solving a congruence of the form
x 2 ≡ a ( mod 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.
(Note: all ≡ are taken to mean ( mod p ) , unless indicated otherwise.)
Inputs:
p, an odd primea, an integer which is a quadratic residue ( mod p ) .Outputs:
x, an integer satisfying x 2 ≡ a . Note that if x is a solution, −x is a solution as well and since p is odd, x ≠ − x . So there is always a second solution when one is found.Pocklington separates 3 different cases for p:
The first case, if p = 4 m + 3 , with m ∈ N , the solution is x ≡ ± a m + 1 .
The second case, if p = 8 m + 5 , with m ∈ N and
- a 2 m + 1 ≡ 1 , the solution is x ≡ ± a m + 1 .
- a 2 m + 1 ≡ − 1 , 2 is a (quadratic) non-residue so 4 2 m + 1 ≡ − 1 . This means that ( 4 a ) 2 m + 1 ≡ 1 so y ≡ ± ( 4 a ) m + 1 is a solution of y 2 ≡ 4 a . Hence x ≡ ± y / 2 or, if y is odd, x ≡ ± ( p + y ) / 2 .
The third case, if p = 8 m + 1 , put D ≡ − a , so the equation to solve becomes x 2 + D ≡ 0 . Now find by trial and error t 1 and u 1 so that N = t 1 2 − D u 1 2 is a quadratic non-residue. Furthermore let
t n = ( t 1 + u 1 D ) n + ( t 1 − u 1 D ) n 2 , u n = ( t 1 + u 1 D ) n − ( t 1 − u 1 D ) n 2 D .
The following equalities now hold:
t m + n = t m t n + D u m u n , u m + n = t m u n + t n u m and t n 2 − D u n 2 = N n .
Supposing that p is of the form 4 m + 1 (which is true if p is of the form 8 m + 1 ), D is a quadratic residue and t p ≡ t 1 p ≡ t 1 , u p ≡ u 1 p D ( p − 1 ) / 2 ≡ u 1 . Now the equations
t 1 ≡ t p − 1 t 1 + D u p − 1 u 1 and u 1 ≡ t p − 1 u 1 + t 1 u p − 1 give a solution t p − 1 ≡ 1 , u p − 1 ≡ 0 .
Let p − 1 = 2 r . Then 0 ≡ u p − 1 ≡ 2 t r u r . This means that either t r or u r is divisible by p. If it is u r , put r = 2 s and proceed similarly with 0 ≡ 2 t s u s . Not every u i is divisible by p, for u 1 is not. The case u m ≡ 0 with m odd is impossible, because t m 2 − D u m 2 ≡ N m holds and this would mean that t m 2 is congruent to a quadratic non-residue, which is a contradiction. So this loop stops when t l ≡ 0 for a particular l. This gives − D u l 2 ≡ N l , and because − D is a quadratic residue, l must be even. Put l = 2 k . Then 0 ≡ t l ≡ t k 2 + D u k 2 . So the solution of x 2 + D ≡ 0 is got by solving the linear congruence u k x ≡ ± t k .
The following are 3 examples, corresponding to the 3 different cases in which Pocklington divided forms of p. All ≡ are taken with the modulus in the example.
Solve the congruence
x 2 ≡ 18 ( mod 23 ) . The modulus is 23. This is 23 = 4 ⋅ 5 + 3 , so m = 5 . The solution should be x ≡ ± 18 6 ≡ ± 8 ( mod 23 ) , which is indeed true: ( ± 8 ) 2 ≡ 64 ≡ 18 ( mod 23 ) .
Solve the congruence
x 2 ≡ 10 ( mod 13 ) . The modulus is 13. This is 13 = 8 ⋅ 1 + 5 , so m = 1 . Now verifying 10 2 m + 1 ≡ 10 3 ≡ − 1 ( mod 13 ) . So the solution is x ≡ ± y / 2 ≡ ± ( 4 a ) 2 / 2 ≡ ± 800 ≡ ± 7 ( mod 13 ) . This is indeed true: ( ± 7 ) 2 ≡ 49 ≡ 10 ( mod 13 ) .
Solve the congruence x 2 ≡ 13 ( mod 17 ) . For this, write x 2 − 13 = 0 . First find a t 1 and u 1 such that t 1 2 + 13 u 1 2 is a quadratic nonresidue. Take for example t 1 = 3 , u 1 = 1 . Now find t 8 , u 8 by computing
t 2 = t 1 t 1 + 13 u 1 u 1 = 9 − 13 = − 4 ≡ 13 ( mod 17 ) , ,
u 2 = t 1 u 1 + t 1 u 1 = 3 + 3 ≡ 6 ( mod 17 ) . And similarly t 4 = − 299 ≡ 7 ( mod 17 ) u 4 = 156 ≡ 3 ( mod 17 ) such that t 8 = − 68 ≡ 0 ( mod 17 ) u 8 = 42 ≡ 8 ( mod 17 ) .
Since t 8 = 0 , the equation 0 ≡ t 4 2 + 13 u 4 2 ≡ 7 2 − 13 ⋅ 3 2 ( mod 17 ) which leads to solving the equation 3 x ≡ ± 7 ( mod 17 ) . This has solution x ≡ ± 8 ( mod 17 ) . Indeed, ( ± 8 ) 2 = 64 ≡ 13 ( mod 17 ) .
