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]

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 · Number-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).

fonte: https://web.archive.org/web/20120121102019/http://en.wikipedia.org/wiki/Pocklington%27s_algorithm

Personal tools

Interaction

Toolbox

What links here
Related changes
Upload file
Special pages
Permanent link
Cite this page

Print/export

Create a book
Download as PDF
Printable version

Conheça Walt Disney World

Pocklington's algorithm

Contents

The algorithm

Solution method

Examples

Example 1

Example 2

Example 3

References

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

Interaction

Toolbox

Print/export