Publication
IEEE Trans. Inf. Theory
Paper
Fast Evaluation of Logarithms in Fields of Characteristic Two
Abstract
A method for determining logarithms in GF (2<sup>n</sup>) is presented. Its asymptotic running time is O(exp(cn<sup>1/3</sup> log<sup>2/3</sup> n)) for a small constant c, while, by comparison, Adleman's scheme runs in time O(exp(c′n<sup>1/2</sup> 1og<sup>1/2</sup> n)). The ideas give a dramatic improvement even for moderate-sized fields such as GF (2<sup>127</sup>), and make (barely) possible computations in fields of size around 2<sup>400</sup>. The method is not applicable to GF (q) for a large prime q. © 1984 IEEE.