Pocklington's algorithm

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.

(Note: all ${\displaystyle \equiv }$ are taken to mean ${\displaystyle {\pmod {p}}}$, unless indicated otherwise.)

Inputs:

Outputs:

Pocklington separates 3 different cases for p:

The first case, if ${\displaystyle p=4m+3}$, with ${\displaystyle m\in \mathbb {N} }$, the solution is ${\displaystyle x\equiv \pm a^{m+1}}$.

...
Wikipedia