Pocklington's algorithm

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

${\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]