In mathematics the Function Field Sieve is one of the most efficient algorithms to solve the Discrete Logarithm Problem (DLP) in a finite field.
Leonard Adleman developed it in 1994 [1] and then elaborated it together with M. D. Huang in 1999.
The discrete logarithm problem in a finite field consists of solving the equation
Several cryptographic methods are based on the DLP such as the Diffie-Hellman key exchange, the El Gamal cryptosystem and the Digital Signature Algorithm.
be a polynomial defining an algebraic curve over a finite field
This is a special case of an algebraic function field.
[4] This correspondence is frequently used in the Function Field Sieve algorithm.
The Function Field Sieve algorithm consists of a precomputation where the discrete logarithms of irreducible polynomials of small degree are found and a reduction step where they are combined to the logarithm of
This is analogous to the definition of a smooth number and such functions are useful because their decomposition can be found relatively fast.
The sieving step of the algorithm consists of finding doubly-smooth pairs of functions.
In the subsequent step we use them to find linear relations including the logarithms of the functions in the decompositions.
By solving a linear system we then calculate the logarithms.
as a combination of the logarithm we found before and thus solve the DLP.
The algorithm requires the following parameters: an irreducible function
To implement this, Gray code can be used to efficiently step through multiples of a given polynomial.
This is the most difficult part of the algorithm, involving function fields, places and divisors as defined above.
The goal is to use the doubly-smooth pairs of functions to find linear relations involving the discrete logarithms of elements in the factor base.
For each irreducible function in the factor base we find places
Then Here we can take the discrete logarithm of the equation up to a unit.
Once enough equations of this form are found, a linear system can be solved to find
the unit corresponding to the restricted discrete logarithm can be calculated which then gives
can be reduced to polynomials of smaller degree using a generalization of the Coppersmith method.
, we can eventually compute The Function Field Sieve is thought to run in subexponential time in using the L-notation.
There is no rigorous proof of this complexity since it relies on some heuristic assumptions.
For example in the sieving step we assume that numbers of the form
There are two other well known algorithms that solve the discrete logarithm problem in sub-exponential time: the index calculus algorithm and a version of the Number Field Sieve.
[6] and is therefore slightly slower than the best performance of the Function Field Sieve.
In fact there is an extensive analogy between these two kinds of global fields.
The index calculus algorithm is much easier to state than the Function Field Sieve and the Number Field Sieve since it does not involve any advanced algebraic structures.
The main reason why the Number Field Sieve and the Function Field Sieve are faster is that these algorithms can run with a smaller smoothness bound