Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Searching for best Karatsuba recurrences



Cagdas Calik, Morris Dworkin, Nathan Dykas, Rene 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.
Proceedings Title
Analysis of Experimental Algorithms
Conference Dates
June 24-29, 2019
Conference Location
Kalamata, GR
Conference Title
Special Event on Analysis of Experimental Algorithms (SEA2 2019)


polynomial multiplication, Karatsuba recurrences, circuit complexity


Calik, C. , Dworkin, M. , Dykas, N. and Peralta, R. (2019), Searching for best Karatsuba recurrences, Analysis of Experimental Algorithms, Kalamata, GR, [online],, (Accessed July 22, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created August 31, 2019, Updated October 12, 2021