Pocklington's algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

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]

The algorithm[edit]

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

Inputs:

  • p, an odd prime
  • a, an integer which is a quadratic residue \pmod p.

Outputs:

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

Solution method[edit]

Pocklington separates 3 different cases for p:

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

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

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

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

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

Supposing that p is of the form 4m+1 (which is true if p is of the form 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. Now the equations

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}

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

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

Examples[edit]

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

Example 1[edit]

Solve the congruence

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

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

Example 2[edit]

Solve the congruence

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

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

Example 3[edit]

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

t_2 = t_1 t_1 + 13u_1u_1 = 9-13 = -4 \equiv 13\pmod {17},\,,
u_2 = t_1u_1 + t_1u_1 = 3+3 \equiv 6\pmod {17}.\,

And similarly t_4 = -299 \equiv 7 \pmod {17}\, u_4=156 \equiv 3\pmod {17} such that t_8=-68 \equiv 0\pmod {17}\, u_8 = 42 \equiv 8\pmod {17}.

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

References[edit]

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