Pocklington's algorithm is a technique for solving a congruence of the form
x
2
≡
a
(
mod
p
)
,
{\displaystyle 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
≡
{\displaystyle \equiv }
are taken to mean
(
mod
p
)
{\displaystyle {\pmod {p}}}
, unless indicated otherwise.)
Inputs:
p , an odd prime
a , an integer which is a quadratic residue
(
mod
p
)
{\displaystyle {\pmod {p}}}
.
Outputs:
x , an integer satisfying
x
2
≡
a
{\displaystyle x^{2}\equiv a}
. Note that if x is a solution, −x is a solution as well and since p is odd,
x
≠
−
x
{\displaystyle 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
=
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
a
2
m
+
1
≡
1
{\displaystyle a^{2m+1}\equiv 1}
, the solution is
x
≡
±
a
m
+
1
{\displaystyle x\equiv \pm a^{m+1}}
.
a
2
m
+
1
≡
−
1
{\displaystyle a^{2m+1}\equiv -1}
, 2 is a (quadratic) non-residue so
4
2
m
+
1
≡
−
1
{\displaystyle 4^{2m+1}\equiv -1}
. This means that
(
4
a
)
2
m
+
1
≡
1
{\displaystyle (4a)^{2m+1}\equiv 1}
so
y
≡
±
(
4
a
)
m
+
1
{\displaystyle y\equiv \pm (4a)^{m+1}}
is a solution of
y
2
≡
4
a
{\displaystyle y^{2}\equiv 4a}
. Hence
x
≡
±
y
/
2
{\displaystyle x\equiv \pm y/2}
or, if y is odd,
x
≡
±
(
p
+
y
)
/
2
{\displaystyle x\equiv \pm (p+y)/2}
.
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
t
n
=
(
t
1
+
u
1
D
)
n
+
(
t
1
−
u
1
D
)
n
2
,
u
n
=
(
t
1
+
u
1
D
)
n
−
(
t
1
−
u
1
D
)
n
2
D
{\displaystyle 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
,
u
m
+
n
=
t
m
u
n
+
t
n
u
m
and
t
n
2
−
D
u
n
2
=
N
n
{\displaystyle t_{m+n}=t_{m}t_{n}+Du_{m}u_{n},\quad u_{m+n}=t_{m}u_{n}+t_{n}u_{m}\quad {\mbox{and}}\quad t_{n}^{2}-Du_{n}^{2}=N^{n}}
.
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
t
1
≡
t
p
−
1
t
1
+
D
u
p
−
1
u
1
and
u
1
≡
t
p
−
1
u
1
+
t
1
u
p
−
1
{\displaystyle t_{1}\equiv t_{p-1}t_{1}+Du_{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
≡
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}}
.
Examples
edit
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.
Example 0
edit
x
2
≡
43
(
mod
47
)
.
{\displaystyle x^{2}\equiv 43{\pmod {47}}.}
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.
Example 1
edit
Solve the congruence
x
2
≡
18
(
mod
23
)
.
{\displaystyle x^{2}\equiv 18{\pmod {23}}.}
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}}}
.
Example 2
edit
Solve the congruence
x
2
≡
10
(
mod
13
)
.
{\displaystyle x^{2}\equiv 10{\pmod {13}}.}
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}}}
.
Example 3
edit
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
t
2
=
t
1
t
1
+
13
u
1
u
1
=
9
−
13
=
−
4
≡
13
(
mod
17
)
,
{\displaystyle t_{2}=t_{1}t_{1}+13u_{1}u_{1}=9-13=-4\equiv 13{\pmod {17}},}
u
2
=
t
1
u
1
+
t
1
u
1
=
3
+
3
≡
6
(
mod
17
)
.
{\displaystyle u_{2}=t_{1}u_{1}+t_{1}u_{1}=3+3\equiv 6{\pmod {17}}.}
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}}}
.
References
edit
Leonard Eugene Dickson, "History Of The Theory Of Numbers" vol 1 p 222, Chelsea Publishing 1952
^ H.C. Pocklington, Proceedings of the Cambridge Philosophical Society, Volume 19, pages 57–58