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 relies on modular operations that is often easy when the given number is prime.
Algorithm
To find y from a given value
![{\displaystyle B=y^{2}{\bmod {N}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f148cea4d01d25a6efeeac96203ba471cb7d4aa6)
it takes the following steps:
- find the modular square root of
. This step is quite easy, irrespectively of how big N when
is a prime.
- 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 integer square and thus setting z to zero.
- Expand out the following equation to obtain the quadratic
![{\displaystyle ((B\cdot z+r)^{2}\pm N)/B=w^{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1206c4bf65603dd65ce56da7984033332e87ff84)
- One can always make sure that the quadratic can be solved by adjusting the modulus N in the above equation. Thus
![{\displaystyle ((B\cdot z+r)^{2}+(B\cdot F+N))/B=w^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8d03c35ab4f60012633e24c2615bd139da6064d)
- will ensure a quadratic of
.
- One can then adjust F to make sure that
is a square. For large moduli, such as
, can have their square roots computed quickly via this method.
- The parameters of the polynomial expansion are quite flexible, in that
can be done, for instance. It is quite easy to choose X and Y such that
is a square. The modular square root of
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
and
the following equation:
![{\displaystyle \alpha =w(v+w\beta ),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/799708c8f673154849579fa358f561f956f11d8f)
- Obtain a value for X via factorization of the following polynomial:
![{\displaystyle \alpha ^{2}\cdot x^{2}+(2\alpha \beta -N)x+(\beta ^{2}-(y^{2}{\bmod {N}}))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a90195d820a160a687f1eeac824dc12c1fb2ad29)
- obtaining an answer like
![{\displaystyle (-37+9x)(1+25x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a74418d87fbb80ef59995f8fa561240d96a5c305)
- 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.
![{\displaystyle y\equiv \alpha X+\beta {\pmod {N}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5b170d207452bbcb90ac56c36a2ea4bff542189)
Example
To obtain
first obtain
.
Then expand the polynomial:
![{\displaystyle ((41z+13)^{2}+856)/41=w^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61e41df22d6f495bc57ac6f44ebc103269460002)
into
![{\displaystyle 25+26z+41z^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f683c7ec828fea6d06482b203e14db97dcd4483)
Since, in this case the C term is a square, we take
and compute
(in general,
).
- Solve for
and
the following equation
![{\displaystyle \alpha ==w(v+w\beta )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e67a2c71cf21285d0c26328b627c013b2f72c3b3)
- getting the solution
and
. (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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a5cf4dc55f843074f04457989e023acda4e0831)
- obtaining
![{\displaystyle (-37+9x)(1+25x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a74418d87fbb80ef59995f8fa561240d96a5c305)
- Then obtain the modular square root via
![{\displaystyle 15\cdot (37\cdot 9^{-1})+(-2)\equiv 345{\pmod {856}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b83e17613e0c7e637d178247d997f11000e028e5)
- Verify that
![{\displaystyle 345^{2}\equiv 41{\pmod {856}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfb90f6f6b4aa6141646b4b46ac7495e14cf1241)
In the case that
has no answer, then
can be used instead.
See also
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.
- 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