Better Circuits for Binary Polynomial Multiplication
Rene C. Peralta, Magnus G. Find
We develop a new and simple way to describe Karatsuba-like algorithms for multiplication of polynomials over GF2. These techniques, along with interpolation-based recurrences, yield circuits that are better (smaller and with lower depth) than anything previously known. We use our optimization tools to actually build the circuits for n-term binary polynomial multiplication for values of n of practical interest.