Manipulating Large Numbers on a Computer:

First we must define "large". On most computer architectures, the space allocated for any integer is four bytes. Four bytes is equivalent to 32 bits which can represent an integer no larger than (about 2 billion). If the integer is signed, then the largest number that can be arithmetically manipulated at one time is (about 1 billion). Many architectures, however, will also support manipulation of 64 bit integers if the programmer explicitly asks for the space. Still, this is quite a limitation considering the context of RSA encryption. Decrypting a typical message may involve something like . It would not be possible to compute on any desktop machine because this is approximately; much bigger than any integer that can fit in a computer's register where it can be manipulated.

Decrypting a message is possible because it also uses modular arithmetic. There is no way to compute with the standard architecture, but because there is modular arithmetic involved, there is a way to keep the numbers small at each step of the computation, never allowing them to exceed (or for certain, ). The algorithm to do so is as follows: Factor the desired number into powers so that each factor can be easily computed from the previous factor. To compute each factor, we square the previous factor and then reduce modulo n.

Consider the following sample computation which could be necessary to decrypt a particular message:

First, we write:

As mentioned above, we factor into powers, each exponent of which is a power of two, because each such power is very easy to compute from the previous power. We simply have to square one to find the next.

We still have some factors that are too large to compute individually, but we start with . By properties of modular arithmetic, we can reduce modulo 355 at each step. Consider the following:

If we start with , we see that .

We will next compute , even though we do not need this particular factor. is the square of the previous term (and thus easy to compute), so

.

We can then find .

We did not need the factor either, but it enables us to easily find the next term , in which we are interested.

Continuing on...

Now we have computed all of the factors of without ever exceeding , which is less than .

We still have not finished computing the value of x. From before, we had the following:

We now know that

,

,

, and

, so we just have to find the product of these values.

.

We can reduce modulo 355 after each multiplication as follows:

.

Finally, we get, .

This algorithm demonstrates a way to solve these problems on a typical computer.

This example came from the following web page:

www.disappearing-inc.com/ciphers/rsa.html