# Which one is fastest? Karatsuba or Montgomery multiplication?

Is there any complexity analysis between Karatsuba and Montgomery multiplication algorithms? It seems that Karatsuba is more general in the sense that is not modulo tuned while Montgomery it is. Does a also a hybrid model using Karasuba and Montogomery exists?

-
The actual speed of an implementation of an algorithm depends on which language you are coding in, which compiler you are using and what the target CPU is. For instance, if we are discussing the integer sizes commonly used in cryptography and reasonably optimized assembler implementations, Karatsuba multiplication followed by Montgomery reduction is typically faster on x86 than Montgomery multiplication, while on x64 it is the other way around. Hence, this is not a crypto.stackexchange question, but rather one for stackoverflow. –  Henrick Hellström Feb 25 '13 at 0:27
@HenrickHellström On the other hand, I don't think curious would get a better answer at stackoverflow than he just did in your comment, so... –  Maarten Bodewes Feb 25 '13 at 2:18
To state explicit what's already implicit contained in Henrick's excellent comment: Montgomery multiplication is a trick for modular multiplication using multiplication without division and Karatsuba multiplication is a trick for multiplying in less than quadratic time (with respect to bitlength). So of course one can (and does) use Karatsuba within Montgomery multiplication. As Karatsuba multiplication comes with a small overhead, it depends on the lengths of the factors (and on the criteria Henrick mentionend) if it's worth using it. –  j.p. Feb 25 '13 at 9:17
@HenrickHellström Thanks for your comment. But why on x64 is the other way around? You just have bigger registers on x64.At each clock pulse you can transfer 64bits. That means that you can save at once 64bits and your word size is 64 bits. So i guess it will further improve the running time of the scheme Karatsuba-then-Montgomery. Or i am missing sth? –  curious Feb 25 '13 at 9:51
The Big-O complexity values for the algorithms are based on the number of single precision MUL operations (and DIV, but not for those) only. On modern CPUs the performance of MUL is not as relatively bad as it was 10-20 years ago. Instead, on x64 Karatsuba suffers from its higher memory usage and more CALL operations. Montgomery Multiplication OTOH might be implemented to take advantage of r8-r15. –  Henrick Hellström Feb 25 '13 at 11:07

Montgomery arithmetic is used only for modular multiplication. At the cost of some pre- and post-computation (of mostly negligible cost in the case of modular exponentiation in the context of cryptography with exponents big enough to be private), it simplifies the modular reduction step, by avoiding possible mis-estimation of the quotient, and allowing to make that estimation earlier, thus easing implementation of multiplication and modular reduction in the same scan of the temporary result. However, Montgomery arithmetic leaves the asymptotic cost unchanged, both in $O()$ and $o()$ notation, accounting for either or both of elementary multiplications and number of memory accesses, compared to a good implementation of the classical multiplication and modular reduction using the same digit width.
Karatsuba multiplication reduces the asymptotic cost of modular multiplication of $n$-digit numbers from $O(n^2)$ to $O(n^{\log_2 3})$ [that's O($n^{1.58\dots})$], and from $O(n^3)$ to $O(n^{1+\log_2 3})$ [that's O($n^{2.58\dots})$] for modular exponentiation with $n$-digit numbers including exponent. That allows a speedup past some threshold for $n$, which vary considerably depending on an awful lot of things.