Cipolla's algorithm

In computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form

${\displaystyle x^{2}\equiv n{\pmod {p}},}$

where ${\displaystyle x,n\in \mathbf {F} _{p}}$, so n is the square of x, and where ${\displaystyle p}$ is an odd prime. Here ${\displaystyle \mathbf {F} _{p}}$ denotes the finite field with ${\displaystyle p}$ elements; ${\displaystyle \{0,1,\dots ,p-1\}}$. The algorithm is named after Michele Cipolla, an Italian mathematician who discovered it in 1907.

Apart from prime moduli, Cipolla's algorithm is also able to take square roots modulo prime powers.^[1]