Paper 2015/1247

Missing a trick: Karatsuba variations

Mike Scott

Abstract

There are a variety of ways of applying the Karatsuba idea to multi-digit multiplication. These apply particularly well in the context where digits do not use the full word-length of the computer, so that partial products can be safely accumulated without fear of overflow. Here we re-visit the ``arbitrary degree'' version of Karatsuba and show that the cost of this little-known variant has been over-estimated in the past. We also attempt to definitively answer the question as to the cross-over point where Karatsuba performs better than the classic method.

Note: Minor improvement to adkmul5 code

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. ArticCrypt 2016
Contact author(s)
mike scott @ miracl com
History
2020-10-30: last of 10 revisions
2016-01-01: received
See all versions
Short URL
https://ia.cr/2015/1247
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1247,
      author = {Mike Scott},
      title = {Missing a trick: Karatsuba variations},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1247},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1247}},
      url = {https://eprint.iacr.org/2015/1247}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.