[Resource Topic] 2007/393: Overlap-free Karatsuba-Ofman Polynomial Multiplication Algorithms

Welcome to the resource topic for 2007/393

Overlap-free Karatsuba-Ofman Polynomial Multiplication Algorithms

Authors: Haining Fan, Jiaguang Sun, Ming Gu, Kwok-Yan Lam


We 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=2^{t} and n=3^{t} (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(2^n) multipliers in 1990.

ePrint: https://eprint.iacr.org/2007/393

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .