Searching for best Karatsuba recurrences

Published

September 1, 2019

Author(s)

Cagdas Calik, Morris Dworkin, Nathan Dykas, Rene Peralta

Abstract

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.

Proceedings Title

Analysis of Experimental Algorithms

Volume

11544

Conference Dates

June 24-29, 2019

Conference Location

Kalamata, GR

Conference Title

Special Event on Analysis of Experimental Algorithms (SEA2 2019)

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-030-34029-2_22

Local Download

Keywords

polynomial multiplication, Karatsuba recurrences, circuit complexity

Citation

Calik, C. , Dworkin, M. , Dykas, N. and Peralta, R. (2019), 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 April 19, 2024)