Pocklington's algorithm

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

${\displaystyle x^{2}\equiv a{\pmod {p}},}${\displaystyle 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.^[1]

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

Inputs:

• p, an odd prime
• a, an integer which is a quadratic residue ${\displaystyle {\pmod {p}}}${\displaystyle {\pmod {p}}}.

Outputs:

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

Pocklington separates 3 different cases for p:

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

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

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

The third case, if ${\displaystyle p=8m+1}${\displaystyle p=8m+1}, put ${\displaystyle D\equiv -a}${\displaystyle D\equiv -a}, so the equation to solve becomes ${\displaystyle x^{2}+D\equiv 0}${\displaystyle x^{2}+D\equiv 0}. Now find by trial and error ${\displaystyle t_{1}}${\displaystyle t_{1}} and ${\displaystyle u_{1}}${\displaystyle u_{1}} so that ${\displaystyle N=t_{1}^{2}-Du_{1}^{2}}${\displaystyle N=t_{1}^{2}-Du_{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}},\qquad u_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}-(t_{1}-u_{1}{\sqrt {D}})^{n}}{2{\sqrt {D}}}}}${\displaystyle 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:

${\displaystyle 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}}${\displaystyle 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 ${\displaystyle 4m+1}${\displaystyle 4m+1} (which is true if p is of the form ${\displaystyle 8m+1}${\displaystyle 8m+1}), D is a quadratic residue and ${\displaystyle t_{p}\equiv t_{1}^{p}\equiv t_{1},\quad u_{p}\equiv u_{1}^{p}D^{(p-1)/2}\equiv u_{1}}${\displaystyle 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

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

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

Let ${\displaystyle p-1=2r}${\displaystyle p-1=2r}. Then ${\displaystyle 0\equiv u_{p-1}\equiv 2t_{r}u_{r}}${\displaystyle 0\equiv u_{p-1}\equiv 2t_{r}u_{r}}. This means that either ${\displaystyle t_{r}}${\displaystyle t_{r}} or ${\displaystyle u_{r}}${\displaystyle u_{r}} is divisible by p. If it is ${\displaystyle u_{r}}${\displaystyle u_{r}}, put ${\displaystyle r=2s}${\displaystyle r=2s} and proceed similarly with ${\displaystyle 0\equiv 2t_{s}u_{s}}${\displaystyle 0\equiv 2t_{s}u_{s}}. Not every ${\displaystyle u_{i}}${\displaystyle u_{i}} is divisible by p, for ${\displaystyle u_{1}}${\displaystyle u_{1}} is not. The case ${\displaystyle u_{m}\equiv 0}${\displaystyle u_{m}\equiv 0} with m odd is impossible, because ${\displaystyle t_{m}^{2}-Du_{m}^{2}\equiv N^{m}}${\displaystyle t_{m}^{2}-Du_{m}^{2}\equiv N^{m}} holds and this would mean that ${\displaystyle t_{m}^{2}}${\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}${\displaystyle t_{l}\equiv 0} for a particular l. This gives ${\displaystyle -Du_{l}^{2}\equiv N^{l}}${\displaystyle -Du_{l}^{2}\equiv N^{l}}, and because ${\displaystyle -D}${\displaystyle -D} is a quadratic residue, l must be even. Put ${\displaystyle l=2k}${\displaystyle l=2k}. Then ${\displaystyle 0\equiv t_{l}\equiv t_{k}^{2}+Du_{k}^{2}}${\displaystyle 0\equiv t_{l}\equiv t_{k}^{2}+Du_{k}^{2}}. So the solution of ${\displaystyle x^{2}+D\equiv 0}${\displaystyle x^{2}+D\equiv 0} is got by solving the linear congruence ${\displaystyle u_{k}x\equiv \pm t_{k}}${\displaystyle u_{k}x\equiv \pm t_{k}}.

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

${\displaystyle x^{2}\equiv 43{\pmod {47}}.}${\displaystyle x^{2}\equiv 43{\pmod {47}}.}

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

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

Solve the congruence

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

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

Solve the congruence ${\displaystyle x^{2}\equiv 13{\pmod {17}}}${\displaystyle x^{2}\equiv 13{\pmod {17}}}. For this, write ${\displaystyle x^{2}-13=0}${\displaystyle x^{2}-13=0}. First find a ${\displaystyle t_{1}}${\displaystyle t_{1}} and ${\displaystyle u_{1}}${\displaystyle u_{1}} such that ${\displaystyle t_{1}^{2}+13u_{1}^{2}}${\displaystyle t_{1}^{2}+13u_{1}^{2}} is a quadratic nonresidue. Take for example ${\displaystyle t_{1}=3,u_{1}=1}${\displaystyle t_{1}=3,u_{1}=1}. Now find ${\displaystyle t_{8}}${\displaystyle t_{8}}, ${\displaystyle u_{8}}${\displaystyle u_{8}} by computing

${\displaystyle t_{2}=t_{1}t_{1}+13u_{1}u_{1}=9-13=-4\equiv 13{\pmod {17}},}${\displaystyle t_{2}=t_{1}t_{1}+13u_{1}u_{1}=9-13=-4\equiv 13{\pmod {17}},}

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

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

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

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

• Modular arithmetic
• Number theoretic algorithms