Cryptology ePrint Archive: Report 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$\%.

Category / Keywords: implementation / finite field arithmetic; elliptic curve cryptography

Date: received 22 Feb 2004, last revised 5 Mar 2004

Contact author: doche at ics mq edu au

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20040305:131432 (All versions of this report)

Short URL: ia.cr/2004/055

Discussion forum: Show discussion | Start new discussion