Fast evaluation of logarithms in fields of characteristic two
Don Coppersmith · IEEE Transactions on Information Theory · 1984
A method for determining logarithms in GF(2^{n})is presented. Its asymptotic running time isO(\exp (cn^{1/3} \log^{2/3} n))for a small constantc, while, by comparison, Adleman's scheme runs in timeO(\exp (c^{'}n^{1/2} \log^{1/2} n )). The ideas give a dramatic improvement even for moderate-sized fields such as GF(2^{127}), and make (barely) possible computations in fields of size around2^{400}. The method is not applicable to GF(q)for a large primeq.