Publication
IEEE Trans. Inf. Theory
Paper

Fast Evaluation of Logarithms in Fields of Characteristic Two

View publication

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.

Date

01 Jan 1984

Publication

IEEE Trans. Inf. Theory

Authors

Topics

Share