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 relies on modular operations that is often easy when the given number is prime.
To find y from a given value
it takes the following steps:
To obtain first obtain .
Then expand the polynomial:
into
Since, in this case the C term is a square, we take and compute (in general, ).
In the case that has no answer, then can be used instead.