This is the simplest to explain of the procedures involved in implementing RSA.
One can raise a number, preferably a suitably small one, such as 1.0001, to the 1024th power on a pocket calculator fairly quickly. Just push the x squared button ten times.
Thus, the algorithm for fast exponentiation resembles a method of multiplication called "Russian Peasant Multiplication", and proceeds as follows:
Let result=1.
Convert the desired exponent to binary notation, and note its length in bits. Let n be this length, and store the bits of the exponent in an array, with the least significant bit in a(1), up to the most significant bit in a(n).
Let base=the number being raised to the power.
For i = 1 to n: ( if a(i)=1 : ( result = result * base ) ; if i < n : ( base = base * base ) )
The methods involved in performing multi-precision arithmetic in the ordinary fashion are simply scaled-up versions of the decimal hand arithmetic one learned in school, but using a base just under the square root of the available integer size.
A fancier method of multi-precision arithmetic, known as Schönhage-Strassen multiplication exists. It is usually practical, though, only for numbers even larger than those used in performing RSA. If you want to calculate pi to a million digits, you will need it. Although it shouldn't be needed for RSA, I will still try to explain it a little.
Schönhage-Strassen multiplication involves taking the string of digits that makes up a number, and subjecting it to a Fast Fourier Transform, and then multiplying (and also adding) the frequency coefficients of the transform individually. The imaginary as well as the real components of the transform are retained in the actual Schönhage-Strassen method.
How on Earth can such a thing work? How can arithmetic still be done with a number after its digits have been subjected to so frightful an insult?
I will try, at least, to make it plausible by illustrating a somewhat debased form of Schönhage-Strassen arithmetic.
An old idea of a way to perform addition and multiplication very quickly on large numbers is called radix arithmetic. If you have, for two numbers, their remainder modulo a series of relatively prime numbers, then you have uniquely identified each number modulo the product of all those relatively prime numbers.
And you can add, subtract, or multiply the separate residues independently, and get a correct result within the range of representable numbers.
An old way of finding the value of a decimal number, modulo 9, is by adding all its digits together.
The remainder when you divide a number by 11 can be found by subtracting the digits in even positions (counting the last digit as digit 1) from the digits in odd positions.
Adding all the digits together is, in Fourier-transform terms, taking the DC component of the digit string; taking the differences of alternating digits is, from that viewpoint, taking the component with a wavelength of length two digits.
Thus, a number from 0 to 9999 can be uniquely identified by its remainders modulo 99 and modulo 101, which can be found by breaking the number into halves and adding and subtracting the halves. 99 can be split into 9 and 11 in the same way; since 101 is bigger than 99, and 10001 is bigger than 9999, the method becomes a little more complicated than would be nice, but it can still be made to work.
Taking a number apart into its remainders modulo various numbers is easy enough. But how does one put a number back together from this form?
For example, 1001 is 7 times 11 times 13. So one could identify any three-digit number uniquely with its remainders after division by 7, 11, and 13.
These remainders are determined by division, but given the remainders, how does one determine the number?
The answer is as follows:
One uses a linear combination of the various moduli, modulo their product.
For the case where there are three moduli, a, b, and c, and x, y, and z are the remainders of our number for each of these moduli respectively, the formula for the original number is:
( ibcx + jacy + kabz ) modulo abc
where i, j, and k are defined as follows:
ibc modulo a = 1 jac modulo b = 1 kab modulo c = 1
The reasoning behind this should be obvious:
Thus, if we know the residues modulo 7, 11, and 13 of a number (say they are 1, 5, and 6) then the number must be
( i * 143 * 1 + j * 91 * 5 + k * 77 * 6 ) modulo 1001
Since 143 is equal to 3 modulo 7, i must equal 5 (5*3=15, one more than 14=2*7); since 91 is equal to 3 modulo 11, j must equal 4 (4*3=12, one more than 11); since 77 is equal to 12 modulo 13, k must equal 12 (12*12=144, one more than 143=11*13).
Thus, the number we're looking for must be:
(715 * 1 + 364 * 5 + 924 * 6) modulo 1001 or (715 + 1820 + 5544) modulo 1001 or 8079 modulo 1001 or 71
And, indeed, 71 is 1 modulo 7 (71 - 7*10 = 1), and 5 modulo 11 (71 - 6*11 = 5), and 6 modulo 13 (71 - 5*13 = 6).
Applying this to the case of breaking a number into pieces by addition and subtraction, what do we find for how we can invert the process?
Thus: if we wish to perform multiplication modulo 99999999, then we can split the numbers up into pieces: each number is split up into two four digit halves. Their sum is made modulo 9999. Their difference - with the least significant half being positive - is made modulo 10001.
We can multiply the numbers modulo 9999 and the numbers modulo 10001 independently. Now what happens when we reconstitute?
The answer, from what we've seen above, is that the sum has to be multiplied by something that is 1 modulo 9999, and 0 modulo 10001. And the difference has to be multiplied by something that is 1 modulo 10001 and 0 modulo 9999. Then the two can be added to form the product.
10001 itself is equal to 2 modulo 9999. So to get 1 modulo 9999, we need to multiply 10001 by 5000, since 5000 times 2 is 10000, which is 1 modulo 9999.
9999 itself is equal to 9999, or -2, modulo 10001. So to get 1 modulo 10001, we can multiply 9999 by 5000. This produces -10000, which again is 1 modulo 10001.
So now we see the key to making large number multiplication work in this simplified form.
Let us do an example:
We wish to multiply
2174 3129 4026 8021
by
5408 2176 9330 4427
modulo
9999 9999 9999 9999 9999 9999 9999 9999
a sufficiently large modulus that we will get the real product of the two numbers.
0000 0000 0000 0000 2174 3129 4026 8021
becomes
2174 3129 4026 8021 modulo 9999 9999 9999 9999 2174 3129 4026 8021 modulo 1 0000 0000 0000 0001
and
0000 0000 0000 0000 5408 2176 9330 4427
becomes
5408 2176 9330 4427 modulo 9999 9999 9999 9999 5408 2176 9330 4427 modulo 1 0000 0000 0000 0001
2174 3129 4026 8021 modulo 9999 9999 9999 9999
becomes
6201 1150 modulo 9999 9999 1852 4892 modulo 1 0000 0001
and
2 174 312 940 268 021 modulo 10 000 000 000 000 001
(note that since 1 0000 0000 0000 0001 is greater than 9999 9999 9999 9999, we have to split it into bigger halves to guarantee getting the right result) becomes
942 442 333 modulo 999 999 999 938 093 709 modulo 1 000 000 001