Redundant trinomials for finite fields of characteristic 2

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 sign₂, we describe redundant trinomial bases and discuss how to implement them efficiently. They are well suited to build double-struck F sign_2n 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%.