Pocklington algorithm

The Pocklington algorithm is a technique for solving a congruent equation of the form

x^{2}\equiv a{\pmod {p}},\,

{\ 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 effective methods for solving such an equation. The algorithm described by in 1917 ^[1] .

Content

Algorithm

( Note : All Signs $\equiv$ ${\ displaystyle \ equiv}$ mean ${\pmod {p}}$ ${\ displaystyle {\ pmod {p}}}$ unless otherwise stated.)

Entrance:

p , odd prime
a , an integer that is a binary residue ${\pmod {p}}$ ${\ displaystyle {\ pmod {p}}}$ .

Output:

x , integer satisfying identity $x^{2}\equiv a$ ${\ displaystyle x ^ {2} \ equiv a}$ . Note that if x is a solution, then - x is also a solution and, since p is odd, $x\neq -x$ ${\ displaystyle x \ neq -x}$ . Thus, there is always a second solution, if at least one is found.

Solution Method

Pocklington considers 3 different cases for p :

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

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

$a^{2m+1}\equiv 1$ ${\ displaystyle a ^ {2m + 1} \ equiv 1}$ , the decision is equal $x\equiv \pm a^{m+1}$ ${\ displaystyle x \ equiv \ pm a ^ {m + 1}}$ .
$a^{2m+1}\equiv -1$ ${\ displaystyle a ^ {2m + 1} \ equiv -1}$ , 2 is not a (quadratic) residue, so $4^{2m+1}\equiv -1$ ${\ displaystyle 4 ^ {2m + 1} \ equiv -1}$ . It means that $(4a)^{2m+1}\equiv 1$ ${\ displaystyle (4a) ^ {2m + 1} \ equiv 1}$ , so that $y\equiv \pm (4a)^{m+1}$ ${\ displaystyle y \ equiv \ pm (4a) ^ {m + 1}}$ is the solution $y^{2}\equiv 4a$ ${\ displaystyle y ^ {2} \ equiv 4a}$ . Consequently, $x\equiv \pm y/2$ ${\ displaystyle x \ equiv \ pm y / 2}$ or, if y is odd, $x\equiv \pm (p+y)/2$ ${\ displaystyle x \ equiv \ pm (p + y) / 2}$ .

Third case if $p=8m+1$ ${\ displaystyle p = 8m + 1}$ put $D\equiv -a$ ${\ displaystyle D \ equiv -a}$ so the equation turns into $x^{2}+D\equiv 0$ ${\ displaystyle x ^ {2} + D \ equiv 0}$ . Now by trial and error we find $t_{1}$ ${\ displaystyle t_ {1}}$ and $u_{1}$ ${\ displaystyle u_ {1}}$ such that $N=t_{1}^{2}-Du_{1}^{2}$ ${\ displaystyle N = t_ {1} ^ {2} -Du_ {1} ^ {2}}$ is not a quadratic residue. Next, let

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

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

{\ displaystyle u_ {n} = {\ frac {(t_ {1} + u_ {1} {\ sqrt {D}}) ^ {n} - (t_ {1} -u_ {1} {\ sqrt {D }}) ^ {n}} {2 {\ sqrt {D}}}}}

.

Now the following equalities hold:

t_{m+n}=t_{m}t_{n}+Du_{m}u_{n}

{\ displaystyle t_ {m + n} = t_ {m} t_ {n} + Du_ {m} u_ {n}}

u_{m+n}=t_{m}u_{n}+t_{n}u_{m}

{\ displaystyle u_ {m + n} = t_ {m} u_ {n} + t_ {n} u_ {m}}

t_{n}^{2}-Du_{n}^{2}=N^{n}

{\ displaystyle t_ {n} ^ {2} -Du_ {n} ^ {2} = N ^ {n}}

.

If p is $4m+1$ ${\ displaystyle 4m + 1}$ (which is true if p is $8m+1$ ${\ displaystyle 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}$ ${\ 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 equality

t_{1}\equiv t_{p-1}t_{1}+Du_{p-1}u_{1}

{\ displaystyle t_ {1} \ equiv t_ {p-1} t_ {1} + Du_ {p-1} u_ {1}}

u_{1}\equiv t_{p-1}u_{1}+t_{1}u_{p-1}

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

Let be $p-1=2r$ ${\ displaystyle p-1 = 2r}$ . Then $0\equiv u_{p-1}\equiv 2t_{r}u_{r}$ ${\ displaystyle 0 \ equiv u_ {p-1} \ equiv 2t_ {r} u_ {r}}$ . That means either $t_{r}$ ${\ displaystyle t_ {r}}$ either $u_{r}$ ${\ displaystyle u_ {r}}$ divided by p . If is divided $u_{r}$ ${\ displaystyle u_ {r}}$ put $r=2s$ ${\ displaystyle r = 2s}$ and carry out similar calculations with $0\equiv 2t_{s}u_{s}$ ${\ displaystyle 0 \ equiv 2t_ {s} u_ {s}}$ . Not all $u_{i}$ ${\ displaystyle u_ {i}}$ divided by p so $u_{1}$ ${\ displaystyle u_ {1}}$ not divided. Happening $u_{m}\equiv 0$ ${\ displaystyle u_ {m} \ equiv 0}$ with odd m is impossible because it is executed $t_{m}^{2}-Du_{m}^{2}\equiv N^{m}$ ${\ displaystyle t_ {m} ^ {2} -Du_ {m} ^ {2} \ equiv N ^ {m}}$ and that should mean that $t_{m}^{2}$ ${\ displaystyle t_ {m} ^ {2}}$ congruently non-counting quadratic, obtained a contradiction. Thus, the cycle is interrupted when $t_{l}\equiv 0$ ${\ displaystyle t_ {l} \ equiv 0}$ for some l . This gives $-Du_{l}^{2}\equiv N^{l}$ ${\ displaystyle -Du_ {l} ^ {2} \ equiv N ^ {l}}$ as well $-D$ ${\ displaystyle -D}$ is a square residue, l must be even. Set $l=2k$ ${\ displaystyle l = 2k}$ . Then $0\equiv t_{l}\equiv t_{k}^{2}+Du_{k}^{2}$ ${\ displaystyle 0 \ equiv t_ {l} \ equiv t_ {k} ^ {2} + Du_ {k} ^ {2}}$ . So, solving the equation $x^{2}+D\equiv 0$ ${\ displaystyle x ^ {2} + D \ equiv 0}$ we obtain by solving a linear equation $u_{k}x\equiv \pm t_{k}$ ${\ displaystyle u_ {k} x \ equiv \ pm t_ {k}}$ .

Examples

Below are 3 examples corresponding to 3 different cases. In the examples all signs $\equiv$ ${\ displaystyle \ equiv}$ means modulo comparison .

Example 1

Solve the congruent equation

x^{2}\equiv 18{\pmod {23}}.

{\ displaystyle x ^ {2} \ equiv 18 {\ pmod {23}}.}

The modulus is 23. Because $23=4\cdot 5+3$ ${\ displaystyle 23 = 4 \ cdot 5 + 3}$ , $m=5$ ${\ displaystyle m = 5}$ . Solutions must be values $x\equiv \pm 18^{6}\equiv \pm 8{\pmod {23}}$ ${\ displaystyle x \ equiv \ pm 18 ^ {6} \ equiv \ pm 8 {\ pmod {23}}}$ , and these are really solutions: $(\pm 8)^{2}\equiv 64\equiv 18{\pmod {23}}$ ${\ displaystyle (\ pm 8) ^ {2} \ equiv 64 \ equiv 18 {\ pmod {23}}}$ .

Example 2

Solve the congruent equation

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

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

The modulus is 13. Because $13=8\cdot 1+5$ ${\ displaystyle 13 = 8 \ cdot 1 + 5}$ , $m=1$ ${\ displaystyle m = 1}$ . Check that $10^{2m+1}\equiv 10^{3}\equiv -1{\pmod {13}}$ ${\ displaystyle 10 ^ {2m + 1} \ equiv 10 ^ {3} \ equiv -1 {\ pmod {13}}}$ . So the solution will be $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}}}$ . And these are really solutions: $(\pm 7)^{2}\equiv 49\equiv 10{\pmod {13}}$ ${\ displaystyle (\ pm 7) ^ {2} \ equiv 49 \ equiv 10 {\ pmod {13}}}$ .

