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.

The algorithm

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
  1. , the solution is.
  2. , 2 is a 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 , 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,.