Cryptology ePrint Archive: Report 2007/393

Overlap-free Karatsuba-Ofman Polynomial Multiplication Algorithms

Haining Fan and Jiaguang Sun and Ming Gu and Kwok-Yan Lam

Abstract: 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.

Category / Keywords: Karatsuba algorithm, polynomial multiplication, subquadratic space complexity multiplier, finite fields, Galois fields.

Publication Info: IET Information security, vol. 4, no. 1, pp. 8-14, 2010.

Date: received 6 Oct 2007, last revised 27 Jun 2010

Contact author: fhn at tsinghua edu cn

Available formats: PDF | BibTeX Citation

Note: I received an email from Dr. Ekatherina Karatsuba, A. Karatsuba' daughter, and she told me that the Karatsuba algorithm was found by her father himself. So I added the following information on the 1st page.

I am sorry that I have made the following mistake: The first subquadratic integer multiplication algorithm was invented by A.A. Karatsuba himself, not Karatsuba and Ofman. [1]

Version: 20100628:012059 (All versions of this report)

Discussion forum: Show discussion | Start new discussion