Paper 2007/192

Optimal Irreducible Polynomials for GF(2^m) Arithmetic

Michael Scott

Abstract

The irreducible polynomials recommended for use by multiple standards documents are in fact far from optimal on many platforms. Specifically they are suboptimal in terms of performance, for the computation of field square roots and in the application of the ``almost inverse'' field inversion algorithm. In this paper we question the need for the standardisation of irreducible polynomials in the first place, and derive the ``best'' polynomials to use depending on the underlying processor architecture. Surprisingly it turns out that a trinomial polynomial is in many cases not necessarily the best choice. Finally we make some specific recommendations for some particular types of architecture.

Note: More typos fixed, and an appendix added on the calculation of square roots.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Irreducible polynomialsimplementation
Contact author(s)
mike @ computing dcu ie
History
2007-05-30: last of 5 revisions
2007-05-23: received
See all versions
Short URL
https://ia.cr/2007/192
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/192,
      author = {Michael Scott},
      title = {Optimal Irreducible Polynomials for GF(2^m) Arithmetic},
      howpublished = {Cryptology ePrint Archive, Paper 2007/192},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/192}},
      url = {https://eprint.iacr.org/2007/192}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.