Kunerth's Algorithm

Kunerth's algorithm is an algorithm for computing the modular square root of a given number.Leonard Eugene Dickson, "History of Numbers", vol 2, pp. 382–384.
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^ \bmod,$
it takes the following steps:

# find the modular square root of $r\equiv \sqrt \pmod$. This step is quite easy, irrespectively of how big ''N'' when $B$ is a prime.
# solve a quadratic equation associated with the modular square root of $w^=A\cdot z^+B\cdot 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\cdot z + r)^2 \pm N)/B = w^.$
#:One can always make sure that the quadratic can be solved by adjusting the modulus ''N'' in the above equation. Thus
#:::$((B\cdot z + r)^2 +(B\cdot F+N))/B = w^$
#:::will ensure a quadratic of $A\cdot z^+D\cdot z+C+F$.
#:One can then adjust ''F'' to make sure that $C+F$ is a square. For large moduli, such as $\sqrt\bmod$, 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\cdot RSA260)/(67y)$ can be done, for instance. It is quite easy to choose ''X'' and ''Y'' such that $(r^+X\cdot RSA260)/(67y)$ is a square. The modular square root of $\sqrt\bmod$ can be taken this way.
# 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).
# Solve for variables $\alpha$ and $\beta$ the following equation:
#::$\alpha = w (v + w \beta ),$
# Obtain a value for ''X'' via factorization of the following polynomial:
#::$\alpha^ \cdot x^ + (2 \alpha \beta - N) x +(\beta^ - (y^\bmod))$
#:obtaining an answer like
#::$(-37 + 9 x) (1 + 25 x)$
# 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.$

Example

To obtain $\sqrt\bmod,$ first obtain $\sqrt\equiv 13\pmod$.

Then expand the polynomial:
:$((41 z + 13)^2 + 856)/41 = w^2$
into
:$25 + 26 z + 41 z^$
Since, in this case the ''C'' term is a square, we take $w=5$ and compute $v=13$ (in general, $v=41\cdot 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^ - 41)$

::obtaining

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

::Then obtain the modular square root via

::$15 \cdot (37\cdot 9^)+(-2) \equiv 345\pmod.$

:Verify that $345^\equiv 41\pmod.$

In the case that $\sqrt\bmod$ has no answer, then $r\equiv \sqrt\pmod$ 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

{{number theoretic algorithms

Mathematics articles needing expert attention
Algorithms
Cryptographic algorithms