Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

share|improve this question
@fgrieu Fantastic, thank you. – montreux Feb 23 at 16:54
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] – fgrieu Feb 23 at 17:08
How large are you numbers? For typical crypto sizes schoolbook multiplications are still pretty popular. These alternative algorithms only pull ahead for larger numbers. – CodesInChaos Feb 23 at 20:23
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. – Thomas Feb 24 at 9:35

2 Answers

up vote 0 down vote

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.

share|improve this answer
up vote 1 down vote

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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