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?
Best Answer
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.