Paper 2004/055

Redundant Trinomials for Finite Fields of Characteristic $2$

Christophe Doche

Abstract

In this paper we introduce a new way to represent elements of a finite field of characteristic $2$. We describe a new type of polynomial basis, called {\it redundant trinomial basis} and discuss how to implement it efficiently. Redundant trinomial bases are well suited to build $\mathbb{F}_{2^n}$ when no irreducible trinomial of degree $n$ exists. Tests with {\tt NTL} show that improvements for squaring and exponentiation are respectively up to $45$\% and $25$\%. More attention is given to relevant extension degrees for doing elliptic and hyperelliptic curve cryptography. For this range, a scalar multiplication can be speeded up by a factor up to $15$\%.

Metadata
Available format(s)
PDF PS
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
finite field arithmeticelliptic curve cryptography
Contact author(s)
doche @ ics mq edu au
History
2004-03-05: revised
2004-02-23: received
See all versions
Short URL
https://ia.cr/2004/055
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/055,
      author = {Christophe Doche},
      title = {Redundant Trinomials for Finite Fields of Characteristic $2$},
      howpublished = {Cryptology ePrint Archive, Paper 2004/055},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/055}},
      url = {https://eprint.iacr.org/2004/055}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.