International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Overlap-free Karatsuba-Ofman Polynomial Multiplication Algorithm

Authors:
Haining Fan
Jiaguang Sun
Ming Gu
Kwok-Yan Lam
Download:
URL: http://eprint.iacr.org/2007/393
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2007-13673,
  title={Overlap-free Karatsuba-Ofman Polynomial Multiplication Algorithm},
  booktitle={IACR Eprint archive},
  keywords={Karatsuba, polynomial multiplication,subquadratic multiplier},
  url={http://eprint.iacr.org/2007/393},
  note={unpublished paper. fan_haining@yahoo.com 13802 received 6 Oct 2007, last revised 16 Oct 2007},
  author={Haining Fan and Jiaguang Sun and Ming Gu and Kwok-Yan Lam},
  year=2007
}