Modular Exponentiation

We promised you that we would go through some of the mathematical details of the RSA algorithm. If you are not interested in the details, feel free to skip to the next section.

Modular exponentiation means that we want to find $c$, given general integers $a$, $b$, and $N$, where

$$c = a^b \bmod N.$$

In other words, $c$ is the remainder of dividing $a^b$ by $N$. We could use a brute force method to find $c$: calculate $a^b$ and then divide by $N$ to find the remainder $c$. The difficulty is that $a$, $b$, and $N$ might be large numbers, which need to be stored as exact binary sequences, and $a^b$ is extremely large and must be stored exactly. Also, carrying out the division by $N$ will be time consuming. However, once we have chosen $a$ and $N$, there is a simple algorithm to find $c$ that avoids the large number issues:

1. Set $c=1,b^′ =0$.
2. Increase $b^′$ by $1$.
3. Set $c=(a·c)b^′ \bmod N$.
4. If $b^′ <b$, go to step 2. Otherwise, $c$ is the solution to $c = a^b \bmod N$.

Note that $b^{\prime}$ serves as an index to keep track of the loops through the algorithm. Here is a flow chart for the algorithm: