Better Circuits for Binary Polynomial Multiplication
Magnus Find, René Peralta · IEEE Transactions on Computers · 2018
We develop a new and simple way to describe Karatsuba-like algorithms for multiplication of polynomials over$\mathbb {F}_2$. We restrict the search of small circuits to a class of circuits we callsymmetric bilinear. These are circuits in which AND gates only compute functions of the form$\sum _{i \in S} a_i \cdot \sum _{i \in S} b_i \quad \quad (S \subseteq \lbrace 0, \ldots, n-1\rbrace).$∑i∈Sai·∑i∈Sbi(S⊆{0,...,n-1}).These techniques yield improved recurrences for$M(kn)$M(kn), the number of gates used in a circuit that multiplies two$kn$kn-term polynomials, for$k = 4,5,6,$k=4,5,6,and 7. We built and verified the circuits for$n$n-term binary polynomial multiplication for values of$n$nof practical interest. Circuits for$n$nup to 100 are posted athttp://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/BinPolMult.tar.gz.