Prime numbers and how to find them

Prime numbers have now become a crucial part of modern life, but they have been fascinating mathematicians for thousands of years.

A prime number is always bigger than 1 and can only be divided by itself and 1 – no other number will divide in to it. So the number 2 is the first prime number, then 3, 5, 7, and so on. Non-prime numbers are defined as composite numbers (they are composed of other smaller numbers).

Prime numbers are so tantalizing because they seem to be in never ending supply, and are distributed somewhat randomly throughout all the other numbers. Also, no-one has (yet) found a simple and quick way to find a specific (new) prime number.

Because of this, very large prime numbers are used every day when encrypting data to make the online world a safer place to communicate, move money, and control our households. But could we ever run out of prime numbers? How can we find new, incredibly large prime numbers? Below is a brief explanation about how we can do this:

This got us interested in learning more about primes, so we’ve collected together some facts about these elusive numbers:

• A simple way to find prime numbers is to write out a list of all numbers and then cross off the composite numbers as you find them – this is called the Sieve of Eratosthenes. However, this can take a long time!
• In 2002 a quicker way to test whether a number is prime was discovered – an algorithm called the ‘AKS primality test’, published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena.
• Even though prime numbers seem to be randomly distributed, there are fewer large primes than smaller ones. This is logical, as there are more ways for large numbers to not be prime, but mathematicians ask: how much rarer are larger primes?
• In 2001 a group of computer scientists from IBM and Stanford University showed that a quantum computer could be programmed to find the prime factors of numbers.
• The RSA enciphering process, published in 1978 by Ron Rivest, Adi Shamir, and Leonard Adleman, is used to hide plaintext messages using prime numbers. In this process every person has a private key which is made up of three numbers, two of which are very large prime numbers.
• At any moment in time, the largest known prime number is also usually the largest known Mersenne prime.

Featured image credit: numbers by morebyless. CC-BY-2.0 via Flickr.