Paper 2006/224

Generalizations of the Karatsuba Algorithm for Efficient Implementations

André Weimerskirch and Christof Paar

Abstract

In this work we generalize the classical Karatsuba Algorithm (KA) for polynomial multiplication to (i) polynomials of arbitrary degree and (ii) recursive use. We determine exact complexity expressions for the KA and focus on how to use it with the least number of operations. We develop a rule for the optimum order of steps if the KA is used recursively. We show how the usage of dummy coefficients may improve performance. Finally we provide detailed information on how to use the KA with least cost, and also provide tables that describe the best possible usage of the KA for polynomials up to a degree of 127. Our results are especially useful for efficient implementations of cryptographic and coding schemes over fixed-size fields like $GF(p^m)$.

Metadata
Available format(s)
PDF PS
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Karatsubapolynomial multiplication
Contact author(s)
aweimerskirch @ escrypt com
History
2006-07-03: received
Short URL
https://ia.cr/2006/224
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/224,
      author = {André Weimerskirch and Christof Paar},
      title = {Generalizations of the Karatsuba Algorithm for Efficient Implementations},
      howpublished = {Cryptology ePrint Archive, Paper 2006/224},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/224}},
      url = {https://eprint.iacr.org/2006/224}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.