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.
-
$\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$– fgrieu - mod election time ♦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$– CodesInChaosFeb 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$– ThomasFeb 24, 2013 at 9:35
2 Answers
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.
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.