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/720ace3c30d1185d70cdb1e1a5902a0e8a8b97c2)
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]
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
![{\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
.
Examples
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.
Example 1
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:
.
Example 2
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:
.
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
,
![{\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/6907db7753332cb4c8ab62d1e7eeb1cb0d426865)
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