Cipolla's algorithm

In <a href="/facts/Computational_number_theory/7Lu5N57C">computational number theory</a>, Cipolla's algorithm is a technique for solving a <a href="/facts/Congruence_relation/TV3njpqF">congruence</a> of the form

x
          
            2
          
        
        ≡
        n
        
          
          (
          mod
          
          p
          )
        
        ,
      
    
    {\displaystyle x^{2}\equiv n{\pmod {p}},}

where 
 
 
 
 x
 ,
 n
 ∈
 
 
 F
 
 
 p
 
 
 
 
 {\displaystyle x,n\in \mathbf {F} _{p}}
 
, so n is the square of x, and where 
 
 
 
 p
 
 
 {\displaystyle p}
 
 is an <a href="/facts/Parity_(mathematics)/7zq2UM4V">odd</a> <a href="/facts/Prime_number/L20FLkgn">prime</a>. Here 
 
 
 
 
 
 F
 
 
 p
 
 
 
 
 {\displaystyle \mathbf {F} _{p}}
 
 denotes the finite <a href="/facts/Field_(mathematics)/xAjAS4ko">field</a> with 
 
 
 
 p
 
 
 {\displaystyle p}
 
 <a href="/facts/Element_(mathematics)/Q2mx1vHL">elements</a>; 
 
 
 
 {
 0
 ,
 1
 ,
 …
 ,
 p
 −
 1
 }
 
 
 {\displaystyle \{0,1,\dots ,p-1\}}
 
. The <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> is named after <a href="/facts/Michele_Cipolla/AcGWwmeL">Michele Cipolla</a>, an <a href="/facts/Italy/tUf0PDYF">Italian</a> <a href="/facts/Mathematician/eaFSR8Fx">mathematician</a> who discovered it in 1907.
Apart from prime moduli, Cipolla's algorithm is also able to take square roots modulo prime powers.

Cipolla's algorithm open-in-new

Cipolla's algorithm