Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I came upon an interesting way to relatively quickly compute modular exponentiation with large numbers. However, I do not fully understand it and was hoping for a better explanation.

The method basically states if you have $x^y \bmod N$, it can be computed by repeatedly multiplying by $x$ modulo $N$:

$$x \bmod N \rightarrow x^2 \bmod N \rightarrow x^4 \bmod N \rightarrow x^8 \bmod N \rightarrow \ldots \rightarrow x^{2[\log y]} \bmod N$$

This is supposed to calculate in $\mathcal{O}(\log_2 N)$ time.

An example is given:

$$x^{25} = x^{11001_2} = x^{10000_2} * x^{1000_2} * x^{1_2} = x^{16} * x^8 * x^1$$

I don't really understand how this is faster. Aren't you just doing the same thing? You're just breaking down the exponents into representations of base $2$. Also where does $x^{2[\log y]}$ come from? If you're breaking it down into exponents of two where does a logarithm come from? (Aren't logs representations of numbers in exponents of $10$?)

I'm sorry if this appears to be a really stupid question - I have minimal knowledge in math. Also, I wasn't sure if this belongs here or on stack exchange, so give me the word and I'll move it.

share|improve this question
    
When dealing with algorithmic complexity 2 is probably more common as a base for logarithms than 10. Also, it is assumed that the calculation of a product of two numbers modulo $N$ takes (or rather defines) one unit of time. –  Jyrki Lahtonen Mar 12 '12 at 20:29
add comment

3 Answers

up vote 0 down vote accepted

Explaining where the log comes from and how this is faster is a good question and it's the same whether you multiply the usual way or mod(N). But faster than what? The issue is how many multiplications and how many additions are required, with the assumption that multiplications are inherently slower than addition, a lot slower.

The usual way to compute $x^y$ for integer y is simply to multiply x by x, then x by the result, and so on, y times. Obviously this requires $y-1$ multiplications and no additions, 24 in your example.

The method of repeated squaring, on the other hand, uses the fact that any exponent $y$ can be written as the sum of powers of two: 1, 2, 4, 8, 16 and so on, which is the basis of the binary number system. Your breakdown of 25 into 16 + 8 + 1 is a good example, and the way it comes from the binary representation of 25 should be sufficient to convey the process to anyone who understands binary representation.

Then, ask yourself what is the most such powers of two that could be required. Clearly, it's the number of binary places in the representation of y, which is $\log_2(y)$, or more precisely $\lceil \log_2(y) \rceil$, ($\lceil x \rceil$ is the ceil or next higher or equal integer function). So the $\log$ here is base 2, not base 10 (but those only differ by a constant factor, namely $log_{10}(2) \approx .301$), which really tells you how many doublings are needed to go from 1 to $y$. In your example, $log_2(25)$ is about 4.64 ($\log_{10}(25)/.301$), so the most powers of two needed is 5.

Last question is, how many arithmetic operations are needed to carry out this method? To get the 5 powers of 2 in your example by repeated squaring you need only 4 multiplications: $x^2 = x \times x, x^4 = x^2 \times x^2, x^8 = x^4 \times x^4, x^{16}=x^8 \times x^8$). Of course, you also need some additions, but they are computationally "cheap", and I'll leave it to you to figure how many of them might be required.

Finally you need to multiply together the powers -- $x^{16} \times x^8 \times x^1$ in this case, which might involve yet one more set of up to 4 or $\lceil \log_2(y)\rceil-1$ multiplications.

So, the general answer is you will need $2 \times\lfloor \log_2(y)\rfloor$ multiplications rather than $y-1$ the "slow" way, or 8 versus 24 for your example -- a big time savings, even bigger for longer numbers, especially if it in the innermost loop of a program and gets done zillions of times.

Bill Dubuque's answer is really this method written out in a special polynomial form which accomplishes the required multiplications and additions efficiently and elegantly.

share|improve this answer
    
Thank You, that made perfect sense. –  user26649 Mar 12 '12 at 21:01
    
@FarhadYusufali: As Jyrki Lahtonen explains, you need a few more (as many as twice) to get the intervening powers mixed in, but it is still an improvement. You can also be clever, like making $x^12=((x^2x)^2)^2$. The minimum is shown in oeis.org/A003313 –  Ross Millikan Mar 12 '12 at 22:10
    
