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