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).