Pocklington's algorithm
Pocklington's algorithm is a technique for solving a congruence of the form
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.^{[1]}
Contents
The algorithm
(Note: all are taken to mean , unless indicated otherwise.)
Inputs:
- p, an odd prime
- a, an integer which is a quadratic residue .
Outputs:
- x, an integer satisfying . Note that if x is a solution, −x is a solution as well and since p is odd, . So there is always a second solution when one is found.
Solution method
Pocklington separates 3 different cases for p:
The first case, if , with , the solution is .
The second case, if , with and
- , the solution is .
- , 2 is a (quadratic) non-residue so . This means that so is a solution of . Hence or, if y is odd, .
The third case, if , put , so the equation to solve becomes . Now find by trial and error and so that is a quadratic non-residue. Furthermore, let
- .
The following equalities now hold:
- .
Supposing that p is of the form (which is true if p is of the form ), D is a quadratic residue and . Now the equations
give a solution .
Let . Then . This means that either or is divisible by p. If it is , put and proceed similarly with . Not every is divisible by p, for is not. The case with m odd is impossible, because holds and this would mean that is congruent to a quadratic non-residue, which is a contradiction. So this loop stops when for a particular l. This gives , and because is a quadratic residue, l must be even. Put . Then . So the solution of is got by solving the linear congruence .
Examples
The following are 4 examples, corresponding to the 3 different cases in which Pocklington divided forms of p. All are taken with the modulus in the example.
Example 0
This is the first case, according to the algorithm, , but then not 43, so we should not apply the algorithm at all. The reason why the algorithm is not applicable is that a=43 is a quadratic non residue for p=47.
Example 1
Solve the congruence
The modulus is 23. This is , so . The solution should be , which is indeed true: .
Example 2
Solve the congruence
The modulus is 13. This is , so . Now verifying . So the solution is . This is indeed true: .
Example 3
Solve the congruence . For this, write . First find a and such that is a quadratic nonresidue. Take for example . Now find , by computing
- ,
And similarly such that
Since , the equation which leads to solving the equation . This has solution . Indeed, .
References
- ^ H.C. Pocklington, Proceedings of the Cambridge Philosophical Society, Volume 19, pages 57–58