# Factoring

On the other hand, there are algorithms that are suspected to run in subexponential time $\exp(o(k))$, 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 $n^{1/4}$, due to Pollard and Strassen.