Kunerth's algorithm

To find y from a given value

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

it takes the following steps:

1. find the modular square root of ${\displaystyle r\equiv {\sqrt {\pm N}}{\pmod {B}}}$ . This step is quite easy, irrespectively of how big N when ${\displaystyle B}$  is a prime.
2. solve a quadratic equation associated with the modular square root of ${\displaystyle 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 out the following equation to obtain the quadratic

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

   One can always make sure that the quadratic can be solved by adjusting the modulus N in the above equation. Thus

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

   will ensure a quadratic of ${\displaystyle A\cdot z^{2}+D\cdot z+C+F}$ .

   One can then adjust F to make sure that ${\displaystyle C+F}$  is a square. For large moduli, such as ${\displaystyle {\sqrt {67}}{\bmod {67F+RSA260}}}$ , can have their square roots computed quickly via this method.

   The parameters of the polynomial expansion are quite flexible, in that ${\displaystyle ((67z+r)^{2}+X\cdot RSA260)/(67y)}$  can be done, for instance. It is quite easy to choose X and Y such that ${\displaystyle (r^{2}+X\cdot RSA260)/(67y)}$  is a square. The modular square root of ${\displaystyle {\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 ${\displaystyle \alpha }$  and ${\displaystyle \beta }$  the following equation:

   ${\displaystyle \alpha =w(v+w\beta ),}$ 

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

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

   obtaining an answer like

   ${\displaystyle (-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.

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

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

Then expand the polynomial:

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

into

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

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

Solve for ${\displaystyle \alpha }$  and ${\displaystyle \beta }$  the following equation

${\displaystyle \alpha ==w(v+w\beta )}$ 

getting the solution ${\displaystyle \alpha =15}$  and ${\displaystyle \beta =-2}$ . (There may be other pairs of solutions to this equation.)

Then factor the following polynomial:

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

obtaining

${\displaystyle (-37+9x)(1+25x)}$ 

Then obtain the modular square root via

${\displaystyle 15\cdot (37\cdot 9^{-1})+(-2)\equiv 345{\pmod {856}}.}$ 

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

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

• 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