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.
Inputs: Outputs: Pocklington separates 3 different cases for p: The first case, if
, so the equation to solve becomes
Now find by trial and error
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
and proceed similarly with
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
is a quadratic residue, l must be even.
is got by solving the linear congruence
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.
This is the first case, according to the algorithm,
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.
Solve the congruence The modulus is 23.
Solve the congruence The modulus is 13.
Solve the congruence
is a quadratic nonresidue.
by computing And similarly
which leads to solving the equation