Better Circuits for Binary Polynomial Multiplication

We develop a new and simple way to describe Karatsuba-like algorithms for multiplication of polynomials over F2. We restrict the search of small circuits to a class of circuits we call symmetric bilinear. These are circuits in which AND gates only compute functions of the form ∑i∈S^a_i⋅∑i∈S^b_i (S⊆{0,…,n−1}). These techniques yield improved recurrences for M(kn), the number of gates used in a circuit that multiplies two knkn-term polynomials, for k=4,5,6, and 7. We built and verified the circuits for nn-term binary polynomial multiplication for values of nn of practical interest. Circuits for nn up to 100 are posted at http://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/BinPolMult.tar.gz.