This article needs attention from an expert in Mathematics. The specific problem is: the article as it stands is generally incomprehensible.. WikiProject Mathematics may be able to help recruit an expert. (January 2025)

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.

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

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.

• 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