A survey of some recent bit-parallel GF(2n) multipliers

This paper surveys bit-parallel multipliers for finite field GF(2n) according to i) quadratic and subquadratic arithmetic complexities of the underlying algorithms, ii) various bases used for representing the field elements, and iii) design approaches that rely on polynomial and matrix operations. Techniques for constructing space- and time-efficient multipliers are reviewed, and complexities of recent quadratic and subquadratic multipliers are summarized. For quadratic multipliers, the emphasis is placed on polynomial bases and their generalization. Low-degree Karatsuba-Toom formulae and their multiplication complexities are considered primarily for the subquadratic multipliers.