From Polymath Wiki
Revision as of 17:24, 8 August 2009 by Teorth (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.

  1. C. Pomerance, Smooth numbers and the quadratic sieve, Algorithmic Number Theory, MSRI Publications, 44 (2008)
  2. Wikipedia entry on integer factorisation