Kunerth's algorithm

Kunerth's algorithm is an algorithm to determine the modular square root of a number.[1][2] 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

do the following steps

1) find the modular square root of This step is quite easy, no matter how big the original modulus is, if is a prime.
2) solve a quadratic equation associated with the modular square root of . 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 then
You can always ensure that the quadratic can be solved by adjusting the N term(modulus) in the above equation. Thus
will ensure a quadratic of
You can then adjust F to ensure that C+F is a square. Quite large modula, such as can have their square roots taken quickly via this method.
The parameters of the polynomial expansion are quite fluid, in that can be done, for instance. It is quite easy to set X and Y so that is a square. The modular square root of 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 two more variables, alpha and beta by the following equation
alpha == w (v + w beta )
This is not a modular operation and that alpha and beta could have many paired answers.
5) Obtain a value for X via a factorization of the following polynomial.
obtaining an answer like
(-37 + 9 x) (1 + 25 x)
6) Obtain the modular square root by the equation. Remember to set X so that the term above is zero. Thus X would be 37/9 or -1/25.

Example

To obtain first obtain

Then expand out the following polynomial

which is

Since, in this case the C term in the quadratic is a natural square then

Set and (If z had a value then set )
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
obtaining
Then obtain the modular square root via
Verify that

In the case that has no answer then 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

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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.