New prime number algorithm found

Three computer scientists at the Indian Institute of Technology have discovered an algorithm for determining if a number is prime which is both deterministic and relatively fast.

This is a very cool result, one that is likely to help cryptographers in the future as much of cryptography such as public key encryption is based on large prime numbers. The story mentions the “sieve of Eratosthenes”, which was a method for finding prime numbers that was determined in ancient Greece. The sieve works like this: Write down all the numbers from one to however high you want to go. Circle the number 2, which is known to be prime, and then cross out every multiple of two. Once you’ve done that, the first number that isn’t crossed out (in this case, 3) is prime. Circle it, then cross out every multiple of it. Continue on in this fashion, and when you’re done you will have circled all of the prime numbers from the range you wrote down.

This method is deterministic, in that it will find all of the primes and nothing but primes, but it’s really slow. The length of time it takes for a computer to run this algorithm grows exponentially with the size of the largest number. For really large primes, the kind that are needed for public key encryption, the fastest computer in the world would need all the time since the Earth was created and then some to run the sieve algorithm.

The new method is also deterministic but works in polynomial time, which is orders of magnitude faster. With a little refinement, it will be a boon to cryptographers everywhere.

You can read their press release here and download the algorithm itself (it’s a nine-page PDF file) here.

Related Posts:

• No Related Posts