Cagdas Calik, Morris J. Dworkin, Nathan Dykas, Rene C. Peralta
Efficient circuits for multiplication of binary polynomials use what are known as Karatsuba recurrences. These methods divide the polynomials of size kn into k pieces of size n. Multiplication is performed by treating the factors as degree-(k-1) polynomials, with multiplication of the pieces of size n done recursively. This yields recurrences of the form M(kn) <= a M(n) + bn + c; where M(x) is the number of binary operations necessary and sufficient for multiplying two binary polynomials with x terms each. Efficiently determining the smallest achievable values of (in order) a,b,c is an funsolved problem. We describe a search method that yields improvements to the best known Karatsuba recurrences for k = 6,7 and 8. This yields improvements on the size of circuits for multiplication of binary polynomials in a range of practical interest.
Analysis of Experimental Algorithms
June 24-29, 2019
Special Event on Analysis of Experimental Algorithms (SEA2 2019)