Dr. Christophe Doche
Macquarie University
Title: Redundant trinomials for finite fields of characteristic 2
In this talk we introduce so-called redundant trinomials to represent elements of finite fields of
characteristic 2.
After recalling well-known techniques to perform efficient arithmetic in extensions of
GF(2), we describe redundant trinomial bases
and discuss how to implement them efficiently.
They are well suited to build GF(2^d) when no irreducible trinomial exists and one has to choose
an irreducible pentanomial.
Tests with NTL show that
improvements for squaring and exponentiation are respectively
up to 45% and 25% when compared to a representation based on pentanomials.
More attention is given to extension degrees relevant for
elliptic and hyperelliptic curve cryptography.
For this range, a scalar multiplication can be speeded up by a factor up to 15%.