Function field sieve

<p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a> the Function Field Sieve is one of the most efficient algorithms to solve the <a href="/facts/Discrete_Logarithm/k8TXh5bL">Discrete Logarithm</a> Problem (DLP) in a <a href="/facts/Finite_field/UkMGJo3m">finite field</a>. It has <a href="/facts/Heuristic/BcBEkv9c">heuristic</a> <a href="/facts/Subexponential_time/77T62gmf">subexponential</a> complexity. <a href="/facts/Leonard_Adleman/uSGnztdj">Leonard Adleman</a> developed it in 1994  and then elaborated it together with M. D. Huang in 1999.
Previous work includes the work of D. Coppersmith  about the DLP in fields of characteristic two.
</p><p>The discrete logarithm problem in a finite field consists of solving  the equation 
  
    
      
        
          a
          
            x
          
        
        =
        b
      
    
    {\displaystyle a^{x}=b}
  
  for 
  
    
      
        a
        ,
        b
        ∈
        
          
            F
          
          
            
              p
              
                n
              
            
          
        
      
    
    {\displaystyle a,b\in \mathbb {F} _{p^{n}}}
  
,  
  
    
      
        p
      
    
    {\displaystyle p}
  
 a prime number and 
  
    
      
        n
      
    
    {\displaystyle n}
  
 an integer. The function 
  
    
      
        f
        :
        
          
            F
          
          
            
              p
              
                n
              
            
          
        
        →
        
          
            F
          
          
            
              p
              
                n
              
            
          
        
        ,
        a
        ↦
        
          a
          
            x
          
        
      
    
    {\displaystyle f:\mathbb {F} _{p^{n}}\to \mathbb {F} _{p^{n}},a\mapsto a^{x}}
  
 for a fixed 
  
    
      
        x
        ∈
        
          N
        
      
    
    {\displaystyle x\in \mathbb {N} }
  
 is a <a href="/facts/One-way_function/rGtcumDW">one-way function</a> used in <a href="/facts/Cryptography/e94PEVau">cryptography</a>. Several cryptographic methods are based on the DLP such as the <a href="/facts/Diffie-Hellman_key_exchange/xR4YQcaD">Diffie-Hellman key exchange</a>, the <a href="/facts/El_Gamal/sKDVyMyR">El Gamal</a> cryptosystem and the <a href="/facts/Digital_Signature_Algorithm/0o0FK486">Digital Signature Algorithm</a>.
</p>

Function field sieve open-in-new

Function field sieve