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

Alexander Maximov; Helena Sjoberg

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 \leq 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: implementation multiplication modular reduction finite field primitive polynomial
Contact author(s): alexander maximov @ ericsson com
History: 2017-09-17: received
Short URL: https://ia.cr/2017/889
License: 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},
      url = {https://eprint.iacr.org/2017/889}
}