Appendix A - Why big primes are useful

Summary

Bernhard Riemann and other mathematicians from his time (the nineteenth century) investigated prime numbers only because they were intrigued by their mathematical properties. But at the end of the twentieth century it turned out that big prime numbers had completely unexpected applications in cryptography, the science of secret writing. Using modern cryptographic methods, digital messages can be enciphered and provided with digital signatures in a virtually unbreakable way. Anyone banking electronically or paying bills via the internet uses this technique. In many cryptosystems primes of more than a hundred digits are used. One such system is RSA, dating from 1976. RSA is an acronym of the surnames of its inventors Rivest, Shamir and Adleman. Their system rests, among others, on the following mathematical pillars:

1. Big primes exist in an incredible amount. For instance, the number of primes with one hundred digits is greater than the number of elementary particles in the universe (this is estimated to be a number of about 80 digits).

2. There are very fast methods (prime tests) to check whether big numbers (say, of a few hundred digits) are prime.

3. Therefore it is easy to find in a very fast way such big primes at random.

4. If a prime test for a big number establishes that it is a composite number (so not a prime), such a test does notyield a factorization. Whether or not it is a prime is determined by advanced, indirect mathematical methods and not by factoring.

5. So for big numbers there is an essential difference between prime testing and factorization. The former is practically easy, while the latter is much more difficult.

6. The best known factorization methods don't get farther than numbers of at most 180 digits. Even using the most powerful computers, such a factorization may take months or even years. For the factorization of numbers ofmore than 200 digits (without easy to find small factors), using the most powerful computer methods will take longer than the age of the universe.

So anyone with a laptop computer with a suitable computer algebra package may provide himself or herself with an unbreakable personal secret:

1. a. Find two big primes pand q, both of at least 100 digits.

2. b. Compute their product m= p× q. Publishm, for instance via the internet, but keep p and q secret. Then nobody else will be able to factor m into its prime factors p and q.