Index calculus algorithm

<p>In <a href="/facts/Computational_number_theory/7Lu5N57C">computational number theory</a>, the index calculus algorithm is a <a href="/facts/Probabilistic/fgYvMhwb">probabilistic</a> <a href="/facts/Algorithm/fnl5NmRt">algorithm</a>  for computing <a href="/facts/Discrete_logarithm/k8TXh5bL">discrete logarithms</a>.
Dedicated to the discrete logarithm in 
  
    
      
        (
        
          Z
        
        
          /
        
        q
        
          Z
        
        
          )
          
            ∗
          
        
      
    
    {\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{*}}
  
 where 
  
    
      
        q
      
    
    {\displaystyle q}
  
 is a prime, index calculus leads to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes.
</p>

Index calculus algorithm open-in-new

Index calculus algorithm