Paper 2015/1247 Original: eprint.iacr.org/2015/1247 ↗
Missing a trick: Karatsuba variations
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.
Metadata
- Available format(s)
PDF- Category
- Implementation
- Publication info
- Preprint.
- History
- 2020-10-30: last updated
- 2016-01-01: published
- Short URL
- https://ia.cr/2015/1247
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}