Abstract

A simple algorithm to find logarithms in a finite field of characteristic two is described. It uses the Euclidean algorithm for polynomials in attempting to reduce an element to a product of factors all of whose logarithms are stored in a database. The algorithm, which is similar to one of Adleman, has a random runtime and constant storage requirements. It is analyzed and problems associated with the construction of the database are considered. The aim of the work is to show that the algorithm is feasible for the field with $2^{127} $ elements on which several proposed public key distribution systems have been based. For such application it is felt that the discrete logarithm is still a viable technique for sufficiently large fields.

Keywords

Discrete logarithmLogarithmFinite fieldMathematicsEuclidean geometryField (mathematics)Product (mathematics)Simple (philosophy)Euclidean spaceKey (lock)AlgorithmDiscrete mathematicsComputer sciencePure mathematicsPublic-key cryptographyMathematical analysis

Related Publications

Publication Info

Year
1984
Type
article
Volume
5
Issue
2
Pages
276-285
Citations
70
Access
Closed

External Links

View on DOI.org

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

70
OpenAlex

Cite This

Ian F. Blake, Ryoh Fuji‐Hara, R. C. Mullin et al. (1984). Computing Logarithms in Finite Fields of Characteristic Two. SIAM Journal on Algebraic and Discrete Methods , 5 (2) , 276-285. https://doi.org/10.1137/0605029

Identifiers

DOI
10.1137/0605029