Factoring
To make the finding primes project easier, we are assuming the existence of a factoring oracle which, when given any integer as input, returns the factors of that integer as output in O(1) time (though one would need O(k) time just to input a k-digit number).
It is not known whether factoring can be achieved in polynomial time for classical computers (for quantum computers, one can use Shor's algorithm). If it can, then a factoring oracle can be provided essentially "for free".
On the other hand, there are algorithms that are suspected to run in subexponential time [math]\displaystyle{ \exp(o(k)) }[/math], such as the Quadratic sieve or Number field sieve. The former is deterministic. Thus, it is not unreasonable to assume that deterministic subexponential factoring algorithms exist, in which case a factoring oracle is essentially "free" for the weak version of the problem.
The provably fastest deterministic algorithm known for factoring an integer n has run time about [math]\displaystyle{ n^{1/4} }[/math], due to Pollard and Strassen.
If factoring was hard instead of easy, then algorithms such as RSA could in principle be used for pseudorandom number generation; however, RSA requires one to have large primes in hand in the first place, which seems to render this idea circular.
- C. Pomerance, Smooth numbers and the quadratic sieve, Algorithmic Number Theory, MSRI Publications, 44 (2008)
- Wikipedia entry on integer factorisation
