Pocklington's algorithm

Wikipedia on Answers.com:

Pocklington's algorithm

Top

Home > Library > Miscellaneous > Wikipedia

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]

Contents

1 The algorithm
- 1.1 Solution method
2 Examples
3 References

The algorithm

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

Inputs:

p, an odd prime
a, an integer which is a quadratic residue $(mod 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 = 4 m + 3$ , with $m \in \mathbb{N}$ , the solution is $x \equiv \pm a^{m+1}$ .

The second case, if $p = 8 m + 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 = 8 m + 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 $4 m + 1$ (which is true if p is of the form $8 m + 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 = 2 r$ . 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 = 2 s$ 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 = 2 k$ . 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

v · d · eNumber-theoretic algorithms

Primality tests	AKS · APR · Baillie–PSW · ECPP · Elliptic curve · Pocklington · Fermat · Lucas · Lucas–Lehmer · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay–Strassen · Miller–Rabin · Trial division

Sieving algorithms	Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization

Integer factorization algorithms	CFRAC · Dixon's · ECM · Euler's · Pollard's rho · p − 1 · p + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's

Multiplication algorithms	Ancient Egyptian multiplication · Karatsuba algorithm · Toom–Cook multiplication · Schönhage–Strassen algorithm · Fürer's algorithm

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

GCD algorithms	Binary GCD · Euclidean · Extended Euclidean · Lehmer's

Modular square root algorithms	Cipolla · Pocklington's · Tonelli–Shanks

Other algorithms	Chakravala · Cornacchia · integer relation algorithm · integer square root · Modular exponentiation · Schoof's

Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests (current article is always in bold).

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

Help us answer these

How do you do the algorithm?

Which algorithm is Baran's backward learning algorithm?

What do you mean by a stable algorithm and inplace algorithm?

algorithm code for blind hide algorithm?

Post a question - any question - to the WikiAnswers community:

Copyrights:

Cite

Wikipedia on Answers.com This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article Pocklington's algorithm. Read