Kunerth's algorithm

Kunerth's algorithm is an algorithm to determine the modular square root of a number. The algorithm does not require the factorization of the modulus, and only has one modular operation that is often easy if the cipher is a prime.

To find

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

do the following steps:

1. find the modular square root of $r\equiv {\sqrt {\pm N}}{\pmod {y^{2}{\bmod {N}}}}$. This step is quite easy, no matter how big the original modulus is, if $y^{2}{\bmod {N}}$ is a prime.
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 natural square and thus setting z to zero.

   Expand out the following equation to obtain the quadratic

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

   $((B*z+r)^{2}\pm N)/B=w^{2}$

   You can always ensure that the quadratic can be solved by adjusting the N term(modulus) in the above equation. Thus

   $((B*z+r)^{2}+(B*F+N))/B=w^{2}$

   will ensure a quadratic of $A*z^{2}+D*z+C+F$

   You can then adjust F to ensure that C+F is a square. Quite large modula, such as ${\sqrt {67}}{\bmod {67F+RSA260}}$ can have their square roots taken quickly via this method.

   The parameters of the polynomial expansion are quite fluid, in that $((67z+r)^{2}+X\cdot RSA260)/(67y)$ can be done, for instance. It is quite easy to set X and Y so that $(r^{2}+X\cdot RSA260)/(67y)$ is a square. The modular square root of ${\sqrt {67y}}{\bmod {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+wbeta)$

   This is not a modular operation and that $(\alpha .\beta )$ may have many values.

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}}{\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\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
• 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