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

${\displaystyle x^2\equiv a(\mathrm{mod}p),}$

wherex anda are integers anda is aquadratic residue.

The algorithm is one of the first efficient methods to solve such a congruence. It was described byH.C. Pocklington in 1917.^[1]

(Note: all${\displaystyle \equiv }$ are taken to mean${\displaystyle (\mathrm{mod}p)}$, unless indicated otherwise.)

Inputs:

• p, an oddprime
• a, an integer which is a quadratic residue${\displaystyle (\mathrm{mod}p)}$.

Outputs:

• x, an integer satisfying${\displaystyle x^2\equiv a}$. Note that ifx is a solution, −x is a solution as well and sincep is odd,${\displaystyle x\ne -x}$. So there is always a second solution when one is found.

Pocklington separates 3 different cases forp:

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

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

1. ${\displaystyle a^{2m+1}\equiv 1}$, the solution is${\displaystyle x\equiv \pm a^{m+1}}$.
2. ${\displaystyle a^{2m+1}\equiv -1}$, 2 is a (quadratic) non-residue so${\displaystyle 4^{2m+1}\equiv -1}$. This means that${\displaystyle (4a{)}^{2m+1}\equiv 1}$ so${\displaystyle y\equiv \pm (4a{)}^{m+1}}$ is a solution of${\displaystyle y^2\equiv 4a}$. Hence${\displaystyle x\equiv \pm y/2}$ or, ify is odd,${\displaystyle x\equiv \pm (p+y)/2}$.

The third case, if${\displaystyle p=8m+1}$, put${\displaystyle D\equiv -a}$, so the equation to solve becomes${\displaystyle x^2+D\equiv 0}$. Now find by trial and error${\displaystyle t_1}$ and${\displaystyle u_1}$ so that${\displaystyle N=t_1^2-D{u}_1^2}$ is a quadratic non-residue. Furthermore, let

${\displaystyle 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:

${\displaystyle 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 thatp is of the form${\displaystyle 4m+1}$ (which is true ifp is of the form${\displaystyle 8m+1}$),D is a quadratic residue and${\displaystyle 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

${\displaystyle 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${\displaystyle t_{p-1}\equiv 1,u_{p-1}\equiv 0}$.

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

The following are 4 examples, corresponding to the 3 different cases in which Pocklington divided forms ofp. All${\displaystyle \equiv }$ are taken with themodulus in the example.

${\displaystyle x^2\equiv 43(\mathrm{mod}47).}$

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

Solve the congruence

${\displaystyle x^2\equiv 18(\mathrm{mod}23).}$

The modulus is 23. This is${\displaystyle 23=4\cdot 5+3}$, so${\displaystyle m=5}$. The solution should be${\displaystyle x\equiv \pm {18}^6\equiv \pm 8(\mathrm{mod}23)}$, which is indeed true:${\displaystyle (\pm 8{)}^2\equiv 64\equiv 18(\mathrm{mod}23)}$.

Solve the congruence

${\displaystyle x^2\equiv 10(\mathrm{mod}13).}$

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

Solve the congruence${\displaystyle x^2\equiv 13(\mathrm{mod}17)}$. For this, write${\displaystyle x^2-13=0}$. First find a${\displaystyle t_1}$ and${\displaystyle u_1}$ such that${\displaystyle t_1^2+13u_1^2}$ is a quadratic nonresidue. Take for example${\displaystyle t_1=3,u_1=1}$. Now find${\displaystyle t_8}$,${\displaystyle u_8}$ by computing

${\displaystyle t_2=t_1{t}_1+13u_1{u}_1=9-13=-4\equiv 13(\mathrm{mod}17),}$

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

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

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

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

• Modular arithmetic
• Number theoretic algorithms