Mathematicians have always had a problem with prime numbers, because they appear to be so random. Most numbers follow a pattern, and so future number is the series can be predicted accurately. But prime numbers are different - they seem to have no real logic to them. There are two main problems involving prime numbers:
The first one is hard enough, though in the last ten years much progress has been made. Numbers can be proved prime in a much shorter time than in previous years, so that larger and larger primes can be found; the largest known so far is 2^6972593-1 (which has 2098960 digits, and was discovered in 1999). The largest found in 2000 is 48594^65536+1 (which has 307140 digits). The table below shows how the discovery of primes is still getting better in recent years.
| Primes added in 1992 | 12 |
| Primes added in 1993 | 5 |
| Primes added in 1994 | 8 |
| Primes added in 1995 | 50 |
| Primes added in 1996 | 32 |
| Primes added in 1997 | 64 |
| Primes added in 1998 | 253 |
| Primes added in 1999 | 882 |
| Primes added in 2000 so far | 1894 |
The second problem is a far harder proposition, which gets progressively harder as the number gets larger. The problem is easy to understand - imagine I take two prime numbers, and I multiply them together. This is nice and easy and I can do it in a split second on my calculator. I get 391. What did I multiply together to get 391? The only way for you to work it out is to try dividing 391 by 2 and seeing if it works. No. So try each prime number in sequence: 391÷3. No. 391÷5? No. 391÷7? No. 11? No. Eventually you try 17, and find that 391÷17 = 23, so that 17 and 23 are the two numbers I started with. This is obviously a lot harder that it was for me to generate 391 in the first place.
At the moment, even with some clever mathematical shortcuts to the brute force method, finding the prime factors of a number with 200 digits in a sensible time is beyond current computing power and factorisation methods. In October 1999, Simon Singh published a challenge to readers of his Code Book in which they had to factor a prime number with just over 150 digits. This took the winners a little over a year to do, showing that even a relatively short number (over 300 digits long is more normal nowadays) takes ages to factor.