Redundant trinomials for finite fields of characteristic 2

Christophe Doche

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


In this article we introduce redundant trinomials to represent elements of finite fields of characteristic 2. This paper develops applications to cryptography, especially based on elliptic and hyperelliptic curves. After recalling well-known techniques to perform efficient arithmetic in extensions of double-struck F sign2, we describe redundant trinomial bases and discuss how to implement them efficiently. They are well suited to build double-struck F sign2n when no irreducible trinomial of degree n exists. Depending on n ∈ [2, 10000] tests with NTL show that, in this case, improvements for squaring and exponentiation are respectively up to 45% and 25%. More attention is given to extension degrees relevant for curve-based cryptography. For this range, a scalar multiplication can be sped up by a factor up to 15%.

Original languageEnglish
Pages (from-to)122-133
Number of pages12
JournalLecture Notes in Computer Science
Publication statusPublished - 2005


Dive into the research topics of 'Redundant trinomials for finite fields of characteristic 2'. Together they form a unique fingerprint.

Cite this