Suppose you are working in a prime field GF(*p*) and you want to know whether a particular element *n* is a square – that is to say, whether there is some other element *r* that satisfies *r*^{2} = *n* mod *p*.

Sometimes it’s trivial. 0 is always a square, regardless of *p* because 0^{2} = 0 mod *p*. Or if *p* is the prime 2, then both of the options for *n* are squares, because 0^{2} = 0 mod 2 and 1^{2} = 1 mod 2.

Other than these trivial cases, there is a quick way to tell whether a given *n* is a square – raise it to the (*p* – 1) / 2 power, mod *p*. This will either be the number 1 or the number *p* – 1.

If *n*^{(p – 1) / 2} = 1 mod *p* then *n* is a square mod *p*. If *n*^{(p – 1) / 2} = *p* – 1 mod *p*, then *n* is not a square.

This is called Euler’s criterion.

Some quick examples:

- 159
^{(257 – 1) / 2}= 159^{128}= 1 mod 257, so 159 IS a square mod 257 - 160
^{(257 – 1) / 2}= 160^{128}= 256 mod 257, so 160 IS NOT a square mod 257 - 4855
^{(7883 – 1)/2}= 4855^{3941}= 1 mod 7883, so 4855 IS a square mod 7883 - 4856
^{(7883 – 1)/2}= 4856^{3941}= 7882 mod 7883, so 4856 IS NOT a square mod 7883

So if all you care about is *whether* there is a square root, it’s fast and easy.

But what if you want to know *what the square root is*?

Besides the trivial cases above, you have a decent chance to get lucky. If *p* = 3 mod 4 there is an easy way to find the square root – raise *n* to (*p* + 1) / 4. This is one square root – call it *r*. The other square root is *p* – *r*.

Example:

- 4855 is a square mod 7883, and 7883 mod 4 = 3. So the square roots are 4855
^{(7883 + 1)/4}= 4855^{1971}= 6047 and 7883 – 6047 = 1836. As a check, 6047^{2}= 4855 mod 7883 and 1836^{2}= 4855 mod 7883 as desired.

But what if *p* = 1 mod 4, like the *p* = 257 example?

In that case, there’s no way to immediately write down the answer. But there is an algorithm, discovered by Alberto Tonelli in 1891, and rediscovered by Daniel Shanks in 1973. This is called the Tonelli-Shanks algorithm.

You start by dividing *p* – 1 into a power of 2 and an odd part. For example, 7883 – 1 = 3941 * 2^{1} and 257 – 1 = 1 * 2^{8}.

Then you make an initial guess for *r* which is probably wrong.

Then you perform a series of operations, which leads you to another, better, guess.

You keep making guesses until you get it right. You may have to make a guess for every power of 2 that divides *p* – 1, but no more than that. This isn’t exactly *immediate*, but it is a heck of a lot better than trying different values of *r* until you eventually find one.

I implemented a PowerShell script that calculates the square root of a given *n* modulo a given prime *p*, using the Tonelli-Shanks algorithm. Here is an input and output for a rather high power of 2:

`> `

.\`tonelli-shanks.ps1 -p 257 -n 159`

Looking for r so that r^2 = 159 mod 257

257 - 1 = 1 * 2^8

3 is a nonsquare modulo 257

Initial: m = 8, c = 3, t = 159, r = 159

159^(2^7) = 1 mod 257

3^(2^(8 - 7 - 1)) = 3 mod 257

Loop 1: m = 7, c = 9, t = 146, r = 220

146^(2^6) = 1 mod 257

9^(2^(7 - 6 - 1)) = 9 mod 257

Loop 2: m = 6, c = 81, t = 4, r = 181

4^(2^3) = 1 mod 257

81^(2^(6 - 3 - 1)) = 249 mod 257

Loop 3: m = 3, c = 64, t = 256, r = 94

256^(2^1) = 1 mod 257

64^(2^(3 - 1 - 1)) = 241 mod 257

Loop 4: m = 1, c = 256, t = 1, r = 38

Solutions:

38^2 = 159 mod 257

219^2 = 159 mod 257

## 2 thoughts on “Calculating square roots modulo a prime, using the Tonelli-Shanks algorithm”