Wikipedia / Function field sieve
Wikipedia / Function field sieve
In mathematics, the Function Field Sieve is one of the most efficient algorithms to solve the Discrete Logarithm Problem (DLP) in a finite field. It has heuristic subexponential complexity. Leonard Adleman 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.
is a one-way function used in cryptography. Several cryptographic methods are based on the DLP such as the Diffie-Hellman key exchange, the El Gamal cryptosystem and the Digital Signature Algorithm.
Number theoretical background
Function Fields
be a polynomial defining an algebraic curve. A function field may be viewed as the field of fractions and has transcendence degree.
There exist bijections between valuation rings in function fields and equivalence classes of places, as well as between valuation rings and equivalence classes of valuations. This correspondence is frequently used in the Function Field Sieve algorithm.
Divisors
.
.
Method
.
-smooth. This is analogous to the definition of a smooth number.
as a combination of the logarithm we found before and thus solve the DLP.
Precomputation
Parameter selection
.
.
.
Sieving
are found.
-smooth. To implement this, Gray code can be used to efficiently step through multiples of a given polynomial.
This is completely analogous to the sieving step in other sieving algorithms such as the Number Field Sieve or the index calculus algorithm but those functions can be factored into irreducible polynomials just as numbers can be factored into primes.
Finding linear relations
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.
.
we get the following expression:
. Then, using the fact that the divisor of a surrogate function is unique up to a constant, one gets
in this decomposition. Then
.
.
.
Reduction step
can be reduced to polynomials of smaller degree using a generalization of the Coppersmith method., we can eventually compute
, which solves the DLP.
Complexity
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 behave like random numbers in a given range.
Comparison with other methods
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. In their easiest forms both solve the DLP in a finite field as well.
. It is not surprising that there exist two similar algorithms, one with number fields and the other one with function fields. In fact there is an extensive analogy between these two kinds of global fields.
The index calculus algorithm, so most of the computations can be done with smaller numbers.