Deterministic way of finding primes

Terence Tao, Tim Gowers and others have a wonderful new polymath project that aims at efficient finding of large primes. The best known deterministic algorithm to find a -bit prime at this moment takes time and is based on the result that every interval contains at least one prime. Assuming Riemann hypothesis, one can deterministically find a -bit prime in time . Since the problem seems to be difficult, they also consider a number of relaxations, like allowing a unit-cost factoring oracle, or ask how to find just two large squarefree numbers and .

Now, what is a polymath project? The idea is to use the joint energy of millions of bored people, who’d otherwise just sit on Facebook, to actually do something useful. Somebody poses an interesting question and then everybody is free to take a stab on it. Hopefully, those millions of people can finally jointly solve the problem.

The current discussion thread for this project is here. Michael Nielsen has a wiki page that summarizes the known results and current ideas. Finally, Terry Tao has a number of posts about this project on his blog too.

From familiar people, I’ve spotted Avi Wigderson on those pages. I’ve also commented, though only anonymously, since I am just an egg.

About these ads