Pocklington's algorithm

Summary

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]

The algorithm edit

(Note: all   are taken to mean  , unless indicated otherwise.)

Inputs:

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

Outputs:

  • x, an integer satisfying  . Note that if x is a solution, −x is a solution as well and since p is odd,  . 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  , with  , the solution is  .

The second case, if  , with   and

  1.  , the solution is  .
  2.  , 2 is a (quadratic) non-residue so  . This means that   so   is a solution of  . Hence   or, if y is odd,  .

The third case, if  , put  , so the equation to solve becomes  . Now find by trial and error   and   so that   is a quadratic non-residue. Furthermore, let

 .

The following equalities now hold:

 .

Supposing that p is of the form   (which is true if p is of the form  ), D is a quadratic residue and  . Now the equations

 

give a solution  .

Let  . Then  . This means that either   or   is divisible by p. If it is  , put   and proceed similarly with  . Not every   is divisible by p, for   is not. The case   with m odd is impossible, because   holds and this would mean that   is congruent to a quadratic non-residue, which is a contradiction. So this loop stops when   for a particular l. This gives  , and because   is a quadratic residue, l must be even. Put  . Then  . So the solution of   is got by solving the linear congruence  .

Examples edit

The following are 4 examples, corresponding to the 3 different cases in which Pocklington divided forms of p. All   are taken with the modulus in the example.

Example 0 edit

 

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

 

The modulus is 23. This is  , so  . The solution should be  , which is indeed true:  .

Example 2 edit

Solve the congruence

 

The modulus is 13. This is  , so  . Now verifying  . So the solution is  . This is indeed true:  .

Example 3 edit

Solve the congruence  . For this, write  . First find a   and   such that   is a quadratic nonresidue. Take for example  . Now find  ,   by computing

 
 

And similarly   such that  

Since  , the equation   which leads to solving the equation  . This has solution  . Indeed,  .

References edit

  • Leonard Eugene Dickson, "History Of The Theory Of Numbers" vol 1 p 222, Chelsea Publishing 1952
  1. ^ H.C. Pocklington, Proceedings of the Cambridge Philosophical Society, Volume 19, pages 57–58