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 ^[1] and then elaborated it together with M. D. Huang in 1999.^[2] Previous work includes the work of D. Coppersmith ^[3] about the DLP in fields of characteristic two.

The discrete logarithm problem in a finite field consists of solving the equation ${\displaystyle a^{x}=b}$ for ${\displaystyle a,b\in \mathbb {F} _{p^{n}}}$, ${\displaystyle p}$ a prime number and ${\displaystyle n}$ an integer. The function ${\displaystyle f:\mathbb {F} _{p^{n}}\to \mathbb {F} _{p^{n}},a\mapsto a^{x}}$ for a fixed ${\displaystyle x\in \mathbb {N} }$ 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.