## Tonelli-Shanks Algorithm

### November 23, 2012

One of the operations of modular arithmetic, and an important step in many algorithms of number theory, is finding modular square roots. In the expression *x*^{2} ≡ *a* (mod *p*), *x* is a modular square root of *a*; for instance, 62 is a square root of 2, mod 113, because 62 * 62 = 3844 = 36 * 113 + 2. Like real numbers, modular square roots come in pairs, so -62 ≡ 51 (mod 113) is also a square root of 2.

The usual method for finding modular square roots involves an algorithm developed by Alberto Tonelli in the 1890s; there are several variants, including one due to Daniel Shanks in 1973, one of which we saw in a previous exercise. The particular variant that we will look at today is described at http://www.math.vt.edu/people/brown/doc/sqrts.pdf.

We will assume that the modulus *p* = *s* · 2^{e} + 1 is an odd prime, that the number *a* for which we seek a square root is coprime to *p*, and that the Legendre symbol (*a*/*p*) is 1, which indicates that the square root exists. Find an *n* such that *n*^{(p−1)/2} ≡ −1 (mod *p*); it won’t take long if you start from *n* = 2 and increase *n* by 1 until you find one. Then set *x* ≡ *a*^{(s+1)/2} (mod *p*), *b* ≡ *a*^{s} (mod *p*), *g* ≡ *n ^{s}* (mod

*p*), and

*r*=

*e*. Next find the smallest non-negative integer

*m*such that

*b*

^{2m}≡ 1 (mod

*p*), which is done by repeated squarings and reductions. If

*m*is zero, you’re finished; report the value of

*x*and halt. Otherwise, set

*x*to

*x*·

*g*

^{2r−m−1}(mod

*p*), set

*b*to

*b*·

*g*

^{2r−m}(mod

*p*), set

*g*to

*g*

^{2r−m}(mod

*p*), and set

*r*=

*m*, then loop back and compute a new

*m*, continuing until

*m*is zero.

As an example we find the square root of 2 mod 113. First compute *p* = 113 = 7 · 2^{4} + 1 and *n* = 3, then *x* = 16, *b* = 15, *g* = 40, and *r* = 4. The first computation of *m* is 2, so set *x* = 62, *b* = 1, *g* = 98, and *r* = 2. Then the second computation of *m* is 0, so *x* = 62 is a square root of 2 (mod 113), and so is 113 – 62 = 51.

Your task is to write a function that computes modular square roots according to the algorithm described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

[...] Pages: 1 2 [...]

A python version.

when i try to execute, i get the error as No module named ma.primee

This is great, was looking for an implementation of this instead of just the theory on Wikipedia, thank you!