Brent Yorgey/YouTube

An ancient Greek algorithm could reveal all-new prime numbers

Moar primes!

FIONA MACDONALD
28 SEP 2016
 

In case you missed it, mathematicians are pretty obsessed with prime numbers - the limitless 'atoms' of the mathematical world that are only divisible by themselves and one.

People are so into them, in fact, that there's a continual push (and even financial incentive) to compute larger and larger new prime numbers.

 

But one of the world's top mathematicians thinks the key to taking things to the next level could come from an ancient Greek algorithm, called the sieve of Eratosthenes.

The sieve of Eratosthenes is pretty much what it sounds like - a mathematical sieve that helps people filter out prime numbers.

Developed by Eratosthenes of Cyrene, a Greek mathematician and astronomer (and former director of the famed Library of Alexandria) back in around 240 BC, the sieve allows people to determine all the primes between a certain set of numbers.

It works by having you write all the numbers out (say 1 to 100) and then you start crossing numbers off in a particular order - the multiples of 2 (other than 2) are first to go, then the multiples of 3, etc. starting from the next number that hadn't been crossed out.

Any remaining numbers on your messy piece of paper have survived the sieve, and therefore must be primes.

That sounds a little clunky for today's standards (the latest prime number discovered was 22 million digits long), but the sieve of Eratosthenes can also be turned into an algorithm that computers can use to run primes.

 

There's one big problem with that algorithm, though - it takes up a crap load of memory, making it pretty inefficient for modern mathematicians to use.

But now a top mathematician, Harald Helfgott, has found a way to streamline the sieve of Eratosthenes algorithm - and thinks it could hold the key to future prime number discoveries.

Helfgott is a Peruvian mathematician from France's National Centre for Scientific Research and the University of Göttingen in Germany. He rose to fame in the maths world when, back in 2013, he solved a 271-year-old problem called Goldbach's weak conjecture.

Now, according to Matías Loewy from Scientific American, Helfgott has set his sights even further back, and come up with an improved version of the sieve of Eratosthenes that reduces the amount of computer memory it requires.

"Like many other children, I was taught this it in primary school when I was 10, with a table," Helfgott told Loewy, referring to the sieve.

Realising that there must be a way to make it efficient with modern computers, he used something called the circle method to make the sieve of Eratosthenes work with a whole lot less memory.

"In mathematical terms: instead of needing a space N, now it is enough to have the cube root of N," writes Loewy.

That might not sound that impressive, but mathematician Jean Carlos Cortissoz from Cornell University and Los Andes University, who wasn't part of the research, puts it into perspective for Scientific American:

"Let's pretend that you are a computer and that to store data in your memory you use sheets of paper. If to calculate the primes between 1 and 1,000,000, you need 200 reams of paper (10,000 sheets), and with the algorithm proposed by Helfgott you will only need one fifth of a ream (about 100 sheets)."

That condensing could slow things down a bit, but Helfgott believes computers could be able to make up for that by using cache memory, which is smaller but faster than RAM.

There are plenty of other techniques and algorithms out there that mathematicians are using for finding primes, but what Helfgott thinks sets the sieve of Eratosthenes apart is that it could also be used to perform operations such as factorisation - the basis of modern cryptography.

And, who knows, it could also be the tool that helps him find the next new prime number. With US$150,000 on the line for whoever finds the first 100-million-digit prime, there's a lot of incentive out there.

The ideas behind the upgraded sieve of Eratosthenes was presented in July at the XXI Latin American Colloquium of Algebra in Buenos Aires, and Sinapsis 2016 in Paris.

More From ScienceAlert