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)
, Dworkin, M.
, Dykas, N.
and Peralta, R.
Searching for best Karatsuba recurrences, Analysis of Experimental Algorithms, Kalamata, GR, [online], https://doi.org/10.1007/978-3-030-34029-2_22, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=928663
(Accessed January 24, 2022)