Kunerth's algorithm

Adolf Kunerth's 1878 Modular Square Root Algorithm is detailed at . A monograph on the Kindle also explains the algorithm and provides seven examples of it working

The algorithm is notable since it doesn't require the factorization of the modulus, and only has one modular operation that is often easy if the cipher is a prime.

To find

$x^{2}{\bmod {N}}$

do the following steps

1) find the modular square root of $r\equiv {\sqrt {\pm N}}{\bmod {(x^{2}{\bmod {N}})}}$ This step is quite easy, no matter how big the original modulus is if $x^{2}{\bmod {N}}$ is a prime.

2) solve a quadratic equation associated with the modular square root of $w^{2}=A*z^{2}+B*z+C$. Most of Kunerth's examples in his original paper solve this equation by having C be a natural square and thus setting z to zero.

Expand out the following equation to obtain the quadratic

if $x^{2}{\bmod {N}}\equiv B$ then

((B* z + r)^2 + N)/B==w^{2}</math>

3) Having solved the associated quadratic equation we now have the variables w and set v=r (if C in the quadratic is a natural square).

4) Solve for two more variables, alpha and beta by the following equation

alpha == w (v + w beta )

Please note that this is not a modular operation and that alpha and beta could have many paired answers.

5) Obtain a value for X via a factorization of the following polynomial.

$alpha^{2}*x^{2}+(2*alpha*beta-N)x+(beta^{2}-(x^{2}{\bmod {N}}))$

obtaining an answer like

(-37 + 9 x) (1 + 25 x)

6) Obtain the modular square root by the equation. Remember to set X so that the term above is zero. Thus X would be 37/9 or -1/25.

$x\equiv alpha*X+beta{\bmod {N}}$

The hard step is the solving of the quadratic equation, but if this can be done then the algorithm quickly finds the modular square root without much computation.

An Example

To obtain ${\sqrt {41}}{\bmod {856}}$

first obtain ${\sqrt {-856}}{\bmod {41}}\equiv 13$

Then expand out the following polynomial

$((41z+13)^{2}+856)/41==w^{2}$

which is

$25+26z+41z^{2}==5^{2}$

Since, in this case the C term in the quadratic is a natural square then $W=5$

Set $w=5$ and $v=13$ (If z had a value then set $v=41*z+13$)

Solve for alpha and beta in the following equation involving W and V

alpha == W (V + W* beta)

getting the answer alpha=15 and beta = -2. (There may be many paired answers to this equation)

Then factor the following polynomial

$alpha^{2}x^{2}+(2*alpha*beta-856)x+(beta^{2}-41)$

obtaining

$(-37+9x)(1+25x)$

Then obtain the modular square root via

$15*(37*9^{-1})+(-2){\bmod {856}}\equiv 345$

Verify that $345^{2}{\bmod {856}}\equiv 41$

In the case that ${\sqrt {-856}}{\bmod {41}}$ has no answer then $r\equiv {\sqrt {-856}}{\bmod {(b*856+41)}}$ can be used instead.