Kunerth's algorithm

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 uses modular operations that are often easy when the given number is prime.

Algorithm

To find ${\displaystyle y}$ from a given value

${\displaystyle B=y^{2}{\bmod {N}},}$

it takes the following steps:

1. Find the modular square root ${\displaystyle r\equiv {\sqrt {\pm N}}{\pmod {B}}}$. This step is quite easy when ${\displaystyle B}$ is a prime, irrespective of how large ${\displaystyle N}$ is.
2. Solve a quadratic equation associated with the modular square root of ${\displaystyle w^{2}=A\cdot z^{2}+B\cdot z+C}$. Most of Kunerth's examples in his original paper solve this equation by having ${\displaystyle C}$ be a integer square and thus setting ${\displaystyle z}$ to zero.

   Expand the left hand side of the following equation:

   ${\displaystyle ((B\cdot z+r)^{2}+(B\cdot F\mp N))/B=w^{2}.}$

   Expanding the left hand side results in a quadratic form ${\displaystyle A\cdot z^{2}+D\cdot z+C+F}$. One can then make sure that the equation can be solved by adjusting ${\displaystyle F}$ so as to make ${\displaystyle C+F}$ a square.

3. Having solved the associated quadratic equation we now have the variables ${\displaystyle w}$ and set ${\displaystyle v}$ = ${\displaystyle r}$ (if ${\displaystyle C}$ in the quadratic is a natural square).
4. Solve for variables ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ the following equation:

   ${\displaystyle \alpha =w(v+w\beta ),}$

5. Obtain a value for ${\displaystyle X}$ via factorization of the following polynomial:

   ${\displaystyle \alpha ^{2}\cdot x^{2}+(2\alpha \beta -N)x+(\beta ^{2}-(y^{2}{\bmod {N}}))}$

   obtaining an answer like

   ${\displaystyle (-37+9x)(1+25x)}$

6. Obtain the modular square root by the equation. Remember to set ${\displaystyle X}$ such that the term above is zero. Thus ${\displaystyle X}$ would be 37/9 or -1/25.

   ${\displaystyle y\equiv \alpha X+\beta {\pmod {N}}.}$

Example

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

Then expand the polynomial:

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

into

${\displaystyle 25+26z+41z^{2}}$

Since, in this case the C term is a square, we take ${\displaystyle w=5}$ and compute ${\displaystyle v=13}$ (in general, ${\displaystyle v=41\cdot z+13}$).

Solve for ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ the following equation

${\displaystyle \alpha ==w(v+w\beta )}$

getting the solution ${\displaystyle \alpha =15}$ and ${\displaystyle \beta =-2}$. (There may be other pairs of solutions to this equation.)

Then factor the following polynomial:

${\displaystyle \alpha ^{2}x^{2}+(2\alpha \beta -856)x+(\beta ^{2}-41)}$

obtaining

${\displaystyle (-37+9x)(1+25x)}$

Then obtain the modular square root via

${\displaystyle 15\cdot (37\cdot 9^{-1})+(-2)\equiv 345{\pmod {856}}.}$

Verify that ${\displaystyle 345^{2}\equiv 41{\pmod {856}}.}$

In the case that ${\displaystyle {\sqrt {-856}}{\bmod {41}}}$ has no answer, then ${\displaystyle r\equiv {\sqrt {-856}}{\pmod {b\cdot 856+41}}}$ can be used instead.

See also

• Methods of computing square roots

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 url="https://pdfhost.io/v/~OwxzpPNA_KUNERTH_1878" retrieved="09/09/2024"
2. Leonard Eugene Dickson, "History of Numbers", vol 2, pp. 382–384.

• 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