Right about doubling -- to actually multiply the powers together. And yes, you can do even better -- I was just looking for a simple bound. I will fix my answer. –  David Lewis Mar 13 '12 at 0:01
add comment

This is known as repeated squaring. It deserves to be better known that this arises simply from writing the exponent in binary radix in Horner polynomial form, i.e. $\rm\ d_0 + x\ (d_1 + x\ (d_2\ +\:\cdots))\:.\ $ Below is an example of computing $\rm\ x^{101}\ $ by repeated squaring. Note that the repeated square form arises simply from performing various substitutions into the binary polynomial Horner form namely $\rm\ 1\to x,\ \ 0\to 1,\ \ (n)\:2\to (n)^2\ $ into $101_{10} = 1100101_2\ $ expanded into Horner form, viz. enter image description here

share|improve this answer
add comment

Let's count how many modular multiplications we need to do to get to $x^{25}$ with the two methods. The trivial method would need 24 multiplications (I leave out the calculation of the residue modulo $N$ - that will always be there): $x^2=x*x$, $x^3=x^2*x$, $x^4=x^3*x$, $\ldots$, $x^{25}=x^{24}*x$. With repeated squaring there are several approaches. We might first compute $x^2=x*x$, $x^4=(x^2)*(x^2)$, $x^8=(x^4)*(x^4)$, $x^{16}=(x^8)*(x^8)$. That is 4 multiplications so far. The point of doing this to store these values somewhere. Then we can compute $x^{24}=(x^{16})*(x^8)$ and $x^{25}=(x^{24})*x$ with just two extra multiplications. A total of 6 multiplications in comparison to 24. In the worst case we need to do about $2*\log_2m$ multiplications to compute $x^m$.

If you don't have enough memory to store that look table of powers $x^{2^k},k=0,1,\ldots,[\log_2m]$, then you can get away with less by using the approach outlined in Bill Dubuque's answer. In addition to $x$ itself you only need to store one other intermediate value. Here $25=11001_2$, and for a hopefully obvious reason I will also write the exponents in binary in parentheses in what follows. First compute the square $$ x^2=(x^{10_2})=x*x. $$ We notice that our exponent $25=11001_2$ begin with two 1s, so next we multiply this result with $x$ and calculate $$ x^3=(x^{11_2})=(x^2)*x. $$ Notice that this calculation needed only the result of the previous multiplication and the input $x$. Let's square this $$ x^6=(x^{110_2})=(x^3)*(x^3). $$ Again we only needed the previous output $x^3$. Now we have the three leading bits from the exponent correctly in place, or because the third bit (starting with the most significant) of the exponent was 0, there is no need to multiply this by $x$. So we square again and get $$ x^{12}=(x^{1100_2})=(x^6)*(x^6). $$ Again we only needed the previous result ($x^6$). The fourth bit of the exponent was also a zero, so we can proceed with the final squaring $$ x^{24}=(x^{11000_2})=(x^{12})*(x^{12}). $$ The "previous value only" -comment applies again. The final bit of the exponent was a '1', so we need to fix it. The last multiplication is $$ x^{25}=(x^{11001_2})=(x^{24})*x. $$ To summarize: We square repeatedly. If the next bit of the exponent is a '1' we insert an extra multiplication with the original input.

share|improve this answer
    
Bill Dubuque's ability to compress an answer is something special. My motivation for adding this was to break down an example case very explicitly, and also to explain that using the Horner form gives memory savings in comparison to the more straightforward squaring. That may be critical in some applications, where you need to implement this on a small chip. Crypto applications come to mind. –  Jyrki Lahtonen Mar 12 '12 at 19:48
    
Thank You, that really helped. Just one question- I still don't see where you get the number 2∗log2m from. Could you show how you arrived at that number? –  user26649 Mar 12 '12 at 20:26
    
We need to do $[\log_2m]$ squarings (for the purposes of complexity I treat suqaring as a special case of a product) to compute all those $x^2, x^4, x^8, \ldots$ in the first stage. In the second stage we need to A) pick at most $\lceil \log_2m\rceil$ among the original input $x$ and the entries from the newly computed look-up-table and B) multiply them together. The worst case is when $m=11\ldots11_2$. We get away with one less multiplication for each zero in the binary expansion of $m$. –  Jyrki Lahtonen Mar 12 '12 at 20:38
add comment

Your Answer

 
discard

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