Cryptology ePrint Archive: Report 2007/393

Overlap-free Karatsuba-Ofman Polynomial Multiplication Algorithms for Hardware Implementations

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, Karatsuba-Ofman algorithm, polynomial multiplication, subquadratic space complexity multiplier, finite fields, Galois fields.

Publication Info: unpublished

Date: received 6 Oct 2007, last revised 7 Oct 2008

Contact author: fhn at tsinghua edu cn

Available formats: PDF | BibTeX Citation

Note: This is a major version. I added 1 example and 1 figure, and corrected some typoes. Actually, its length increased by 50% (10- to 15 pages).

Version: 20081008:011942 (All versions of this report)

Discussion forum: Show discussion | Start new discussion