# 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]\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]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