Missing a trick: Karatsuba variations

Mike Scott

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: 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},
      url = {https://eprint.iacr.org/2015/1247}
}