Example 3

Solve the congruent equation $x^{2}\equiv 13{\pmod {17}}$ ${\ displaystyle x ^ {2} \ equiv 13 {\ pmod {17}}}$ . We write the equation in the form $x^{2}-13=0$ ${\ displaystyle x ^ {2} -13 = 0}$ . First we find $t_{1}$ ${\ displaystyle t_ {1}}$ and $u_{1}$ ${\ displaystyle u_ {1}}$ such that $t_{1}^{2}+13u_{1}^{2}$ ${\ displaystyle t_ {1} ^ {2} + 13u_ {1} ^ {2}}$ is a quadratic non-reading. Take, for example, $t_{1}=3,u_{1}=1$ ${\ displaystyle t_ {1} = 3, u_ {1} = 1}$ . Find $t_{8}$ ${\ displaystyle t_ {8}}$ , $u_{8}$ ${\ displaystyle u_ {8}}$ starting with

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}}, \,}

,

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}}. \,}

We continue in the same way $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}}}$ , $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}}.}$

Insofar as $t_{8}=0$ ${\ displaystyle t_ {8} = 0}$ get $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}}}$ that leads to the equation $3x\equiv \pm 7{\pmod {17}}$ ${\ displaystyle 3x \ equiv \ pm 7 {\ pmod {17}}}$ . The latter has solutions $x\equiv \pm 8{\pmod {17}}$ ${\ displaystyle x \ equiv \ pm 8 {\ pmod {17}}}$ . Really, $(\pm 8)^{2}=64\equiv 13{\pmod {17}}$ ${\ displaystyle (\ pm 8) ^ {2} = 64 \ equiv 13 {\ pmod {17}}}$ .

Notes

↑ Pocklington, 1917 , p. 57–58.

Literature

HC Pocklington. The direct solution of the quadratic and cubic binomial congruences with prime moduli // Proceedings of the Cambridge Philosophical Society. - 1917. - T. 19 .

[_b38652530870a4a5-1] Pocklington, 1917 , p. 57–58.