Kunerth's algorithm explained

Kunerth's algorithm is an algorithm for computing the modular square root of a given number.^{[1] [2]} 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

B = y ^{2} \bmod{N}, it takes the following steps:

1. find the modular square root of

r\equiv \sqrt{\pm N} \pmod{B} . This step is quite easy, irrespectively of how big N when B is a prime.

1. 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 integer square and thus setting z to zero.

Expand out the following equation to obtain the quadratic

((B ⋅ 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

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

will ensure a quadratic of

A ⋅ z ^{2} + D ⋅ z + C + F .

One can then adjust F to make sure that

C + F is a square. For large moduli, such as \sqrt{ 67 }\bmod{ 67 F + RSA 260 } , can have their square roots computed quickly via this method.

The parameters of the polynomial expansion are quite flexible, in that

(( 67 z + r) ^{2+X ⋅} RSA 260 )/( 67 y) can be done, for instance. It is quite easy to choose X and Y such that (r ^{2} + X ⋅ RSA 260 )/( 67 y) is a square. The modular square root of \sqrt{ 67 y}\bmod{RSA 260 } can be taken this way.

1. 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).
2. Solve for variables

\alpha and \beta the following equation:\alpha = w (v + w \beta ),

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

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

obtaining an answer like

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

1. 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:

(( 41 z + 13 ) ^{2} + 856 )/ 41 = w ^{2} into25 + 26 z + 41 z ^{2} Since, in this case the C term is a square, we take w =5 and compute v =13 (in general, v =41 ⋅ 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 + 9 x) ( 1 + 25 x)

Then obtain the modular square root via

15 ⋅ ( 37 ⋅ 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 ⋅ 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

Notes and References

1. Adolf Kunerth, "Sitzungsberichte. Academie Der Wissenschaften" vol 78(2), 1878, p 327-338 (for quadratic equation algorithm), pp. 338–346 (for modular quadratic algorithm), available at Ernest Mayr Library, Harvard University
2. Leonard Eugene Dickson, "History of Numbers", vol 2, pp. 382–384.