What question did this study set out to answer?

This study aims to present a method for evaluating logarithms in finite fields of characteristic two and to analyze its efficiency.

synapse

⌘+K

synapse

⌘+K

July 1, 1984

Fast evaluation of logarithms in fields of characteristic two

Key Points

This study aims to present a method for evaluating logarithms in finite fields of characteristic two and to analyze its efficiency.
Introduced a new evaluation method for logarithms in GF(2^n).
Compared the running time with Adleman's scheme.
Provided theoretical analysis on the performance for moderate-sized fields.
Achieved asymptotic running time of O(exp(cn^{1/3} log^{2/3} n)).
Demonstrated significant improvement for fields like GF(2^{127}).
Allowed computation in larger fields, nearing GF(2^{400}).

Abstract

A method for determining logarithms in GF (2^n) is presented. Its asymptotic running time is O ( (cn^1/3 ^2/3 n) ) for a small constant c, while, by comparison, Adleman's scheme runs in time O ( (c^'n^1/2 ^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 around 2^400. The method is not applicable to GF (q) for a large prime q.

Mark Helpful

Bookmark

Relay