Euclidean Algorithms and Congruences
Square Roots Modulo a Prime: the Shanks-Tonelli Algorithm
Extracting square roots modulo a prime: the easy congruence classes, the general Shanks-Tonelli algorithm, and lifting to prime powers.
Engineering / MathematicsEuclidean Algorithms and Congruences2 min readKV-MATH-0520
Given a quadratic residue modulo a prime, finding an actual square root is a separate problem from deciding that one exists. For most primes a single exponentiation suffices; the general case needs Shanks-Tonelli.
The easy case
When the prime is congruent to three modulo four, the square root is given directly by an exponentiation.
The general algorithm
Shanks-Tonelli handles any odd prime. Write p - 1 as an odd number times a power of two. The algorithm works inside the two-power part of the cyclic group, progressively killing off the obstruction.
Shanks-Tonelli
- Split the group orderWrite p - 1 as Q times 2^S with Q odd.
- Find a non-residuePick random values until the Legendre symbol is -1. Expected two tries.
- InitialiseSet up a candidate root and a correction term from the non-residue raised to Q.
- IterateDetermine the order of the current error term within the two-power subgroup and square the correction down to match; multiply it in.
- TerminateWhen the error term becomes the identity, the candidate is a root.
Cost
Prime powers and composites
Roots modulo a prime power are obtained by Hensel lifting from the prime case. Roots modulo a composite require the factorisation, and are assembled by the Chinese remainder theorem — one root per odd prime power, so a composite with k distinct odd prime factors has 2^k roots.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.4.3. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.