Paper 2017/889

On Fast Multiplication in Binary Finite Fields and Optimal Primitive Polynomials over GF(2)

Alexander Maximov and Helena Sjoberg

Abstract

In this paper we present a number of algorithms and optimization techniques to speedup computations in binary extension fields over GF(2). Particularly, we consider multiplication and modular reduction solutions. Additionally, we provide the table of optimal binary primitive polynomials over GF(2) of degree $2\le d<2048$, and the class of functions for optimal modular reduction algorithms for each of the listed polynomials. We give implementation examples targeting Intel CPU architectures, but generic results can be applied on other platforms as well.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
implementationmultiplicationmodular reductionfinite fieldprimitive polynomial
Contact author(s)
alexander maximov @ ericsson com
History
2017-09-17: received
Short URL
https://ia.cr/2017/889
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/889,
      author = {Alexander Maximov and Helena Sjoberg},
      title = {On Fast Multiplication in Binary Finite Fields and Optimal Primitive Polynomials over GF(2)},
      howpublished = {Cryptology ePrint Archive, Paper 2017/889},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/889}},
      url = {https://eprint.iacr.org/2017/889}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.