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

y^{2}{\bmod {N}}

do the following steps

1) find the modular square root of

r\equiv {\sqrt {\pm N}}{\bmod {(y^{2}{\bmod {N}})}}

This step is quite easy, no matter how big the original modulus is, if

y^{2}{\bmod {N}}

is a prime.

2) 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 natural square and thus setting z to zero.

Expand out the following equation to obtain the quadratic

if

y^{2}{\bmod {N}}\equiv B

then

((B*z+r)^{2}\pm N)/B==w^{2}

You can always ensure that the quadratic can be solved by adjusting the N term(modulus) 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

You can then adjust F to ensure that C+F is a square. Quite large modula, such as

{\sqrt {67}}{\bmod {67*F+RSA260}}

can have their square roots taken quickly via this method.

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

((67z+r)^{2}+X*RSA260)/(Y*67)

can be done, for instance. It is quite easy to set X and Y so that

(r^{2}+X*RSA260)/(y*67)

is a square. The modular square root of

{\sqrt {y*67}}{\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 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.

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)

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.

y\equiv alpha*X+beta{\bmod {N}}

Example

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

Then expand out the following polynomial

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

which is

25+26z+41z^{2}==5^{2}

Since, in this case the C term in the quadratic is a natural square then $W=5$

Set

w=5

and

v=13

(If z had a value then set

v=41*z+13

)

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

alpha^{2}x^{2}+(2*alpha*beta-856)x+(beta^{2}-41)

obtaining

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

Then obtain the modular square root via

15*(37*9^{-1})+(-2){\bmod {856}}\equiv 345

Verify that

345^{2}{\bmod {856}}\equiv 41

In the case that ${\sqrt {-856}}{\bmod {41}}$ has no answer then $r\equiv {\sqrt {-856}}{\bmod {(b*856+41)}}$ can be used instead.

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.

[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

Number-theoretic algorithms
Primality tests	AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin
Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Pritchard Sieve of Sundaram Wheel factorization
Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Euclidean division	Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT
Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks Berlekamp Kunerth
Other algorithms	Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL; KZ) Modular exponentiation Montgomery reduction Schoof Trachtenberg system
Italics indicate that algorithm is for numbers of special forms

Kunerth's algorithm

Example

See also

References