Tonelli–Shanks algorithm
The Tonelli–Shanks algorithm (referred to by Shanks as the RESSOL algorithm) is used in modular arithmetic to solve for r in a congruence of the form r2 ≡ n (mod p), where p is a prime: that is, to find a square root of n modulo p. Tonelli–Shanks cannot be used for composite moduli: finding square roots modulo composite numbers is a computational problem equivalent to integer factorization. An equivalent, but slightly more redundant version of this algorithm was developed byAlberto Tonelliin 1891. The version discussed here was developed independently by Daniel Shanks in 1973, who explained:
- Comment
- enThe Tonelli–Shanks algorithm (referred to by Shanks as the RESSOL algorithm) is used in modular arithmetic to solve for r in a congruence of the form r2 ≡ n (mod p), where p is a prime: that is, to find a square root of n modulo p. Tonelli–Shanks cannot be used for composite moduli: finding square roots modulo composite numbers is a computational problem equivalent to integer factorization. An equivalent, but slightly more redundant version of this algorithm was developed byAlberto Tonelliin 1891. The version discussed here was developed independently by Daniel Shanks in 1973, who explained:
- Has abstract
- enThe Tonelli–Shanks algorithm (referred to by Shanks as the RESSOL algorithm) is used in modular arithmetic to solve for r in a congruence of the form r2 ≡ n (mod p), where p is a prime: that is, to find a square root of n modulo p. Tonelli–Shanks cannot be used for composite moduli: finding square roots modulo composite numbers is a computational problem equivalent to integer factorization. An equivalent, but slightly more redundant version of this algorithm was developed byAlberto Tonelliin 1891. The version discussed here was developed independently by Daniel Shanks in 1973, who explained: My tardiness in learning of these historical references was because I had lent Volume 1 of Dickson's History to a friend and it was never returned. According to Dickson, Tonelli's algorithm can take square roots of x modulo prime powers pλ apart from primes.
- Is primary topic of
- Tonelli–Shanks algorithm
- Label
- enTonelli–Shanks algorithm
- Link from a Wikipage to an external page
- archive.org/details/introductiontoth0000nive/page/110
- archive.org/details/introductiontoth0000nive
- resolver.sub.uni-goettingen.de/purl%3FGDZPPN002525739
- www.ocf.berkeley.edu/~gagnanda/mathstuff/RESSOL.pdf
- www.cmat.edu.uy/~tornaria/pub/Tornaria-2002.pdf
- Link from a Wikipage to another Wikipage
- Algorithm
- Category:Articles containing proofs
- Category:Modular arithmetic
- Category:Number theoretic algorithms
- Cipolla's algorithm
- Daniel Shanks
- Elliptic curves
- Euler's criterion
- Finite field
- Generalized Riemann hypothesis
- History of the Theory of Numbers
- Integer factorization
- Jacobi symbol
- Leonard Eugene Dickson
- Loop invariant
- Modular arithmetic
- Multiplicative group of integers modulo n
- Order (group theory)
- Polynomial time
- Prime number
- Quadratic residue
- Quadratic sieve
- Rabin cryptosystem
- SameAs
- fXTS
- m.09tbj7
- Q17104164
- Алгоритм Тонелли — Шенкса
- Subject
- Category:Articles containing proofs
- Category:Modular arithmetic
- Category:Number theoretic algorithms
- WasDerivedFrom
- Tonelli–Shanks algorithm?oldid=1083519745&ns=0
- WikiPageLength
- 18598
- Wikipage page ID
- 3667375
- Wikipage revision ID
- 1083519745
- WikiPageUsesTemplate
- Template:Cite book
- Template:Number theoretic algorithms
- Template:Reflist