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
-
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}
}
