An Interactive Applet powered by Sage and MathJax.
(By Alyssa Vorpahl and Prof. Gregory V. Bard)
This page describes one of the algorithms we use to calculate exponentiations in modular arithmetic, a method called "Rapid Modular Exponentiation".
This algorithm is necessary for large-sized numbers, and even medium-sized numbers. For example, numbers such as 456123 mod 789 would be far too small for any application in cryptography. Even so, we do not compute 456123 in ordinary integers, and then reduce mod 789 at the end. That's because 456^123 as an integer has 328 digits, and the final answer is between 0 and 788. In the RSA cryptosystem, we encrypt a plaintext message m with an encryption exponent e and a modulus N by computing me mod N. However, N and e typically have more than 300 digits each.
This is in stark contrast to when we do modular arithmetic with paper and pencil, while first learning it. We perform operations such as addition, subtraction, multiplication, and exponentiation as normal, then subtract the modulus from the answer, possibly many times, until the answer is between 0 and the modulus. (This is called 'reducing mod N'.) However, if we were to do this with the large integers often seen in cryptography, it would be too large for many computers (especially smart cards, smart phones, or the devices that handle credit card purchases) to handle. So, the rapid modular exponentiation algorithm was devised to make calculating exponents less taxing.
To begin with, we consider the base value m and the exponent e, and how e would be written in binary (for example, if e = 23, then in binary e would be written as 10111 since 23 = 16+4+2+1). We store this binary representation as an array with length len. Then, for each i such that 0 ≤ i < len, we calculate m2i. For the exponent 23, we would compute m1, m2, m4, m8, and m16, but not m32. In other words, we compute m to all exponents that are powers of 2, starting with 1, and ending with the largest power of 2 that is still less than the desired exponent (which is 16 in this case, since 32 is greater than the desired 23).
Note that we can compute these 'power of 2' exponents very quickly. Surely m1 is just m. Then m2 is the square of that, m4 is the square of m2, m8 is the square of m4, and m16 is the square of m8. However, after each squaring, we reduce mod N. Next, we take all the powers of 2 that are associated with 1s, and multiply them together. In this case, the 1, 2, 4, and 16 positions are 1s, but the 8 position is a 0. So, we will multiply m, m2, m4, and m16 together. Of course, we reduce mod N after each multiplication.
The reason this works is because ax*ay*az = ax+y+z in general. In our example, m1*m2*m4*m16 = m1+2+4+16 = m23. Let's now consider another example.
If we wanted to raise a number m to the 70th power, we first convert 70 to binary and obtain 1000110, because 64+4+2 = 70. Then we will compute m1 = m, m2, m4, m8, m16, m32, and m64. This time, only the 2, 4, and 64 positions are 1s. So, we multiply m2*m4*m64 = m2+4+64 = m70.
Unfortunately, it might be more difficult to read this Python code than most of the interactive webpages in this sequence, because of the way that the arrays are indexed. Sometimes we have to count from left-to-right, and sometimes from right-to-left. This appears to be unavoidable in this case.
Once you load the applet, there will be 3 sliders: one to control the base value m, one to control the exponent e, and one to control the modulus N.