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?
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.
|
|
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. Karatsuba multiplication can be used together with Montgomery reduction (at least) as well as with classical modular reduction, by using big segments of arguments upon which Karatsuba multiplication is used. I suggest Modern Computer Arithmetic for more details. |
||||
|
|
