Fast evaluation of logarithms in fields of characteristic two

Abstract

A method for determining logarithms in GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(2^{n})</tex> is presented. Its asymptotic running time is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(\exp (cn^{1/3} \log^{2/3} n))</tex> for a small constant <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</tex> , while, by comparison, Adleman's scheme runs in time <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(\exp (c^{'}n^{1/2} \log^{1/2} n ))</tex> . The ideas give a dramatic improvement even for moderate-sized fields such as GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(2^{127})</tex> , and make (barely) possible computations in fields of size around <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2^{400}</tex> . The method is not applicable to GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(q)</tex> for a large prime <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</tex> .

Keywords

Affiliated Institutions

• IBM (United States) US

Related Publications