A new representation of elements of finite fields GF(2m) yielding small complexity arithmetic circuits

Let F₂ denote the binary field and F_2m, an algebraic extension of degree m>1 over F₂. Traditionally, elements of F_2m are either represented as powers of a primitive element of F_2m together with 0, or by an expansion in a basis of the vector space F_2m over F₂. We propose a new representation based on an isomorphism from F_2m into the residue polynomial ring module Xⁿ+1. The new representation simultaneously satisfies the properties of various traditional representations, which leads, in some cases, to architectures of parallel-in-parallel-out arithmetic circuits (adder, multiplier, exponentiator/inverter, squarer, divider) with average to small complexity. We show that the implementation of all the arithmetic circuits designed for the new representation on an integrated circuit sometimes has smaller complexity than the implementation of all the arithmetic circuits designed for other representations. In addition, we derive a serial multiplier for the field F_2m which comprises the least number of gates of all the serial multipliers known to the author, when m+1 is a prime such that 2 is primitive in the field Z_m+1