Tonelli-Shanks Modular Square Root Calculator

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. Enter n and a prime p and this calculator checks Euler’s criterion and, if a root exists, runs Tonelli-Shanks to return it.