Searching for Best Karatsuba Recurrences

Efficient circuits for multiplication of binary polynomials use what are known as Karatsuba recurrences. These methods divide the polynomials of size (i.e. number of terms) k⋅n into k pieces of size n. Multiplication is performed by treating the factors as degree- (k−1) polynomials, with... See full abstract

Efficient circuits for multiplication of binary polynomials use what are known as Karatsuba recurrences. These methods divide the polynomials of size (i.e. number of terms) k⋅n 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) ≤ αM(n) + βn + γ, where M(t) is the number of binary operations necessary and sufficient for multiplying two binary polynomials with t terms each. Efficiently determining the smallest achievable values of (in order) α,β,γ is an unsolved 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.
Hide full abstract