Kunerth's algorithm

Kunerth's algorithm is an algorithm for computing the modular square root of a given number.

[1][2] The algorithm does not require the factorization of the modulus, and uses modular operations that are often easy when the given number is prime.

To find

from a given value it takes the following steps: To obtain

first obtain

( mod

Then expand the polynomial: into Since, in this case the C term is a square, we take

and compute