Pocklington's algorithm explained

Pocklington's algorithm is a technique for solving a congruence of the form

x²\equiva\pmodp,

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

(Note: all

\equiv

are taken to mean

\pmodp

, unless indicated otherwise.)

Inputs:

p, an odd prime
a, an integer which is a quadratic residue

\pmodp

Outputs:

x, an integer satisfying

x²\equiva

. 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.

Solution method

Pocklington separates 3 different cases for p:

The first case, if

p=4m+3

, with

m\inN

, the solution is

x\equiv\pma^m+1

The second case, if

p=8m+5

, with

m\inN

and

a^2m+1\equiv1

, the solution is

x\equiv\pma^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\equiv1

y\equiv\pm(4a)^m+1

is a solution of

y²\equiv4a

. Hence

x\equiv\pmy/2

or, if y is odd,

x\equiv\pm(p+y)/2

The third case, if

p=8m+1

, put

D\equiv-a

, so the equation to solve becomes

x²+D\equiv0

. Now find by trial and error

t₁

and

u₁

so that

	2
t
	1

-D

	2
u
	1

is a quadratic non-residue. Furthermore, let

t_n=

	(t₁+u₁\sqrt{D
	)

ⁿ+(t₁-u₁\sqrt{D})^n}{2}, u_n=

	(t₁+u₁\sqrt{D
	)

ⁿ-(t₁-u₁\sqrt{D})^n}{2\sqrt{D}}

.The following equalities now hold:

t_m+n=t_mt_n+Du_mu_n, u_m+n=t_mu_n+t_nu_m and

	2
t
	n

-D

	2
u
	n

=Nⁿ

.Supposing that p is of the form

4m+1

(which is true if p is of the form

8m+1

), D is a quadratic residue and

t_p\equiv

	p
t
	1

\equivt_1, u_p\equiv

	p
u
	1

D^(p-1)/2\equivu₁

. Now the equations

t₁\equivt_p-1t₁+Du_p-1u₁ and u₁\equivt_p-1u₁+t₁u_p-1

give a solution

t_p-1\equiv1, u_p-1\equiv0

Let

p-1=2r

. Then

0\equivu_p-1\equiv2t_ru_r

. This means that either

t_r

u_r

is divisible by p. If it is

u_r

, put

r=2s

and proceed similarly with

0\equiv2t_su_s

. Not every

u_i

is divisible by p, for

u₁

is not. The case

u_m\equiv0

with m odd is impossible, because

	2
t
	m

-D

	2
u
	m

\equivN^m

holds and this would mean that

	2
t
	m

is congruent to a quadratic non-residue, which is a contradiction. So this loop stops when

t_l\equiv0

for a particular l. This gives

-D

	2
u
	l

\equivN^l

, and because

-D

is a quadratic residue, l must be even. Put

l=2k

. Then

0\equivt_l\equiv

	2
t
	k

	2
u
	k

. So the solution of

x²+D\equiv0

is got by solving the linear congruence

u_kx\equiv\pmt_k

Examples

The following are 4 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 0

x²\equiv43\pmod{47}.

This is the first case, according to the algorithm,

x\equiv43^(47+1)/2=43¹²\equiv2

, but then

x²⁼²²⁼⁴

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

Solve the congruence

x²\equiv18\pmod{23}.

The modulus is 23. This is

23=4 ⋅ 5+3

, so

m=5

. The solution should be

x\equiv\pm18⁶\equiv\pm8\pmod{23}

, which is indeed true:

(\pm8)²\equiv64\equiv18\pmod{23}

Example 2

Solve the congruence

x²\equiv10\pmod{13}.

The modulus is 13. This is

13=8 ⋅ 1+5

, so

m=1

. Now verifying

10^2m+1\equiv10³\equiv-1\pmod{13}

. So the solution is

x\equiv\pmy/2\equiv\pm(4a)²/2\equiv\pm800\equiv\pm7\pmod{13}

. This is indeed true:

(\pm7)²\equiv49\equiv10\pmod{13}

Example 3

Solve the congruence

x²\equiv13\pmod{17}

. For this, write

x²-13=0

. First find a

t₁

and

u₁

such that

	2
t
	1

	2
13u
	1

is a quadratic nonresidue. Take for example

t_1=3,u₁=1

. Now find

t₈

u₈

by computing

t₂=t₁t₁+13u_1u₁=9-13=-4\equiv13\pmod{17},

u₂=t_1u₁+t_1u₁=3+3\equiv6\pmod{17}.

And similarly

t₄=-299\equiv7\pmod{17},u₄₌₁₅₆\equiv3\pmod{17}

such that

t_8=-68\equiv0\pmod{17},u₈=42\equiv8\pmod{17}.

Since

t₈=0

, the equation

0\equiv

	2
t
	4

	2
13u
	4

\equiv7²-13 ⋅ 3^2\pmod{17}

which leads to solving the equation

3x\equiv\pm7\pmod{17}

. This has solution

x\equiv\pm8\pmod{17}

. Indeed,

(\pm8)²=64\equiv13\pmod{17}

References

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