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?
$\begingroup$
$\endgroup$
5
-
2$\begingroup$ 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. $\endgroup$– Henrick HellströmCommented Feb 25, 2013 at 0:27
-
1$\begingroup$ @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... $\endgroup$– Maarten Bodewes ♦Commented Feb 25, 2013 at 2:18
-
2$\begingroup$ 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. $\endgroup$– j.p.Commented Feb 25, 2013 at 9:17
-
$\begingroup$ @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? $\endgroup$– curiousCommented Feb 25, 2013 at 9:51
-
$\begingroup$ 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. $\endgroup$– Henrick HellströmCommented Feb 25, 2013 at 11:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
Summary: Montgomery only aims at modest (if any) speedup compared to classic algorithms; it is popular for other reasons. Karatsuba allows large speedups for very large parameters, but the threshold where it becomes beneficial is often not reached in cryptographic applications. The techniques can be used together.
Montgomery arithmetic is used for modular multiplication and exponentiation, a common operation in cryptography (RSA, some Elliptic Curve Cryptography systems). At the cost of some pre- and post-computation (of mostly negligible cost when the exponent is big enough to be secret), it simplifies the modular reduction steps, specifically with two benefits:
- It avoids possible mis-estimation of the quotient, which in classical algorithms leads to a special case; this is beneficial from the standpoint of side channel leakage (e.g. timing attacks); and by the peace of mind it gives (the classical quotient estimation and its special case are hard to get right and test fully).
- The Montgomery equivalent of quotient estimation is performed based on the low-order bits of the value to be reduced (rather than high-order), and that eases implementation of multiplication and modular reduction interleaved in the same scan of a temporary result (that interleaving technique in turn limits the width of numbers manipulated to about the size of the modulus, and reduces the number of memory accesses, compared to naively computing a full product then reducing it).
However Montgomery arithmetic leaves the cost mostly unchanged compared to a comparably good implementation using classical algorithms, accounting for both elementary multiplications and memory accesses. Modular exponentiation with $n$-bit numbers including exponent remains of cost $\mathcal O(n^3)$. More precisely, for both Montgomery and classical algorithms using $w$-bit words, interleaved multiplication and reduction, and basic scanning of random exponent: $\approx{3\over w^2}n^3$ multiply-and-accumulate with double-width result, and $\approx{6\over w^2}n^3$ memory accesses (${3\over4}$ reads, ${1\over4}$ writes).
Karatsuba multiplication is a divide-and-conquer algorithm for (non-modular) multiplication, which for $n$-bit integers reduces cost from the $\mathcal O(n^2)$ for classical multiplication to $\mathcal O(n^{\log_2 3})$, that is $\mathcal O(n^{1.58\dots})$.
Applied to modular exponentiation with $n$-bit numbers including exponent, the cost goes from $\mathcal O(n^3)$ to $\mathcal O(n^{1+\log_2 3})$, that is $\mathcal O(n^{2.58\dots})$. One of several methods for getting the benefits of Karatsuba multiplication during modular reduction is pre-computing the (non-modular) inverse of the modulus to slightly more than $n$ bits, which can be done at cost $\mathcal O(n^2)$ (thus negligible as far as $\mathcal O$ is concerned) with classical algorithms.
Karatsuba multiplication is beneficial only past some threshold for $n$. That threshold vary considerably depending on an awful lot of things. In a hardware multiplier optimized for low power, Karatsuba pays for modest $n$. In the GNU MP Bignum Library, there used to be a default KARATSUBA_THRESHOLD as high as 32 for non-modular multiplication (that is, Karatsuba was used when $n\ge32w$ with typically $w=32$); the optimal threshold for modular exponentiation tending to be significantly higher. On modern CPUs, Karatsuba in software tends to be non-beneficial for things like ECDSA over P-256 ($n=256$, $w=32$ or $w=64$), but conceivably useful for much wider modulus as used in RSA.
Karatsuba multiplication can be used together with Montgomery reduction. A good way to do so is by using big segments of arguments upon which Karatsuba multiplication is used. That could be the case for example in an implementation using Montgomery in the overall algorithm, with wide words and a wide multiplier (possibly hardware) using Karatsuba. Sometime Karatsuba is used for multiplication, followed by a separate reduction step using Montgomery; in which case the overall savings allowed by Karatsuba is less than $2$, irrespective of $n$.
I suggest Modern Computer Arithmetic for more details; or the classic but still useful Handbook of Applied Cryptography, especially chapter 14.
