Berlekamp–Rabin algorithm

<p>In <a href="/facts/Number_theory/zhoa7zrc">number theory</a>, Berlekamp's root finding algorithm, also called the Berlekamp–Rabin algorithm, is the <a href="/facts/Randomized_algorithm/Fngl1zgk">probabilistic</a> method of <a href="/facts/Root-finding_algorithm/IxTDkhBq">finding roots</a> of <a href="/facts/Polynomial/Lzak8VVx">polynomials</a> over the <a href="/facts/Finite_field/UkMGJo3m">field</a> 
  
    
      
        
          
            F
          
          
            p
          
        
      
    
    {\displaystyle \mathbb {F} _{p}}
  
 with 
  
    
      
        p
      
    
    {\displaystyle p}
  
 elements. The method was discovered by <a href="/facts/Elwyn_Berlekamp/zUTTIlF6">Elwyn Berlekamp</a> in 1970 as an auxiliary to the <a href="/facts/Berlekamp%27s_algorithm/qBfq6P78">algorithm</a> for polynomial factorization over finite fields. The algorithm was later modified by <a href="/facts/Michael_O._Rabin/M6NHIb5J">Rabin</a> for arbitrary finite fields in 1979. The method was also independently discovered before Berlekamp by other researchers.
</p>

Berlekamp–Rabin algorithm open-in-new

Berlekamp–Rabin algorithm