Question of the Week: How can computers calculate exponential math without overflow errors?

This weeks question of the week comes from Kit-Ho who poses:

Studying some RSA encrypt/decrypt methods, I found this article: An Example of the RSA Algorithm It requires this to decrpyt this message  The total result of  is so big, for a 64-bit/32-bit machine, I don’t believe it can hold such a big value in one register. How does the computer do it without an overflow?

For those of you that may not know what this “Overflow” that Kit mentioned, he’s talking about a term Stack Overflow.   Here’s the official “Wiki” definition:

In software, a stack overflow occurs when too much memory is used on the call stack. The call stack contains a limited amount of memory, often determined at the start of the program. The size of the call stack depends on many factors, including the programming language, machine architecture, multi-threading, and amount of available memory. When a program attempts to use more space than is available on the call stack (that is, when it attempts to access memory beyond the call stack’s bounds, which is essentially a buffer overflow), the stack is said to overflow, typically resulting in a program crash.  This class of software bug is usually caused by one of two types of programming errors.    

As pointed out by Dennis (thanks!) I completely got this wrong.  Stack overflow isn’t the issue, but rather integer overflow:

In computer programming, an integer overflow occurs when an arithmetic operation attempts to create a numeric value that is too large to be represented within the available storage space. For instance, adding 1 to the largest value that can be represented constitutes an integer overflow. The most common result in these cases is for the least significant representable bits of the result to be stored (the result is said to wrap). On some processors like GPUs and DSPs, the resultsaturates; that is, once the maximum value is reached, attempts to make it larger simply return the maximum result.  

For example, a mechanical odometer, has a rollover (or reset) after a certain amount of miles:

This is the same as computer integer overflow, where the size of the numbers needed are greater than the object type can hold.  Kit-Ho’s example RSA link exceedes the C#’s max value of 18,446,744,073,709,551,615 of the long type.

Dietrich Epp came up with a great answer as to how computers can calculate these large numerical calculations:

Because the integer modulus operation is a ring homomorphism (Wikipedia),

(X * Y) mod N = (X mod N) * (Y mod N) mod N 

You can verify this yourself with a little bit of simple algebra. Computers use this trick to calculate exponentials in modular rings without having to compute a large number of digits. In algorithmic form,

 
-- compute X^I mod N  
function expmod(X, I, N)  
    if I is zero 
        return 1 
    elif I is odd 
        return (expmod(X, I-1, N) * X) mod N 
    else Y <- expmod(X, I/2, N) 
        return (Y*Y) mod N 
    end if 
end function 

You can use this to compute (855^2753) mod 3233 with only 16-bit registers, if you like. However, the values of X and N in RSA are much larger, too large to fit in a register. A modulus is typically 1024-4096 bits long! So you can have a computer do the multiplication the “long” way, the same way we do multiplication by hand. Only instead of using digits 0-9, the computer will use “words” 0-2¹⁶-1 or something like that. (Using only 16 bits means we can multiply two 16 bit numbers and get the full 32 bit result without resorting to assembly language. In assembly language, it is usually very easy to get the full 64 bit result, or for a 64-bit computer, the full 128-bit result.)

-- Multiply two bigints by each other 
function mul(uint16 X[N], uint16 Y[N]): 
    Z <- new array uint16[N*2] 
    for I in 1..N 
        -- C is the "carry" 
        C <- 0 
        -- Add Y[1..N] * X[I] to Z 
        for J in 1..N 
            T <- X[I] * Y[J] + C + Z[I + J - 1] 
            Z[I + J - 1] <- T & 0xffff 
            C <- T >> 16 
        end 
        -- Keep adding the "carry" 
        for J in (I+N)..(N*2) 
            T <- C + Z[J] 
            Z[J] <- T & 0xffff 
            C <- T >> 16 
        end 
    end 
    return Z 
end 
-- footnote: I wrote this off the top of my head 
-- so, who knows what kind of errors it might have 

This will multiply X by Y in an amount of time roughly equal to the number of words in X multiplied by the number of words in Y. This is called O(N²) time. If you look at the algorithm above and pick it apart, it’s the same “long multiplication” that they teach in school. You don’t have times tables memorized out to 10 digits, but you can still multiply 1,926,348 x 8,192,004 if you sit down and work it out. Long multiplication:

 
    1,234 
  x 5,678 
 --------- 
    9,872 
   86,38 
  740,4 
6,170 
--------- 
7,006,652 

There are actually some faster algorithms around for multiplying (Wikipedia), such as Strassen’s fast Fourier method, and some simpler methods which do extra addition and subtraction but less multiplication, and so end up faster overall. Numerical libraries like GMP are capable of selecting different algorithms based on how big the numbers are: the Fourier transform is only the fastest for the largest numbers, smaller numbers use simpler algorithms.