Cipolla's algorithm
From Wikipedia, the free encyclopedia
In computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form
where , so n is the square of x, and where
is an odd prime. Here
denotes the finite field with
elements;
. 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]