• Images
• Videos
• Documents
• Books
• Articles

The algorithm

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

Inputs:

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

Outputs:

• x, an integer satisfying x 2 ≡ a {\displaystyle x^{2}\equiv a} . Note that if x is a solution, −x is a solution as well and since p is odd, x ≠ − x {\displaystyle 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 = 4 m + 3 {\displaystyle p=4m+3} , with m ∈ N {\displaystyle m\in \mathbb {N} } , the solution is x ≡ ± a m + 1 {\displaystyle x\equiv \pm a^{m+1}} .

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

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

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

t n = ( t 1 + u 1 D ) n + ( t 1 − u 1 D ) n 2 , u n = ( t 1 + u 1 D ) n − ( t 1 − u 1 D ) n 2 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:

t m + n = t m t n + D u m u n , u m + n = t m u n + t n u m and t n 2 − D u 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 4 m + 1 {\displaystyle 4m+1} (which is true if p is of the form 8 m + 1 {\displaystyle 8m+1} ), D is a quadratic residue and t p ≡ t 1 p ≡ t 1 , u p ≡ u 1 p D ( p − 1 ) / 2 ≡ 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

t 1 ≡ t p − 1 t 1 + D u p − 1 u 1 and u 1 ≡ 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 t p − 1 ≡ 1 , u p − 1 ≡ 0 {\displaystyle t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0} .

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

Example 0

x 2 ≡ 43 ( mod 47 ) . {\displaystyle x^{2}\equiv 43{\pmod {47}}.}

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

Example 1

Solve the congruence

x 2 ≡ 18 ( mod 23 ) . {\displaystyle x^{2}\equiv 18{\pmod {23}}.}

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

Example 2

Solve the congruence

x 2 ≡ 10 ( mod 13 ) . {\displaystyle x^{2}\equiv 10{\pmod {13}}.}

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

Example 3

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

t 2 = t 1 t 1 + 13 u 1 u 1 = 9 − 13 = − 4 ≡ 13 ( mod 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 ≡ 6 ( mod 17 ) . {\displaystyle u_{2}=t_{1}u_{1}+t_{1}u_{1}=3+3\equiv 6{\pmod {17}}.}

And similarly t 4 = − 299 ≡ 7 ( mod 17 ) , u 4 = 156 ≡ 3 ( mod 17 ) {\displaystyle t_{4}=-299\equiv 7{\pmod {17}},u_{4}=156\equiv 3{\pmod {17}}} such that t 8 = − 68 ≡ 0 ( mod 17 ) , u 8 = 42 ≡ 8 ( mod 17 ) . {\displaystyle t_{8}=-68\equiv 0{\pmod {17}},u_{8}=42\equiv 8{\pmod {17}}.}

Since t 8 = 0 {\displaystyle t_{8}=0} , the equation 0 ≡ t 4 2 + 13 u 4 2 ≡ 7 2 − 13 ⋅ 3 2 ( mod 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 3 x ≡ ± 7 ( mod 17 ) {\displaystyle 3x\equiv \pm 7{\pmod {17}}} . This has solution x ≡ ± 8 ( mod 17 ) {\displaystyle x\equiv \pm 8{\pmod {17}}} . Indeed, ( ± 8 ) 2 = 64 ≡ 13 ( mod 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

References

1. H.C. Pocklington, Proceedings of the Cambridge Philosophical Society, Volume 19, pages 57–58 ↩