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.

The algorithm

(Note: all \equiv are taken to mean \pmod p, unless indicated otherwise.) Inputs: Outputs:

Solution method

Pocklington separates 3 different cases for p: The first case, if p=4m+3, with, the solution is. The second case, if p=8m+5, with and The third case, if p=8m+1, put D \equiv -a, so the equation to solve becomes. Now find by trial and error t_1 and u_1 so that is a quadratic non-residue. Furthermore, let The following equalities now hold: 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. Now the equations give a solution. Let p-1 = 2r. Then. This means that either t_r or u_r is divisible by p. If it is u_r, put r=2s and proceed similarly with. Not every u_i is divisible by p, for u_1 is not. The case with m odd is impossible, because 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 for a particular l. This gives, and because -D is a quadratic residue, l must be even. Put l = 2k. Then. So the solution of is got by solving the linear congruence.

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

This is the first case, according to the algorithm, , but then 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

Solve the congruence The modulus is 23. This is, so m=5. The solution should be, which is indeed true:.

Example 2

Solve the congruence The modulus is 13. This is, so m=1. Now verifying. So the solution is. This is indeed true:.

Example 3

Solve the congruence. For this, write x^2 -13 =0. First find a t_1 and u_1 such that is a quadratic nonresidue. Take for example. Now find t_8, u_8 by computing And similarly such that Since t_8 = 0, the equation which leads to solving the equation. This has solution. Indeed,.