Section 5. RSA public-key cryptography.

Frequently it is (correctly) stated that a fundamental element in the renowned RSA cryptographic method is the use of the Fermat-Euler theorem: let n ( ) be a natural number, and a be any integer with , then (mod n ), where is the Euler phi -function (the number of integers between 1 and n that are relatively prime to n ).

In fact it is only a very special case of this theorem that is needed for the RSA application, namely the case where , where p and q are distinct primes (in practical applications p and q are both large, and with some added refinements for security purposes). A fairly detailed exposition of the RSA method may be read in my Maple public lecture - Bill Clinton , Bertie Ahern , and digital signatures - in the Maple Public and Other Lectures section of my web site.

The two prime version of Fermat's little theorem is simply this: let

p and q be distinct primes (in cryptographic applications they will be large, but not just merely large (as is sometimes incorrectly stated); to see why , refer to Section 6 )

a be any integer with (mod p ) and (mod q )

then

(mod pq )

One may easily give a proof [see Section 8] of the two prime version which is independent of the normal proof of the full Fermat-Euler result. Here I merely give a Maple numerical illustration:

> restart;

> p := nextprime(10^50 + rand()*rand()*rand());

> q := nextprime(10^60 + rand()^2*rand()^3);

> a := rand()^2 + 30!;

> igcd(a, p);

> igcd(a, q);

> a&^((p-1)*(q-1)) mod p*q;

>