Calculating square roots modulo a prime, using the Tonelli-Shanks algorithm

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 r2 = n mod p.

Sometimes it’s trivial. 0 is always a square, regardless of p because 02 = 0 mod p. Or if p is the prime 2, then both of the options for n are squares, because 02 = 0 mod 2 and 12 = 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 = 159128 = 1 mod 257, so 159 IS a square mod 257
  • 160(257 – 1) / 2 = 160128 = 256 mod 257, so 160 IS NOT a square mod 257
  • 4855(7883 – 1)/2 = 48553941 = 1 mod 7883, so 4855 IS a square mod 7883
  • 4856(7883 – 1)/2 = 48563941 = 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 pr.

Example:

  • 4855 is a square mod 7883, and 7883 mod 4 = 3. So the square roots are 4855(7883 + 1)/4 = 48551971 = 6047 and 7883 – 6047 = 1836. As a check, 60472 = 4855 mod 7883 and 18362 = 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 * 21 and 257 – 1 = 1 * 28.

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s