Fast Evaluation of Logarithms in Fields of Characteristic Two

A method for determining logarithms in GF (2ⁿ) is presented. Its asymptotic running time is O(exp(cn^1/3 log^2/3 n)) for a small constant c, while, by comparison, Adleman's scheme runs in time O(exp(c′n^1/2 1og^1/2 n)). The ideas give a dramatic improvement even for moderate-sized fields such as GF (2¹²⁷), and make (barely) possible computations in fields of size around 2⁴⁰⁰. The method is not applicable to GF (q) for a large prime q. © 1984 IEEE.