Tonelli-Shanks Algorithm
Tonelli-Shanks computes square roots of quadratic residues modulo a prime p: the solutions x of x^2≡n (mod p).
Purpose
To compute modular square roots for prime moduli, used in elliptic curve point compression and number theory.
Mechanism
For p=2 or p≡3 (mod 4) there is a direct solution. In general, write p-1=2^s*q, find a quadratic non-residue z, set c=z^q, and iteratively adjust until the exponent drops to 1. Complexity O(s^2 log p).
Use cases
- Elliptic curve point decompression
- Modular square roots
- Number-theoretic algorithms