Cryptology ePrint Archive: Report 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.
Category / Keywords: implementation /
Original Publication (with minor differences): ArticCrypt 2016
Date: received 1 Jan 2016, last revised 3 Aug 2016
Contact author: mike scott at miracl com
Available format(s): PDF | BibTeX Citation
Note: Corrected and expanded results. New REDC function.
Version: 20160803:185603 (All versions of this report)
Short URL: ia.cr/2015/1247
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]