Cipolla's algorithm
In computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form where , so n is the square of x, and where is an odd prime. Here denotes the finite field with elements; . The algorithm is named after Michele Cipolla, an Italian mathematician who discovered it in 1907. Apart from prime moduli, Cipolla's algorithm is also able to take square roots modulo prime powers.
- Comment
- enIn computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form where , so n is the square of x, and where is an odd prime. Here denotes the finite field with elements; . The algorithm is named after Michele Cipolla, an Italian mathematician who discovered it in 1907. Apart from prime moduli, Cipolla's algorithm is also able to take square roots modulo prime powers.
- Has abstract
- enIn computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form where , so n is the square of x, and where is an odd prime. Here denotes the finite field with elements; . The algorithm is named after Michele Cipolla, an Italian mathematician who discovered it in 1907. Apart from prime moduli, Cipolla's algorithm is also able to take square roots modulo prime powers.
- Is primary topic of
- Cipolla's algorithm
- Label
- enCipolla's algorithm
- Link from a Wikipage to another Wikipage
- Addition
- Algorithm
- Associativity
- Binary numeral system
- Category:Articles containing proofs
- Category:Modular arithmetic
- Category:Number theoretic algorithms
- Characteristic (algebra)
- Commutativity
- Complex number
- Computational number theory
- Congruence relation
- Distributivity
- Element (mathematics)
- Euler's criterion
- Fermat's little theorem
- Field (mathematics)
- Field extension
- Freshman's dream
- Identity element
- Imaginary unit
- Integer polynomial
- Inverse element
- Italy
- Lagrange's theorem (number theory)
- Legendre symbol
- Mathematician
- Michele Cipolla
- Multiplication
- Numerical digit
- Parity (mathematics)
- Prime number
- Square root
- Talk:Cipolla's algorithm
- Tonelli–Shanks algorithm
- Trial and error
- SameAs
- 4iFxL
- Cipolla's algorithm
- m.09v19yz
- Q5121280
- Алгоритм Чиполлы
- Subject
- Category:Articles containing proofs
- Category:Modular arithmetic
- Category:Number theoretic algorithms
- WasDerivedFrom
- Cipolla's algorithm?oldid=1116824954&ns=0
- WikiPageLength
- 13507
- Wikipage page ID
- 25766973
- Wikipage revision ID
- 1116824954
- WikiPageUsesTemplate
- Template:Number theoretic algorithms