##  [Modular Square Root Extraction](/modular-square-root-extraction-0) 

 Definition

The process of finding integers x satisfying x^2 ≡ a (mod n) when such solutions exist; i.e., extracting square roots in the ring Z/nZ or in its local factors when n is composite.

 

 

 

 

 

 





## Principle

Principle

Solvability depends on a being a quadratic residue modulo each prime power dividing n; for prime modulus p use algorithms like Tonelli–Shanks (if p odd) or simple inspection for p=2; for prime powers apply Hensel lifting; for composite n factorization plus Chinese remainder recombination reduces the problem to prime-power cases.

 

 

 

 

 





## Demonstration

Demonstration

Example: find x with x^2 ≡ 10 (mod 13). Squares modulo 13 show 6^2 = 36 ≡ 10 and 7^2 = 49 ≡ 10, so solutions are x ≡ 6 and x ≡ 7 (mod 13). For n composite, factor n, solve each prime‑power congruence, and combine via CRT to obtain all solutions modulo n.

 

 

 

 

## Misapplication

Misapplication

Assuming that a square root exists modulo a composite modulus without checking quadratic residuosity at each prime factor, or attempting CRT recombination without compatible local solutions; also treating Tonelli–Shanks as if it applied without checking p mod 4 conditions would be erroneous understanding.

 

 

 

 

 





## Consequence

Consequence

Correct extraction yields explicit root classes used in algorithms for primality, cryptographic protocols (and their attacks), and in solving quadratic congruences and lifting solutions to higher moduli.

 

 

 

 

## Reversal

Reversal

The inverse viewpoint is deciding quadratic residuosity (whether a is a square mod n) rather than constructing roots; when residuosity is hard to decide (e.g., composite n without factorization), extraction is infeasible and residuosity becomes the central question.

 

 

 

 

 





## Boundary

Boundary

Applies to quadratic congruences x^2 ≡ a (mod n) and relies on factorization structure of n; excludes general k-th root extraction unless adapted, and in practice may be infeasible without prime factorization of composite n.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Tension between working in prime fields F_p (where the ring is a field and standard algorithms apply) and composite moduli Z/nZ (non-field): the former allows direct algebraic inversion and efficient algorithms, the latter forces factorization and CRT or results in ambiguity when factors are unknown.

 

 

 

 

 





## Synthesis

Synthesis

Modular square root extraction is the procedure of checking quadratic residuosity locally at prime powers, computing roots in each local factor (Tonelli–Shanks, Hensel lifting), and recombining via the Chinese remainder theorem to produce all integer solutions x modulo n when they exist.