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 relies on modular operations that is often easy when the given number is prime.

Algorithm

To find y from a given value

[math]\displaystyle{ B = y^{2} \bmod{N}, }[/math]

it takes the following steps:

1. find the modular square root of [math]\displaystyle{ r\equiv \sqrt{\pm N} \pmod{B} }[/math]. This step is quite easy, irrespectively of how big N when [math]\displaystyle{ B }[/math] is a prime.
2. solve a quadratic equation associated with the modular square root of [math]\displaystyle{ w^{2}=A\cdot z^{2}+B\cdot z+C }[/math]. 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

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

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

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

   will ensure a quadratic of [math]\displaystyle{ A\cdot z^{2}+D\cdot z+C+F }[/math].

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

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

   [math]\displaystyle{ \alpha = w (v + w \beta ), }[/math]

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

   [math]\displaystyle{ \alpha^{2} \cdot x^{2} + (2 \alpha \beta - N) x +(\beta^{2} - (y^{2}\bmod{N})) }[/math]

   obtaining an answer like

   [math]\displaystyle{ (-37 + 9 x) (1 + 25 x) }[/math]

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.

   [math]\displaystyle{ y\equiv \alpha X + \beta \pmod{N}. }[/math]

Example

To obtain [math]\displaystyle{ \sqrt{41}\bmod{856}, }[/math] first obtain [math]\displaystyle{ \sqrt{-856}\equiv 13\pmod{41} }[/math].

Then expand the polynomial:

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

into

[math]\displaystyle{ 25 + 26 z + 41 z^{2} }[/math]

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

Solve for [math]\displaystyle{ \alpha }[/math] and [math]\displaystyle{ \beta }[/math] the following equation

[math]\displaystyle{ \alpha == w (v + w\beta) }[/math]

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

Then factor the following polynomial:

[math]\displaystyle{ \alpha^2 x^2 + (2 \alpha \beta - 856) x + (\beta^{2} - 41) }[/math]

obtaining

[math]\displaystyle{ (-37 + 9 x) (1 + 25 x) }[/math]

Then obtain the modular square root via

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

Verify that [math]\displaystyle{ 345^{2}\equiv 41\pmod{856}. }[/math]

In the case that [math]\displaystyle{ \sqrt{-856}\bmod{41} }[/math] has no answer, then [math]\displaystyle{ r\equiv \sqrt{-856}\pmod{b\cdot 856+41} }[/math] 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