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*