##  [Tonelli–Shanks Algorithm](/tonelli-shanks-algorithm) 

  ##  [Tonelli–Shanks Algorithm](https://puremath.quantumdictionary.io/tonelli-shanks-algorithm-0) 

  

 [![Pure Mathematics Dictionary](/sites/default/files/styles/large/public/2026-01/Pure%20Mathematics.png.webp?itok=5pZnFQ59)](/topic-specific-dictionaries/mathematics-logic/pure-mathematics)

- Mathematics & Logic -

**Pure Mathematics Dictionary**

 







 

 

 

 



 

 

 

 

Definition

Deterministic algorithm to compute a square root of a given quadratic residue a modulo an odd prime p (find x with x^2 ≡ a (mod p)) by exponentiation and iterative adjustments using the factorization p−1 = q·2^s and a quadratic nonresidue.