In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
the Function Field Sieve is one of the most efficient algorithms to solve the
Discrete Logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
Problem (DLP) in a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
. It has
heuristic
A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
subexponential complexity.
Leonard Adleman
Leonard Adleman (born December 31, 1945) is an American computer scientist. He is one of the creators of the RSA encryption algorithm, for which he received the 2002 Turing Award, often called the Nobel prize of Computer science. He is also kno ...
developed it in 1994 and then elaborated it together with M. D. Huang in 1999.
[L. Adleman, M.D. Huang. "Function Field Sieve Method for Discrete Logarithms over Finite Fields". In: Inf. Comput. 151 (May 1999), pp. 5-16. DOI: 10.1006/inco.1998.2761.]
Previous work includes the work of D. Coppersmith about the DLP in fields of characteristic two.
The discrete logarithm problem in a finite field consists of solving the equation
for
,
a prime number and
an integer. The function
for a fixed
is a
one-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, spe ...
used in
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
. Several cryptographic methods are based on the DLP such as the
Diffie-Hellman key exchange, the
El Gamal
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in the ...
cryptosystem and the
Digital Signature Algorithm
The Digital Signature Algorithm (DSA) is a Public-key cryptography, public-key cryptosystem and Federal Information Processing Standards, Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular e ...
.
Number theoretical background
Function Fields
Let
be a polynomial defining an
algebraic curve
In mathematics, an affine algebraic plane curve is the zero set of a polynomial in two variables. A projective algebraic plane curve is the zero set in a projective plane of a homogeneous polynomial in three variables. An affine algebraic plane c ...
over a finite field
. A function field may be viewed as the
field of fractions
In abstract algebra, the field of fractions of an integral domain is the smallest field in which it can be embedded. The construction of the field of fractions is modeled on the relationship between the integral domain of integers and the field ...
of the affine coordinate ring
, where
denotes the ideal generated by
. This is a special case of an algebraic function field. It is defined over the finite field
and has
transcendence degree
In abstract algebra, the transcendence degree of a field extension ''L'' / ''K'' is a certain rather coarse measure of the "size" of the extension. Specifically, it is defined as the largest cardinality of an algebraically independent subset of ...
one. The transcendent element will be denoted by
.
There exist bijections between
valuation ring In abstract algebra, a valuation ring is an integral domain ''D'' such that for every element ''x'' of its field of fractions ''F'', at least one of ''x'' or ''x''−1 belongs to ''D''.
Given a field ''F'', if ''D'' is a subring of ''F'' such t ...
s in function fields and equivalence classes of
places
Place may refer to:
Geography
* Place (United States Census Bureau), defined as any concentration of population
** Census-designated place, a populated area lacking its own municipal government
* "Place", a type of street or road name
** Ofte ...
, as well as between valuation rings and equivalence classes of
valuations. This correspondence is frequently used in the Function Field Sieve algorithm.
Divisors
A discrete valuation of the function field
, namely a discrete valuation ring
, has a unique maximal ideal
called a prime of the function field. The degree of
is