Function field sieve

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In mathematics, the function field sieve was introduced in 1994 by Leonard Adleman as an efficient technique for extracting discrete logarithms over finite fields of small characteristic, and elaborated by Adleman and Huang in 1999.

Sieving for points at which a polynomial-valued function is divisible by a given polynomial is not much more difficult than sieving over the integers – the underlying structure is fairly similar, and Gray code provides a convenient way to step through multiples of a given polynomial very efficiently.


The Adleman–Huang paper is available at Science Direct, but views the problem using very algebraic-geometric language.