2
$\begingroup$

First I apologize if this question is better tailored for SO, but since I'm using the method for crypto stuff, I thought I'd ask anybody that might know here. Karatsuba algorithm does a pretty good job, but maybe there is something that works better.

$\endgroup$
3
  • $\begingroup$ Online references for multiple-precision arithmetic are section 14 in the HAC, and Modern Computer Arithmetic. The later covers Karatsuba and asymptotically better techniques. What's best will depend a lot on the size of the modulus, and on if the C++ idiom at hand allows access to the full width of the hardware's multiplier. [edited] $\endgroup$ Feb 23, 2013 at 17:08
  • $\begingroup$ How large are you numbers? For typical crypto sizes schoolbook multiplications are still pretty popular. These alternative algorithms only pull ahead for larger numbers. $\endgroup$ Feb 23, 2013 at 20:23
  • $\begingroup$ Fürer's algorithm is asymptotically the fastest multiplication algorithm known, but only for numbers with several million digits, so it's definitely not meant for cryptography (or anything else, really). If you're just doing RSA, Karatsuba will work fine. $\endgroup$
    – Thomas
    Feb 24, 2013 at 9:35

2 Answers 2

2
$\begingroup$

It depends on the length of the inputs and characteristics of the target platform:

  • If inputs are short (at most around a thousand bits), try a Comba multiplication.
  • If inputs are short and your platform has a lot of registers, try a hybrid Comba multiplication.
  • If you have a multiply-accumulate instruction, give a shot at Schoolbook multiplication.
  • If inputs are larger, divide-and-conquer approaches (Karatsuba, Toom-Cook) start to become faster.
$\endgroup$
1
$\begingroup$

One look in wikipedia http://en.wikipedia.org/wiki/Karatsuba_algorithm

Shows there are faster algotithms:
Toom–Cook algorithm http://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication or even faster the
Schönhage–Strassen algorithm http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm

It depends on the size of your numbers if the effort to implement one of them is worth it. They are also only faster for big numbers. So it depends on the size of your numbers, if one of them can speed up your multiplication.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.