Skip to main content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Searching for best Karatsuba recurrences

Published

Author(s)

Cagdas Calik, Morris J. Dworkin, Nathan Dykas, Rene C. 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, -1
Conference Title
Special Event on Analysis of Experimental Algorithms (SEA2 2019)

Keywords

polynomial multiplication, Karatsuba recurrences, circuit complexity
Created September 1, 2019, Updated March 13, 2020