Modular Square Root Hot Sheet

Use this page when the task is:

\[ x^2 \equiv a \pmod p \]

with one prime modulus and you want the shortest safe route back to Tonelli-Shanks.

Do Not Use When

• the unknown is in the exponent rather than the base
• the modulus is composite or a prime power and you have not separated that case
• the real target is general x^k ≡ a (mod p) rather than square roots

Choose By Signal

• recover one square root modulo one prime -> mod-sqrt-tonelli-shanks.cpp
• recover the exponent from a^x ≡ b (mod m) -> Discrete Log hot sheet
• solve several residue conditions at once -> Chinese Remainder / Linear Congruences
• only need power / inverse / factorial helpers -> Modular Arithmetic hot sheet

Core Invariants

• for odd prime p, test reachability first with Euler's criterion
• split:

\[ p - 1 = q \cdot 2^s \]

with q odd

• Tonelli-Shanks shrinks the remaining mismatch inside a subgroup of 2-power order
• if r is one root, then p-r is the other nonzero root

Main Traps

• applying the Legendre test under a composite modulus
• forgetting the a = 0 and p = 2 edge cases
• assuming Tonelli-Shanks is the route for general k-th roots
• returning "no root" without normalizing a mod p first

Exact Starters In This Repo

• exact starter -> mod-sqrt-tonelli-shanks.cpp
• flagship in-lane rep -> Sqrt Mod
• compare point -> BSGS / Discrete Log
• nearby foundation -> Modular Arithmetic hot sheet

Reopen Paths

• full lesson -> Modular Square Root / Discrete Root
• broader chooser -> Number Theory cheatsheet
• template chooser -> Template Library