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
