**RSA algorithm**

Let P and Q be two prime numbers, and compute N = P Q and N' = (P-1)(Q-1). Let E be a number coprime to N' and D such that D E = 1 mod(N'). D can be easily computed by using the extended Euclid's algorithm. The pair (E,N) is the public key, the pair (D,N) is the secret key. Of course the lagorithm is broken if the number N can be easily factored so that the two factors P and Q are known.

In order to encode a message M we must have M < N.
To encode the message compute M^{E} mod(N).
To do this write the binary representation of E =
e_{0}e_{1}...e_{n}. Then we must compute
M to the power Sum_{i} e_{i}2^{i} that is the
product of the n factors M^{ei2i}.
The n powers M_{i} = M^{2i} can be computed
recursively: M_{0} = M, and each subsequent number is the
square of the preceeding one.
Finally the encoded message M' = M^{E} is obtained from the product
Prod_{i} M_{i}^{ei}.

To decode the message, simply compute the D power of M', ( mod(N) ).
This is equivalent to computing M^{D E} = M^{k N' + 1}
and by Fermat's little theorem this is congruent to M modulo N.
By the Chinese Remainder Theorem any number congruent to M modulo N
differ from M by a multiple of N.
Therefore M^{D E} = M mod(N).

Marco Corvi - 2003