Problem 1. Find a deterministic algorithm which, when given an integer k, is guaranteed to locate a prime of at least k digits, in time polynomial in k.
From the preliminary research thread, we’ve discovered some good reasons why this problem is difficult (unless one assumes some powerful conjectures in number theory or complexity theory), so we have also identified some simpler toy problems:
Problem 2. Find a deterministic algorithm which, when given an integer k, is guaranteed to locate an adjacent pair n, n+1 of square-free numbers of at least k digits, in time polynomial in k.
(Note that finding one large square-free number is easy – just multiply a lot of small primes together. Adjacent large square-free numbers exist in abundance, but it is not obvious how to actually find one deterministically and quickly.)
Problem 3. Assume access to a factoring oracle. Find an algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits (or an integer divisible by a prime of at least k digits) in time .
The current record time is unconditionally, or about on the Riemann hypothesis.
In the new research thread, a number of possible strategies are discussed, and will hopefully be explored soon. In addition to this thread, there is also the wiki page for the project, and a discussion thread aimed at more casual participants. Everyone is welcome to contribute to any of these three components of the project, as always.