Tonelli-Shanks Square Root Calculator

The loop that finds a square root in a finite field.

  • Every loop step
  • Both roots
  • Non-residue test
A small rounded clay table with a large soft clay block and a smaller block nested beside it, a curved clay arrow between them, and a few loose rounded beads in soft daylight.

The guide

Square roots in a finite field: why half the numbers have none, and why the Tonelli-Shanks loop always stops

Why half of all numbers have no square root modulo a prime, why the loop halts because M shrinks, why one prime shape needs a single exponentiation, and why a composite modulus is as hard as factoring.

  • 28 and 13 square roots of 5 modulo 41
  • 40, not 28 what the 3 modulo 4 shortcut gives for 5 modulo 41
  • 11 passes for 3221225473, where p - 1 is 3 times 2 to the 30th
  • 16 roots of 1 modulo 1155, which is 3 x 5 x 7 x 11
Read the full guide Fold the guide 7 min · 12 sources

Ask for the square root of 5 on a calculator and you get a number with a decimal point. Ask for it on a clock that only runs from 0 to 40, where 41 wraps back to 0, and the question changes. Which whole number, squared, lands on 5 after the wrap?

The answer is 28. Check it: 28 squared is 784, and 784 minus 19 times 41 is 5. The other answer is 13, which is 41 minus 28. That small clock is arithmetic modulo the prime 41, and finding square roots on it is a real problem with a real algorithm.

Why half the numbers have none

The integers modulo a prime p form a finite field, the most common example of one, in which you can add, subtract, multiply and divide. In a field a polynomial of degree two has at most two roots. So if r squared equals n, the only other number with the same square is minus r, which is p minus r. Squaring pairs the non-zero numbers up two to one.

That pairing is why half of them miss out. The Wikipedia page on quadratic residues says that modulo an odd prime p there are (p + 1) / 2 residues counting 0 and (p - 1) / 2 non-residues. Modulo 41 that is 20 non-residues among the 40 non-zero numbers.

Euler’s criterion sorts them with one exponentiation. Raise n to the power (p - 1) / 2. The result is 1 if n has a square root and p - 1, that is minus 1, if it has none. The criterion dates from a 1748 paper by Leonhard Euler, and the Legendre symbol writes it compactly.

Why only 1 or minus 1? Fermat’s little theorem says that n to the power p - 1 is 1 when n is not a multiple of p. The power (p - 1) / 2 is a square root of that 1, and in a field the only square roots of 1 are 1 and minus 1. Try it. Three modulo 41 gives 3 to the 20th, which is 40, so 3 has no square root. Five gives 1, so it has two.

The loop and why it halts

Write p - 1 as Q times 2 to the S with Q odd. For 41 that is 5 times 2 cubed. Tonelli-Shanks, which Shanks called RESSOL, starts from a non-residue z and sets M to S, c to z to the Q, t to n to the Q and R to n to the power (Q + 1) / 2. It is the version Daniel Shanks developed independently in 1973, an equivalent one having been published by Alberto Tonelli in 1891. Shanks, an American mathematician, was also the first person to compute pi to 100,000 decimal places.

For 5 modulo 41 the start is Q = 5, S = 3, z = 3, c = 38, t = 9 and R = 2. Two facts are true at every moment: R squared equals t times n, and t is a power of two root of 1. If t is 1, then R is the answer.

Otherwise find the least i, with 0 less than i less than M, such that t to the 2 to the i is 1. The multiplicative order of t is a power of two, so such an i exists. Then set b to c to the 2 to the M minus i minus 1, and update M to i, c to b squared, t to t times b squared and R to R times b.

For our example the first pass finds i = 2, because t is 9, then 40, then 1. It gives b = 38, M = 2, c = 9, t = 40 and R = 35. The second pass finds i = 1 and gives b = 9, M = 1, c = 40, t = 1 and R = 28. The roots are 28 and 13.

Why must it stop? Because i is below M, and M becomes i. M falls on every pass and cannot go below 1. So a prime with S = 3 needs at most two passes, and in general at most S - 1. Over every residue modulo 41 the most the loop ever takes is two.

