Pocklington's algorithm is a technique for solving a congruence of the form
x
2
≡
a
(
mod
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.
(Note: all
≡
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
≡
a
. Note that if x is a solution, −x is a solution as well and since p is odd,
x
≠
−
x
. So there is always a second solution when one is found.
Pocklington separates 3 different cases for p:
The first case, if
p
=
4
m
+
3
, with
m
∈
N
, the solution is
x
≡
±
a
m
+
1
.
The second case, if
p
=
8
m
+
5
, with
m
∈
N
and
-
a
2
m
+
1
≡
1
, the solution is
x
≡
±
a
m
+
1
.
-
a
2
m
+
1
≡
−
1
, 2 is a (quadratic) non-residue so
4
2
m
+
1
≡
−
1
. This means that
(
4
a
)
2
m
+
1
≡
1
so
y
≡
±
(
4
a
)
m
+
1
is a solution of
y
2
≡
4
a
. Hence
x
≡
±
y
/
2
or, if y is odd,
x
≡
±
(
p
+
y
)
/
2
.
The third case, if
p
=
8
m
+
1
, put
D
≡
−
a
, so the equation to solve becomes
x
2
+
D
≡
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
=
(
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
.
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
.
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
≡
t
1
p
≡
t
1
,
u
p
≡
u
1
p
D
(
p
−
1
)
/
2
≡
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
give a solution
t
p
−
1
≡
1
,
u
p
−
1
≡
0
.
Let
p
−
1
=
2
r
. Then
0
≡
u
p
−
1
≡
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
≡
2
t
s
u
s
. Not every
u
i
is divisible by p, for
u
1
is not. The case
u
m
≡
0
with m odd is impossible, because
t
m
2
−
D
u
m
2
≡
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
≡
0
for a particular l. This gives
−
D
u
l
2
≡
N
l
, and because
−
D
is a quadratic residue, l must be even. Put
l
=
2
k
. Then
0
≡
t
l
≡
t
k
2
+
D
u
k
2
. So the solution of
x
2
+
D
≡
0
is got by solving the linear congruence
u
k
x
≡
±
t
k
.
The following are 3 examples, corresponding to the 3 different cases in which Pocklington divided forms of p. All
≡
are taken with the modulus in the example.
Solve the congruence
x
2
≡
18
(
mod
23
)
.
The modulus is 23. This is
23
=
4
⋅
5
+
3
, so
m
=
5
. The solution should be
x
≡
±
18
6
≡
±
8
(
mod
23
)
, which is indeed true:
(
±
8
)
2
≡
64
≡
18
(
mod
23
)
.
Solve the congruence
x
2
≡
10
(
mod
13
)
.
The modulus is 13. This is
13
=
8
⋅
1
+
5
, so
m
=
1
. Now verifying
10
2
m
+
1
≡
10
3
≡
−
1
(
mod
13
)
. So the solution is
x
≡
±
y
/
2
≡
±
(
4
a
)
2
/
2
≡
±
800
≡
±
7
(
mod
13
)
. This is indeed true:
(
±
7
)
2
≡
49
≡
10
(
mod
13
)
.
Solve the congruence
x
2
≡
13
(
mod
17
)
. For this, write
x
2
−
13
=
0
. First find a
t
1
and
u
1
such that
t
1
2
+
13
u
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
+
13
u
1
u
1
=
9
−
13
=
−
4
≡
13
(
mod
17
)
,
,
u
2
=
t
1
u
1
+
t
1
u
1
=
3
+
3
≡
6
(
mod
17
)
.
And similarly
t
4
=
−
299
≡
7
(
mod
17
)
u
4
=
156
≡
3
(
mod
17
)
such that
t
8
=
−
68
≡
0
(
mod
17
)
u
8
=
42
≡
8
(
mod
17
)
.
Since
t
8
=
0
, the equation
0
≡
t
4
2
+
13
u
4
2
≡
7
2
−
13
⋅
3
2
(
mod
17
)
which leads to solving the equation
3
x
≡
±
7
(
mod
17
)
. This has solution
x
≡
±
8
(
mod
17
)
. Indeed,
(
±
8
)
2
=
64
≡
13
(
mod
17
)
.
