This post will be somewhat abridged due to my traveling schedule.
Currently we are up against the “square root barrier”: the fastest time we know of to find a k-digit prime is about (up to factors), even in the presence of a factoring oracle (though, thanks to a method of Odlyzko, we no longer need the Riemann hypothesis). We also have a “generic prime” razor that has eliminated (or severely limited) a number of potential approaches.
One promising approach, though, proceeds by transforming the “finding primes” problem into a “counting primes” problem. If we can compute prime counting function in substantially less than time, then we have beaten the square root barrier.
Currently we have a way to compute the parity (least significant bit) of in time , and there is hope to improve this (especially given the progress on the toy problem of counting square-frees less than x). There are some variants that also look promising, for instance to work in polynomial extensions of finite fields (in the spirit of the AKS algorithm) and to look at residues of in other moduli, e.g. , though currently we can’t break the barrier for that particular problem.