A residue is also the one thing you cannot use as z. The loop relies on c to the 2 to the M minus 1 being minus 1, which is true only for a non-residue. Use 2, a residue modulo 41, and the loop goes wrong: after one pass it can no longer find an i below M and reports no answer. The same signal catches a non-residue n. If the least i would equal M, no root exists.

The prime shape that needs one exponentiation

Finding z looks like a gap. The Wikipedia page on the algorithm says that no deterministic polynomial method is known for it, but that if the generalized Riemann hypothesis holds a non-residue exists below 2 times the square of the natural log of p. In practice half the numbers qualify, so a random try succeeds on average in two.

Now the shortcut. When p is 3 modulo 4, S equals 1, so t is already 1 and R is the answer straight away. The roots are plus and minus n to the power (p + 1) / 4, one exponentiation. Modulo 23, for 2, that gives 2 to the 6th, which is 18, and the other root is 5. The mistake is applying it everywhere. Modulo 41, which is 1 modulo 4, the shortcut gives 5 to the 10th, which is 40, not 28. Squared, 40 is 1, not 5. The shortcut gets a plausible number and no root.

Primes with a large power of two in p - 1 are where the loop earns its keep. Take p = 3221225473, which is 3 times 2 to the 30th plus 1, so S = 30. The tool finds the smallest non-residue 5 and the roots of 2532339937, the square of 123456789: they are 123456789 and 3097768684, found in 11 passes. The prime 2 to the 64th minus 2 to the 32nd plus 1 has S = 32; the roots of the square of 987654321987654321 take 12 passes.

How costly is that? The Wikipedia page gives an average of 2m + 2k + S(S - 1) / 4 + 1 / 2 to the S - 1, minus 9 modular multiplications, with m the bit length of p and k its number of one bits, and does not state how it counts. For 41 the formula gives 10.75, and for 3221225473 it gives 278.50. The same page, and the one on Cipolla’s algorithm, say that Cipolla’s method is better exactly when S(S - 1) exceeds 8m + 20. For 41 that is 6 against 68, so Tonelli-Shanks wins. For 3221225473 it is 870 and 276, so Cipolla wins.

Why a composite modulus is as hard as factoring

The algorithm needs a prime. The Wikipedia page is blunt: it cannot be used for composite moduli, where finding square roots is a computational problem equivalent to integer factorization. The Rabin cryptosystem is built on the same fact, inverting its squaring function being proven as hard as factoring, with four possible inputs for each output.

Four, because a product of two odd primes gives two roots for each prime. With the primes in hand the Chinese remainder theorem does the joining, as the page on it describes for pairwise coprime moduli. Take 4 modulo 15 = 3 times 5. Modulo 3 the roots are 1 and 2, modulo 5 they are 2 and 3, and the four combinations give 2, 7, 8 and 13.

Add primes and the count doubles. Modulo 1155 = 3 times 5 times 7 times 11 the number 1 has 16 roots, one for each choice of sign. If n is a non-residue modulo even one prime, there is no root at all. Without the factors none of this is possible, which is the point. Roots modulo a prime power can be lifted from a root modulo the prime, and Tonelli’s original version could handle them, but the tool leaves prime powers aside.

One more thing it has to be sure of is that p really is prime. The tool tests it with Miller-Rabin, using the twelve bases from 2 to 37, which the Wikipedia page gives as enough for every number below 2 to the 64th.

What the tool does not do

It does not factor anything. It cannot take a square root modulo a number it is not given the primes of, and it refuses numbers above 20 digits. It does not break a cryptosystem; it solves one narrow equation in a field and shows each step of the solution. What it can do is show why the loop is safe. M falls, so the passes are few. The invariants hold, so the answer is checked at every step. And the final check, squaring the root and comparing it with n, is the one that matters most.

Sources

Every source consulted for this guide. Links checked November 21, 2026.

  1. Tonelli-Shanks algorithm Wikipedia
  2. Quadratic residue Wikipedia
  3. Euler's criterion Wikipedia
  4. Legendre symbol Wikipedia
  5. Cipolla's algorithm Wikipedia
  6. Rabin cryptosystem Wikipedia
  7. Chinese remainder theorem Wikipedia
  8. Miller-Rabin primality test Wikipedia
  9. Fermat's little theorem Wikipedia
  10. Finite field Wikipedia
  11. Multiplicative order Wikipedia
  12. Daniel Shanks Wikipedia