Discrete Root¶

Prime-mod square-root extraction through quadratic-residue tests and Tonelli-Shanks first, with primitive-root and discrete-root machinery kept as the follow-up boundary.

Topic slug: math/modular-square-root-discrete-root
Tutorial page: Open tutorial
Ladder page: Open ladder
Repo problems currently tagged here: 1
Repo companion pages: 4
Curated external problems: 2

Microtopics¶

quadratic-residue
legendre-symbol
tonelli-shanks
modular-square-root
primitive-root-boundary
discrete-root-boundary

Learning Sources¶

Source	Type
CP-Algorithms Library Sqrt Mod	`Reference`
cp-algorithms Discrete Root	`Reference`
OI Wiki Primitive Root	`Reference`
Library Checker Sqrt Mod	`Practice`

Practice Sources¶

Source	Type
Library Checker K-th Root Mod	`Practice`

Repo Companion Material¶

Material	Type
Modular Square Root hot sheet	`quick reference`
Sqrt Mod	`flagship note`
Template Library exact starter route	`starter route`
BSGS / Discrete Log	`compare point`

Curated External Problems¶

Core¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Sqrt Mod	`Library Checker`	`Hard`	Quadratic Residues	Math; Implementation	Modular Arithmetic; Binary Exponentiation; Prime Modulus	Modular Square Root; Tonelli-Shanks; Quadratic Residue; Prime Modulus	The cleanest verifier-style benchmark where the first exact route is just: test quadratic-residue reachability, then recover one root with Tonelli-Shanks.

Stretch¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
K-th Root Mod	`Library Checker`	`Hard`	Discrete Root	Math; Implementation	Modular Square Root; Discrete Log; Primitive Root	Primitive Root; Bsgs; Linear Congruence In Exponents	The natural follow-up once the square-root lane is trusted and the learner is ready to reduce x^k ≡ a (mod p) to primitive-root and discrete-log machinery.

Repo Problems¶

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`SQRTMOD`	Sqrt Mod	`primary`	`hard`	-	Note	Code

Regeneration¶

python3 scripts/generate_problem_catalog.py