Cryptology ePrint Archive: Report 2007/393

Overlap-free Karatsuba-Ofman Polynomial Multiplication Algorithm

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

Abstract: We describe how a recently proposed way to split input operands allows for fast VLSI implementations of GF(2)[x] Karatsuba-Ofman multipliers. The XOR gate delay of the proposed multiplier is better than that of previous Karatsuba-Ofman multipliers. For example, it is reduced by about 33% and 25% for n = 2^i and n = 3^i (i > 1), respectively.

Category / Keywords: Karatsuba, polynomial multiplication,subquadratic multiplier

Publication Info: unpublished paper.

Date: received 6 Oct 2007, last revised 16 Oct 2007

Contact author: fan_haining at yahoo com

Available formats: PDF | BibTeX Citation

Version: 20071016:151919 (All versions of this report)

Discussion forum: Show discussion | Start new discussion