View source for Truncated 5-cubes

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

:<math>x^2 \equiv a \pmod p, \, </math>

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 [[Henry Cabourn Pocklington|H.C. Pocklington]] in 1917.<ref>H.C. Pocklington, Proceedings of the Cambridge Philosophical Society, Volume 19, pages 57–58</ref>

==The algorithm==
(Note: all <math>\equiv</math> are taken to mean <math>\pmod p</math>, unless indicated otherwise.)

'''Inputs:'''
* ''p'', an odd [[Prime_number|prime]]
* ''a'', an integer which is a quadratic residue <math>\pmod p</math>.

'''Outputs:'''
* ''x'', an integer satisfying <math>x^2 \equiv a</math>. Note that if ''x'' is a solution, &minus;''x'' is a solution as well and since ''p'' is odd, <math>x \neq -x</math>. So there is always a second solution when one is found.

===Solution method===
Pocklington separates 3 different cases for ''p'':

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

The second case, if <math>p=8m+5</math>, with <math>m \in \mathbb{N}</math> and
# <math>a^{2m+1} \equiv 1</math>, the solution is <math>x \equiv \pm a^{m+1}</math>.
# <math>a^{2m+1} \equiv -1</math>, 2 is a (quadratic) non-residue so <math>4^{2m+1} \equiv -1</math>. This means that <math>(4a)^{2m+1} \equiv 1</math> so <math>y \equiv \pm (4a)^{m+1}</math> is a solution of <math>y^2 \equiv 4a</math>. Hence <math>x \equiv \pm y/2</math> or, if ''y'' is odd, <math>x \equiv \pm (p+y)/2</math>.

The third case, if <math>p=8m+1</math>, put <math>D \equiv -a</math>, so the equation to solve becomes <math>x^2 + D \equiv 0</math>. Now find by trial and error <math>t_1</math> and <math>u_1</math> so that <math>N = t_1^2 - D u_1^2</math> is a quadratic non-residue. Furthermore let
:<math>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}}</math>.
The following equalities now hold:
:<math>t_{m+n} = t_m t_n + D u_m u_n, \quad u_{m+n} = t_m u_n + t_n u_m \quad \mbox{and} \quad t_n^2 - D u_n^2 = N^n</math>.
Supposing that ''p'' is of the form <math>4m+1</math> (which is true if ''p'' is of the form <math>8m+1</math>), ''D'' is a quadratic residue and <math>t_p \equiv t_1^p \equiv t_1, \quad u_p \equiv u_1^p D^{(p-1)/2} \equiv u_1</math>. Now the equations
: <math>t_1 \equiv t_{p-1} t_1 + D u_{p-1} u_1 \quad \mbox{and} \quad u_1 \equiv t_{p-1} u_1 + t_1 u_{p-1}</math>
give a solution <math>t_{p-1} \equiv 1, \quad u_{p-1} \equiv 0</math>.

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

==Examples==
The following are 3 examples, corresponding to the 3 different cases in which Pocklington divided forms of ''p''. All <math>\equiv</math> are taken with the [[Modular_arithmetic|modulus]] in the example.

===Example 1===
Solve the congruence
:<math>x^2 \equiv 18 \pmod {23}.</math>
The modulus is 23. This is <math>23 = 4 \cdot 5 + 3</math>, so <math>m=5</math>. The solution should be <math>x \equiv \pm 18^6 \equiv \pm 8\pmod {23}</math>, which is indeed true: <math>(\pm 8)^2 \equiv 64 \equiv 18\pmod {23}</math>.

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

===Example 3===
Solve the congruence <math>x^2 \equiv 13 \pmod {17}</math>. For this, write <math>x^2 -13 =0</math>. First find a <math>t_1</math> and <math>u_1</math> such that <math>t_1^2 + 13u_1^2</math> is a quadratic nonresidue. Take for example <math>t_1=3, u_1 = 1</math>. Now find <math>t_8</math>, <math>u_8</math> by computing
:<math>t_2 = t_1 t_1 + 13u_1u_1 = 9-13 = -4 \equiv 13\pmod {17},\,</math>,
:<math>u_2 = t_1u_1 + t_1u_1 = 3+3 \equiv 6\pmod {17}.\,</math>
And similarly <math>t_4 = -299 \equiv 7 \pmod {17}\, u_4=156 \equiv 3\pmod {17}</math> such that <math>t_8=-68 \equiv 0\pmod {17}\, u_8 = 42 \equiv 8\pmod {17}.</math>

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

==References==
<references/>

{{number theoretic algorithms}}

[[Category:Modular arithmetic]]
[[Category:Number theoretic algorithms]]