Pocklington's algorithm

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

$x^2\equiv a(\mathrm{mod}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 $(\mathrm{mod}p)$, unless indicated otherwise.)

Inputs:

• p, an odd prime
• a, an integer which is a quadratic residue $(\mathrm{mod}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\ne -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{\mathbb{N}}$, the solution is $x\equiv \pm a^{m+1}$.

The second case, if $p=8m+5$, with $m\in \mathbb{\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-D{u}_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},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+D{u}_m{u}_n,u_{m+n}=t_m{u}_n+t_n{u}_m\text{and}{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,u_p\equiv u_1^p{D}^{(p-1)/2}\equiv u_1$. Now the equations

$t_1\equiv t_{p-1}{t}_1+D{u}_{p-1}{u}_1\text{and}{u}_1\equiv t_{p-1}{u}_1+t_1{u}_{p-1}$

give a solution $t_{p-1}\equiv 1,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-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(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}23)$, which is indeed true: $(\pm 8{)}^2\equiv 64\equiv 18(\mathrm{mod}23)$.

Example 2

Solve the congruence

$x^2\equiv 10(\mathrm{mod}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(\mathrm{mod}13)$. So the solution is $x\equiv \pm y/2\equiv \pm (4a{)}^2/2\equiv \pm 800\equiv \pm 7(\mathrm{mod}13)$. This is indeed true: $(\pm 7{)}^2\equiv 49\equiv 10(\mathrm{mod}13)$.

Example 3

Solve the congruence $x^2\equiv 13(\mathrm{mod}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(\mathrm{mod}17),$

$u_2=t_1{u}_1+t_1{u}_1=3+3\equiv 6(\mathrm{mod}17).$

And similarly $t_4=-299\equiv 7(\mathrm{mod}17),u_4=156\equiv 3(\mathrm{mod}17)$ such that $t_8=-68\equiv 0(\mathrm{mod}17),u_8=42\equiv 8(\mathrm{mod}17).$

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

References

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