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.

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 {N}$, the solution is $x\equiv \pm a^{m+1}$.

The second case, if $p=8m+5$, with $m\in \mathbb {N}$ and

1. $a^{2m+1}\equiv 1$, the solution is $x\equiv \pm a^{m+1}$.
2. $a^{2m+1}\equiv -1$, 2 is a (quadratic) non-residue so $4^{2m+1}\equiv -1$. This means that $(4a)^{2m+1}\equiv 1$ so $y\equiv \pm (4a)^{m+1}$ 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}-Du_{1}^{2}$ is a quadratic non-residue. Furthermore, let

$t_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}+(t_{1}-u_{1}{\sqrt {D}})^{n}}{2}},\qquad u_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}-(t_{1}-u_{1}{\sqrt {D}})^{n}}{2{\sqrt {D}}}}$.

The following equalities now hold:

$t_{m+n}=t_{m}t_{n}+Du_{m}u_{n},\quad u_{m+n}=t_{m}u_{n}+t_{n}u_{m}\quad {\mbox{and}}\quad t_{n}^{2}-Du_{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^{(p-1)/2}\equiv u_{1}$. Now the equations

$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}$

give a solution $t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0$.

Let $p-1=2r$. Then $0\equiv u_{p-1}\equiv 2t_{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 2t_{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}-Du_{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 $-Du_{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}+Du_{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 {47}}.$

This is the first case, according to the algorithm, $x\equiv 43^{(47+1)/2}=43^{12}\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 {23}}.$

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 {23}}$, which is indeed true: $(\pm 8)^{2}\equiv 64\equiv 18{\pmod {23}}$.

Example 2

Solve the congruence

$x^{2}\equiv 10{\pmod {13}}.$

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

Example 3

Solve the congruence $x^{2}\equiv 13{\pmod {17}}$. 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_{1}u_{1}=9-13=-4\equiv 13{\pmod {17}},$

$u_{2}=t_{1}u_{1}+t_{1}u_{1}=3+3\equiv 6{\pmod {17}}.$

And similarly $t_{4}=-299\equiv 7{\pmod {17}},u_{4}=156\equiv 3{\pmod {17}}$ such that $t_{8}=-68\equiv 0{\pmod {17}},u_{8}=42\equiv 8{\pmod {17}}.$

Since $t_{8}=0$, the equation $0\equiv t_{4}^{2}+13u_{4}^{2}\equiv 7^{2}-13\cdot 3^{2}{\pmod {17}}$ which leads to solving the equation $3x\equiv \pm 7{\pmod {17}}$. This has solution $x\equiv \pm 8{\pmod {17}}$. Indeed, $(\pm 8)^{2}=64\equiv 13{\pmod {17}}$.

References

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