International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Redundant Trinomials for Finite Fields of Characteristic $2$

Authors:
Christophe Doche
Download:
URL: http://eprint.iacr.org/2004/055
Search ePrint
Search Google
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$\%.
BibTeX
@misc{eprint-2004-12030,
  title={Redundant Trinomials for Finite Fields of Characteristic $2$},
  booktitle={IACR Eprint archive},
  keywords={implementation / finite field arithmetic; elliptic curve cryptography},
  url={http://eprint.iacr.org/2004/055},
  note={ doche@ics.mq.edu.au 12482 received 22 Feb 2004, last revised 5 Mar 2004},
  author={Christophe Doche},
  year=2004
}