Cryptology ePrint Archive: Report 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.

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