Better Circuits for Binary Polynomial Multiplication

Published: April 01, 2019


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.
Citation: IEEE Transactions on Computers
Volume: 68
Issue: 4
Pub Type: Journals


Binary polynomial multiplication, circuits, symmetric bilinear circuits
Created April 01, 2019, Updated May 01, 2019