Generic prime

We'll use the term generic prime to denote a prime with high Kolmogorov complexity, e.g. a k-digit prime with complexity at least [math]\displaystyle{ \sqrt{k} }[/math]. Note that almost all primes are generic.

On the other hand, the finding primes conjecture is false for generic primes, as deterministic algorithms in poly(k) time can only produce numbers of complexity [math]\displaystyle{ O(\log k) }[/math]. Thus any solution of this conjecture must in some way distinguish primes from generic primes. This rules out any approach based purely on average-case results about the distribution of primes, since primes and generic primes are essentially indistinguishable in these results. (However, for the purposes of the weak conjecture, one could hope to use average-case results on relatively thin sets, of size [math]\displaystyle{ 10^{\varepsilon k} }[/math] or so.)

A factoring oracle breaks the indistinguishability between primes and generic primes, since non-generic primes cannot be given any non-trivial factoring. So generic primes do not seem to provide an obstruction to the conjecture with factoring.