HesapHanem

Tonelli-Shanks Modular Square Root Calculator

Enter n and a prime p to find the modular square root.

How it is calculated

The goal is an r with r² ≡ n (mod p). The tool first reduces n modulo p and confirms that p is prime (by trial division). It then applies Euler's criterion: a root exists only if n^((p-1)/2) ≡ 1 (mod p). If not, there is no result. Next it writes p - 1 = Q × 2^S. When S = 1 (p ≡ 3 mod 4), the root is simply n^((p+1)/4) mod p. Otherwise the Tonelli-Shanks loop runs, using a quadratic non-residue found by search, until the correction term reaches 1.

If r is a root, so is p - r, and the tool shows both, smaller first, plus a check line r² mod p. A negative n or one larger than p is reduced mod p first. If n is a multiple of p, the only root is 0. p = 2 is handled as a special case. A composite p, a non-residue n or a p below 2 gives no result.

Worked example

Find the square root of 10 modulo 13. Euler's criterion: 10^6 mod 13 = 1, so a root exists. Here 13 - 1 = 12 = 3 × 2², so S = 2 and the Tonelli-Shanks loop is used rather than the shortcut. It arrives at 6 (and 7). Check: 6² = 36, and 36 - 2 × 13 = 10, so 6² mod 13 = 10. The second root is 13 - 6 = 7, since 7² = 49 and 49 - 3 × 13 = 10 as well.

Try this example →

Common mistakes

  • Using a composite modulus such as 15. The method needs a prime p, and the tool returns nothing for 15 even if square roots mod 15 exist.
  • Expecting a root for every n. Only quadratic residues have one; for n = 5 and p = 13 there is none, and the tool gives no result.
  • Treating the answer as unique. There are always two roots, r and p - r, except for n = 0 mod p.
  • Confusing the modular root with an ordinary square root. The ordinary root of 10 is 3.16, but the root of 10 modulo 13 is 6, since 6² = 36 leaves remainder 10.
  • Entering n already reduced and then forgetting it is reduced anyway: n = 23 and n = 10 behave identically mod 13.

About this calculator

The Tonelli-Shanks algorithm finds a modular square root — a value r such that r² ≡ n (mod p) — for a given number n and odd prime modulus p, one of the fundamental operations in computational number theory. Before running the main algorithm, it checks Euler’s criterion: n is a quadratic residue mod p (meaning a square root exists at all) exactly when n^((p−1)/2) ≡ 1 (mod p). When p ≡ 3 (mod 4), the square root has a direct closed-form shortcut, but Tonelli-Shanks is needed for the harder general case where p ≡ 1 (mod 4), using repeated squaring against a quadratic non-residue to peel off factors of 2 from p−1.

This operation underlies practical cryptography — most notably decompressing a point on an elliptic curve from its x-coordinate in compressed public-key formats used by ECDSA and Bitcoin, where the y-coordinate must be recovered as a modular square root of a value derived from the curve equation.

Was this helpful?

You can pick up to 3 reactions.

Comments (1)

  • Editorial team

    This tool is best for small primes, where you can check a hand calculation or test your own implementation. It works with ordinary machine-sized integers and tests the modulus by trial division, so the 256-bit primes used by real elliptic curves are far outside its reach. A handy test case: square root of 56 mod 101 gives 37 and 64. Which language are you implementing Tonelli-Shanks in, and which cases have given you trouble?

Popular calculators

Loan Calculator

Monthly payment, total interest and full amortization schedule.

Percentage Calculator

Percent change, percent of, and ratio calculations.

Discount Calculator

Calculate final price, savings, and discount amount.

BMI Calculator

Body mass index from height and weight (metric or imperial).

Age Calculator

Compute your exact age in years, months and days from a birth date.

Compound Interest Calculator

Calculate the final amount and interest earned with compounding.

All Calculators