Big O for modular exponentiation?

Question

I am reading the Algorithms textbook by Dasgupta, Papadimitriou and Vazirani. To compute x^y mod N for large values of x y and N, they state:

"To make sure the numbers we are dealing with never grow too large, we need to perform all intermediate computations modulo N. So here's an idea: calculate x^y mod N by repeatedly multiplying by x modulo N. The resulting sequence of intermediate products,

x mod N -> x^2 mod N -> ... -> x^y mod N

consists of numbers that are smaller than N... But there's a problem: if y is 500 bits long, we need to perform y-1 ~ 2^500 multiplications! This algorithm is clearly exponential in the size of y."

I get where the y-1 multiplications are coming from (and I assume the 2^500 comes from the assumption that we are multiplying by two every time under a binary sysytem?), but how is this exponential in the size of y?

Answer 1

Suppose $y$ is 9999. Then its size—that is, the number of digits—is 4, but to perform $y$ multiplications is 9,999 multiplications, which is almost $10^4$.

In general, the magnitude of a number is exponentially larger than the length of the numeral used to write it. A number with $n$ base-10 digits might be as large as $10^n-1$. 3 digits is very little, but with 3 digits you can write \$999, which is a significant amount of money. 6 digits is only twice as many, but with six digits you can write \$999,999, which is more money than I have ever seen in one place. With nine digits you can write \$999,999,999 which is the size of a large corporation. With twelve digits you are up to \$999,999,999,999, which is the size of a large country. By fifteen digits, you are writing an amount that is far greater than the monetary value of everything in the world. This is typical exponential growth.

A number that, like $y$, is $n$ bits (binary digits) long, could be as large as $2^n-1$. A 500-bit number like $y$ is quite manageable, easy to store, quick to read and write. But to perform some action $y$ times will take the entire life of the universe.

Answer 2

I believe he is talking about computing:

$$ \underbrace{(...(((x \mod n) \times x) \mod n) \times x...)}_\text{y times} $$

Assuming $y$ is represented in binary then it's size is $s=\log_2 y$. So the number of multiplications is $2^s$.

Hopefully the next thing that the author mentions is the actual way that everyone does modular exponentiation, which is by repeated squaring, which off the top of my head takes worst case about $2s$ multiplications.