Pocklington's algorithm is a technique for solving a congruence of the form
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]
(Note: all ≡ ≡ --> {\displaystyle \equiv } are taken to mean ( mod p ) {\displaystyle {\pmod {p}}} , unless indicated otherwise.)
Inputs:
Outputs:
Pocklington separates 3 different cases for p:
The first case, if p = 4 m + 3 {\displaystyle p=4m+3} , with m ∈ ∈ --> N {\displaystyle m\in \mathbb {N} } , the solution is x ≡ ≡ --> ± ± --> a m + 1 {\displaystyle x\equiv \pm a^{m+1}} .
The second case, if p = 8 m + 5 {\displaystyle p=8m+5} , with m ∈ ∈ --> N {\displaystyle m\in \mathbb {N} } and
The third case, if p = 8 m + 1 {\displaystyle p=8m+1} , put D ≡ ≡ --> − − --> a {\displaystyle D\equiv -a} , so the equation to solve becomes x 2 + D ≡ ≡ --> 0 {\displaystyle x^{2}+D\equiv 0} . Now find by trial and error t 1 {\displaystyle t_{1}} and u 1 {\displaystyle u_{1}} so that N = t 1 2 − − --> D u 1 2 {\displaystyle N=t_{1}^{2}-Du_{1}^{2}} is a quadratic non-residue. Furthermore, let
The following equalities now hold:
Supposing that p is of the form 4 m + 1 {\displaystyle 4m+1} (which is true if p is of the form 8 m + 1 {\displaystyle 8m+1} ), D is a quadratic residue and t p ≡ ≡ --> t 1 p ≡ ≡ --> t 1 , u p ≡ ≡ --> u 1 p D ( p − − --> 1 ) / 2 ≡ ≡ --> u 1 {\displaystyle 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
give a solution t p − − --> 1 ≡ ≡ --> 1 , u p − − --> 1 ≡ ≡ --> 0 {\displaystyle t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0} .
Let p − − --> 1 = 2 r {\displaystyle p-1=2r} . Then 0 ≡ ≡ --> u p − − --> 1 ≡ ≡ --> 2 t r u r {\displaystyle 0\equiv u_{p-1}\equiv 2t_{r}u_{r}} . This means that either t r {\displaystyle t_{r}} or u r {\displaystyle u_{r}} is divisible by p. If it is u r {\displaystyle u_{r}} , put r = 2 s {\displaystyle r=2s} and proceed similarly with 0 ≡ ≡ --> 2 t s u s {\displaystyle 0\equiv 2t_{s}u_{s}} . Not every u i {\displaystyle u_{i}} is divisible by p, for u 1 {\displaystyle u_{1}} is not. The case u m ≡ ≡ --> 0 {\displaystyle u_{m}\equiv 0} with m odd is impossible, because t m 2 − − --> D u m 2 ≡ ≡ --> N m {\displaystyle t_{m}^{2}-Du_{m}^{2}\equiv N^{m}} holds and this would mean that t m 2 {\displaystyle t_{m}^{2}} is congruent to a quadratic non-residue, which is a contradiction. So this loop stops when t l ≡ ≡ --> 0 {\displaystyle t_{l}\equiv 0} for a particular l. This gives − − --> D u l 2 ≡ ≡ --> N l {\displaystyle -Du_{l}^{2}\equiv N^{l}} , and because − − --> D {\displaystyle -D} is a quadratic residue, l must be even. Put l = 2 k {\displaystyle l=2k} . Then 0 ≡ ≡ --> t l ≡ ≡ --> t k 2 + D u k 2 {\displaystyle 0\equiv t_{l}\equiv t_{k}^{2}+Du_{k}^{2}} . So the solution of x 2 + D ≡ ≡ --> 0 {\displaystyle x^{2}+D\equiv 0} is got by solving the linear congruence u k x ≡ ≡ --> ± ± --> t k {\displaystyle u_{k}x\equiv \pm t_{k}} .
The following are 4 examples, corresponding to the 3 different cases in which Pocklington divided forms of p. All ≡ ≡ --> {\displaystyle \equiv } are taken with the modulus in the example.
This is the first case, according to the algorithm, x ≡ ≡ --> 43 ( 47 + 1 ) / 2 = 43 12 ≡ ≡ --> 2 {\displaystyle x\equiv 43^{(47+1)/2}=43^{12}\equiv 2} , but then x 2 = 2 2 = 4 {\displaystyle x^{2}=2^{2}=4} not 43, so we should not apply the algorithm at all. The reason why the algorithm is not applicable is that a=43 is a quadratic non residue for p=47.
Solve the congruence
The modulus is 23. This is 23 = 4 ⋅ ⋅ --> 5 + 3 {\displaystyle 23=4\cdot 5+3} , so m = 5 {\displaystyle m=5} . The solution should be x ≡ ≡ --> ± ± --> 18 6 ≡ ≡ --> ± ± --> 8 ( mod 23 ) {\displaystyle x\equiv \pm 18^{6}\equiv \pm 8{\pmod {23}}} , which is indeed true: ( ± ± --> 8 ) 2 ≡ ≡ --> 64 ≡ ≡ --> 18 ( mod 23 ) {\displaystyle (\pm 8)^{2}\equiv 64\equiv 18{\pmod {23}}} .
The modulus is 13. This is 13 = 8 ⋅ ⋅ --> 1 + 5 {\displaystyle 13=8\cdot 1+5} , so m = 1 {\displaystyle m=1} . Now verifying 10 2 m + 1 ≡ ≡ --> 10 3 ≡ ≡ --> − − --> 1 ( mod 13 ) {\displaystyle 10^{2m+1}\equiv 10^{3}\equiv -1{\pmod {13}}} . So the solution is x ≡ ≡ --> ± ± --> y / 2 ≡ ≡ --> ± ± --> ( 4 a ) 2 / 2 ≡ ≡ --> ± ± --> 800 ≡ ≡ --> ± ± --> 7 ( mod 13 ) {\displaystyle x\equiv \pm y/2\equiv \pm (4a)^{2}/2\equiv \pm 800\equiv \pm 7{\pmod {13}}} . This is indeed true: ( ± ± --> 7 ) 2 ≡ ≡ --> 49 ≡ ≡ --> 10 ( mod 13 ) {\displaystyle (\pm 7)^{2}\equiv 49\equiv 10{\pmod {13}}} .
Solve the congruence x 2 ≡ ≡ --> 13 ( mod 17 ) {\displaystyle x^{2}\equiv 13{\pmod {17}}} . For this, write x 2 − − --> 13 = 0 {\displaystyle x^{2}-13=0} . First find a t 1 {\displaystyle t_{1}} and u 1 {\displaystyle u_{1}} such that t 1 2 + 13 u 1 2 {\displaystyle t_{1}^{2}+13u_{1}^{2}} is a quadratic nonresidue. Take for example t 1 = 3 , u 1 = 1 {\displaystyle t_{1}=3,u_{1}=1} . Now find t 8 {\displaystyle t_{8}} , u 8 {\displaystyle u_{8}} by computing
And similarly t 4 = − − --> 299 ≡ ≡ --> 7 ( mod 17 ) , u 4 = 156 ≡ ≡ --> 3 ( mod 17 ) {\displaystyle t_{4}=-299\equiv 7{\pmod {17}},u_{4}=156\equiv 3{\pmod {17}}} such that t 8 = − − --> 68 ≡ ≡ --> 0 ( mod 17 ) , u 8 = 42 ≡ ≡ --> 8 ( mod 17 ) . {\displaystyle t_{8}=-68\equiv 0{\pmod {17}},u_{8}=42\equiv 8{\pmod {17}}.}
Since t 8 = 0 {\displaystyle t_{8}=0} , the equation 0 ≡ ≡ --> t 4 2 + 13 u 4 2 ≡ ≡ --> 7 2 − − --> 13 ⋅ ⋅ --> 3 2 ( mod 17 ) {\displaystyle 0\equiv t_{4}^{2}+13u_{4}^{2}\equiv 7^{2}-13\cdot 3^{2}{\pmod {17}}} which leads to solving the equation 3 x ≡ ≡ --> ± ± --> 7 ( mod 17 ) {\displaystyle 3x\equiv \pm 7{\pmod {17}}} . This has solution x ≡ ≡ --> ± ± --> 8 ( mod 17 ) {\displaystyle x\equiv \pm 8{\pmod {17}}} . Indeed, ( ± ± --> 8 ) 2 = 64 ≡ ≡ --> 13 ( mod 17 ) {\displaystyle (\pm 8)^{2}=64\equiv 13{\pmod {17}}} .
Lokasi Pengunjung: 13.58.7.43