Pocklington's Algorithm

Pocklington's algorithm is a technique for solving a congruence of the form

:$x^2 \equiv a \pmod p,$

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.H.C. Pocklington, Proceedings of the Cambridge Philosophical Society, Volume 19, pages 57–58

The algorithm

(Note: all $\equiv$ are taken to mean $\pmod p$, unless indicated otherwise.)

Inputs:
* ''p'', an odd prime
* ''a'', an integer which is a quadratic residue $\pmod p$.

Outputs:
* ''x'', an integer satisfying $x^2 \equiv a$. Note that if ''x'' is a solution, −''x'' is a solution as well and since ''p'' is odd, $x \neq -x$. So there is always a second solution when one is found.

Solution method

Pocklington separates 3 different cases for ''p'':

The first case, if $p=4m+3$, with $m \in \mathbb$, the solution is $x \equiv \pm a^$.

The second case, if $p=8m+5$, with $m \in \mathbb$ and
# $a^ \equiv 1$, the solution is $x \equiv \pm a^$.
# $a^ \equiv -1$, 2 is a (quadratic) non-residue so $4^ \equiv -1$. This means that $(4a)^ \equiv 1$ so $y \equiv \pm (4a)^$ is a solution of $y^2 \equiv 4a$. Hence $x \equiv \pm y/2$ or, if ''y'' is odd, $x \equiv \pm (p+y)/2$.

The third case, if $p=8m+1$, put $D \equiv -a$, so the equation to solve becomes $x^2 + D \equiv 0$. Now find by trial and error $t_1$ and $u_1$ so that $N = t_1^2 - D u_1^2$ is a quadratic non-residue. Furthermore, let
:$t_n = \frac, \qquad u_n = \frac$.
The following equalities now hold:
:$t_ = t_m t_n + D u_m u_n, \quad u_ = t_m u_n + t_n u_m \quad \mbox \quad t_n^2 - D u_n^2 = N^n$.
Supposing that ''p'' is of the form $4m+1$ (which is true if ''p'' is of the form $8m+1$), ''D'' is a quadratic residue and $t_p \equiv t_1^p \equiv t_1, \quad u_p \equiv u_1^p D^ \equiv u_1$. Now the equations
: $t_1 \equiv t_ t_1 + D u_ u_1 \quad \mbox \quad u_1 \equiv t_ u_1 + t_1 u_$
give a solution $t_ \equiv 1, \quad u_ \equiv 0$.

Let $p-1 = 2r$. Then $0 \equiv u_ \equiv 2 t_r u_r$. This means that either $t_r$ or $u_r$ is divisible by ''p''. If it is $u_r$, put $r=2s$ and proceed similarly with $0 \equiv 2 t_s u_s$. Not every $u_i$ is divisible by ''p'', for $u_1$ is not. The case $u_m \equiv 0$ with ''m'' odd is impossible, because $t_m^2 - D u_m^2 \equiv N^m$ holds and this would mean that $t_m^2$ is congruent to a quadratic non-residue, which is a contradiction. So this loop stops when $t_l \equiv 0$ for a particular ''l''. This gives $-D u_l^2 \equiv N^l$, and because $-D$ is a quadratic residue, ''l'' must be even. Put $l = 2k$. Then $0 \equiv t_l \equiv t_k^2 + D u_k^2$. So the solution of $x^2 + D \equiv 0$ is got by solving the linear congruence $u_k x \equiv \pm t_k$.

Examples

The following are 4 examples, corresponding to the 3 different cases in which Pocklington divided forms of ''p''. All $\equiv$ are taken with the modulus in the example.

Example 0

:$x^2 \equiv 43 \pmod .$

This is the first case, according to the algorithm,
$x \equiv 43^ = 43^ \equiv 2$, but then $x^2=2^2=4$ 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
:$x^2 \equiv 18 \pmod .$
The modulus is 23. This is $23 = 4 \cdot 5 + 3$, so $m=5$. The solution should be $x \equiv \pm 18^6 \equiv \pm 8\pmod$, which is indeed true: $(\pm 8)^2 \equiv 64 \equiv 18\pmod$.

Example 2

Solve the congruence
:$x^2 \equiv 10 \pmod.$
The modulus is 13. This is $13 = 8 \cdot 1 + 5$, so $m=1$. Now verifying $10^ \equiv 10^3 \equiv -1\pmod$. So the solution is $x \equiv \pm y/2 \equiv \pm (4a)^/2 \equiv \pm 800 \equiv \pm 7\pmod$. This is indeed true: $(\pm 7)^2 \equiv 49 \equiv 10\pmod$.

Example 3

Solve the congruence $x^2 \equiv 13 \pmod$. For this, write $x^2 -13 =0$. First find a $t_1$ and $u_1$ such that $t_1^2 + 13u_1^2$ is a quadratic nonresidue. Take for example $t_1=3, u_1 = 1$. Now find $t_8$, $u_8$ by computing
:$t_2 = t_1 t_1 + 13u_1u_1 = 9-13 = -4 \equiv 13\pmod ,$
:$u_2 = t_1u_1 + t_1u_1 = 3+3 \equiv 6\pmod .$
And similarly $t_4 = -299 \equiv 7 \pmod , u_4=156 \equiv 3\pmod$ such that $t_8=-68 \equiv 0\pmod , u_8 = 42 \equiv 8\pmod .$

Since $t_8 = 0$, the equation $0 \equiv t_4^2 + 13u_4^2 \equiv 7^2 - 13 \cdot 3^2\pmod$ which leads to solving the equation $3x \equiv \pm 7\pmod$. This has solution $x \equiv \pm 8\pmod$. Indeed, $(\pm 8)^2 = 64 \equiv 13\pmod$.

References

* Leonard Eugene Dickson, "History Of The Theory Of Numbers" vol 1 p 222, Chelsea Publishing 1952

{{number theoretic algorithms

Modular arithmetic
Number theoretic algorithms