Pocklington's algorithm is a technique for solving a congruence of the form
![{\displaystyle x^{2}\equiv a{\pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9010d7b9e12f7d5f41a6e03daa23dd3ac547fd6f)
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]
(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.
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
![{\displaystyle t_{1}\equiv t_{p-1}t_{1}+Du_{p-1}u_{1}\quad {\mbox{and}}\quad u_{1}\equiv t_{p-1}u_{1}+t_{1}u_{p-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b99472bbd10f1cad7f58e686eba1cc8755977d1)
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
.
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.
![{\displaystyle x^{2}\equiv 43{\pmod {47}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8969dcb441670b771f8481742727ff181dab3158)
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.
Solve the congruence
![{\displaystyle x^{2}\equiv 18{\pmod {23}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd7d189237e6e96cdb3bae26028e2f9b2d3e0cb0)
The modulus is 23. This is
, so
. The solution should be
, which is indeed true:
.
Solve the congruence
![{\displaystyle x^{2}\equiv 10{\pmod {13}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97ac38487ba2c5567de9c643a1cac1d991ed528a)
The modulus is 13. This is
, so
. Now verifying
. So the solution is
. This is indeed true:
.
Solve the congruence
. For this, write
. First find a
and
such that
is a quadratic nonresidue. Take for example
. Now find
,
by computing
![{\displaystyle t_{2}=t_{1}t_{1}+13u_{1}u_{1}=9-13=-4\equiv 13{\pmod {17}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d2b3c0f13c3d9a871ecdb7a508273de031fc4b7)
![{\displaystyle u_{2}=t_{1}u_{1}+t_{1}u_{1}=3+3\equiv 6{\pmod {17}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4220f1dcff25bb0533845721eda7c68464a34045)
And similarly
such that
Since
, the equation
which leads to solving the equation
. This has solution
. Indeed,
.
- Leonard Eugene Dickson, "History Of The Theory Of Numbers" vol 1 p 222, Chelsea Publishing 1952
- ^ H.C. Pocklington, Proceedings of the Cambridge Philosophical Society, Volume 19, pages 57–58