Kunerth's algorithm

Kunerth's algorithm is an algorithm for computing the modular square root of a given number. The algorithm does not require the factorization of the modulus, and uses modular operations that are often easy when the given number is prime.

Algorithm

To find $y$ from a given value

$B=y^{2}{\bmod {N}},$

it takes the following steps:

1. Find the modular square root $r\equiv {\sqrt {\pm N}}{\pmod {B}}$. This step is quite easy when $B$ is a prime, irrespective of how large $N$ is.
2. Solve a quadratic equation associated with the modular square root of $w^{2}=A\cdot z^{2}+B\cdot z+C$. Most of Kunerth's examples in his original paper solve this equation by having $C$ be a integer square and thus setting $z$ to zero.

   Expand the left hand side of the following equation:

   $((B\cdot z+r)^{2}+(B\cdot F\mp N))/B=w^{2}.$

   Expanding the left hand side results in a quadratic form $A\cdot z^{2}+D\cdot z+C+F$. One can then make sure that the equation can be solved by adjusting $F$ so as to make $C+F$ a square. Even large moduli, such as ${\sqrt {67}}{\bmod {67F+{\text{RSA260}}}}$, can have their square roots computed quickly via this method.

   The parameters of the polynomial expansion are quite flexible, in that $((67z+r)^{2}+X\cdot {\text{RSA260}})/(67y)$ can be done, for instance. It is quite easy to choose $X$ and $Y$ such that $(r^{2}+X\cdot {\text{RSA260}})/(67y)$ is a square. The modular square root of ${\sqrt {67y}}{\bmod {\text{RSA260}}}$ can be taken this way.

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 variables $\alpha$ and $\beta$ the following equation:

   $\alpha =w(v+w\beta ),$

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

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

   obtaining an answer like

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

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

   $y\equiv \alpha X+\beta {\pmod {N}}.$

Example

To obtain ${\sqrt {41}}{\bmod {856}},$ first obtain ${\sqrt {-856}}\equiv 13{\pmod {41}}$.

Then expand the polynomial:

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

into

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

Since, in this case the C term is a square, we take $w=5$ and compute $v=13$ (in general, $v=41\cdot z+13$).

Solve for $\alpha$ and $\beta$ the following equation

$\alpha ==w(v+w\beta )$

getting the solution $\alpha =15$ and $\beta =-2$. (There may be other pairs of solutions 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\cdot (37\cdot 9^{-1})+(-2)\equiv 345{\pmod {856}}.$

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

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

See also

• Methods of computing square roots

References

• Adolf Kunerth, "Sitzungsberichte. Academie Der Wissenschaften" vol 75, II, 1877, pp. 7–58
• Adolf Kunerth, "Sitzungsberichte. Academie Der Wissenschaften" vol 82, II, 1880, pp. 342–375