LAST month Cray Research announced the discovery of a record prime number*. It has 378,632 digits, and would take four days, nine hours, 10 minutes and 32 seconds to read at one digit per second.
What are prime numbers? Why would anyone be interested in them? And what is the connection between prime numbers and public key cryptography causing organisations such as the US National Security Agency to have such an interest in them?
Primes are numbers having exactly two factors. For example, 7 is prime (factors 1 and 17), whereas 15 isn't (factors 1, 3, 5 and 15).
The primes are: 2, 3, 5, 7,11, 13, 17 ... In Ancient Greece, Euclid proved that there was an infinite number of primes, and made a remarkable discovery relating certain primes to "perfect numbers".
By Euclid's time there was an especially interesting classification of whole numbers: they were considered to be abundant, deficient or perfect. A number was deemed abundant if the sum of all its factors (excluding itself) was more than itself. So the number 12 is abundant because 1+2+3+4+6 is more than 12. A deficient number is the opposite - replace "more" by "less". For example, 15 is deficient because 1+3+5 is less than 15. These type of number are very common; of the first 1,000, 246 are abundant and 751 are deficient. The "missing" ones - 6, 28 and 496, each having factor sum (itself excluded) equal to itself (e.g. 28=1+2+4+7+14) were deemed to be "perfect" because of their rarity. How many are there altogether? The simple, humbling answer is that nobody knows.
Prime and perfect
Until 1536 AD, it was wrongly believed that there was an infinite number of them. That dated back to Euclid, who found a beautiful connection between perfect numbers and a certain kind of prime number. He discovered that from a prime, which is a power of 2 less 1, one can create a perfect number by multiplying the prime by an intimately related power of 2.
127=2x2x2x2x2x2x2-1=2 7-1 is a prime, and one can create a perfect number from 127 by multiplying
27x64=2x2x2x2x2x2=2 6=8,128.
The three earlier perfect numbers 6,28 and 496 are formed in similar fashion:
6=2x(2 2-1)=2x3
28=22x(2 3-1)=4x7
296=24x(2 5-1)=16x3
And the next prime after 127 of the same kind? It was thought to be 2,047 (=2 11-1) until 1536 AD, when it was noted that 2,047=23x89. By the end of the 700s the record was 2,147,483,647 G-2 31-1). It was found by Euler, the greatest mathematician of that century, and it was believed to be the largest prime that would ever be discovered.
Then by the end of the 1800s Lucas pushed the record up to a 39 digit number (2 127-1), which remained the record until 1952. Since then the ideas of Lucas together with ever increasing computing power have pushed the record up dramatically.
But what have primes to do with computers? Once thought to be of no practical value whatsoever, primes have been in the forefront of mathematical activity since 1978, following revolutionary developments in the field of cryptography.
The Netscape connection
In a nutshell, powerful new cryptographic methods such as RSA public key cryptography which is incorporated into Netscape's Web browser software - rely on a deceptively simple sounding problem in connection with prime numbers, which is a major challenge for theoreticians and practitioners of the art of factoring.
Take two small primes, multiply them together, and reveal their product. There would he little difficulty in finding those primes from their product. Given that the product was 91, the primes would be 7 and 13.
But here's the crunch: given the product of two large primes, not only would you have great difficulty in finding them, but so would - for example - the US National Security Agency. The revolution has been to exploit that difficulty in order to create very secure cryptographic methods.