Overlap-free Karatsuba-Ofman polynomial multiplication algorithms

摘要

The authors describe how a simple way to split input operands allows for fast VLSI implementations of subquadratic GF(2)[x] Karatsuba-Ofman multipliers. The theoretical XOR gate delay of the resulting multipliers is reduced significantly. For example, it is reduced by about 33 and 25% for n = 2t and n = 3t (t > 1), respectively. To the best of our knowledge, this parameter has never been improved since the original Karatsuba-Ofman algorithm was first used to design GF(2n) multipliers in 1990.