You are looking at a specific version 20201030:085742 of this paper.
See the latest version.
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)
- 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