Pocklington's algorithm

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

(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

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

$a^{2m+1} \equiv 1$ , the solution is $x \equiv \pm a^{m+1}$ .
$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

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

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

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

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

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

Number-theoretic algorithms

Primality tests	AKS test APR test Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius test Solovay–Strassen Miller–Rabin

Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Sundaram Wheel factorization

Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks' square forms Trial division Shor's

Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's

Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve

Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's

Modular square root	Cipolla Pocklington's Tonelli–Shanks

Other algorithms	Chakravala Cornacchia LLL Integer square root Modular exponentiation Schoof's

Italics indicate that algorithm is for numbers of special forms

This article is issued from Wikipedia - version of the 4/16/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.