Is the integer factorization problem harder than RSA factorization: $n = pq$?

As far as I can see, an efficient algorithm for factoring semiprimes (RSA) does not automatically translate into an efficient algorithm for factoring general integers (FACT). However, in practice, semiprimes are the hardest integers to factor. One reason for this is that the maximum size of the smallest prime is dependent on the number of factors. For an integer $N$ with $f$ prime factors, the maximum size of the smallest prime factor is $\lfloor N^\frac{1}{f} \rfloor$, and so (via the http://en.wikipedia.org/wiki/Prime_number_theorem) there are approximately $\frac{f N^\frac{1}{f}}{\log(N)}$ possibilities for this. Thus increasing $f$ decreases the number of possibilities for the smallest prime factor. Any algorithm which works be successively reducing this space of probabilities will then work best for large $f$ and worst for $f=2$. This is borne out in practice, as many classical factoring algorithms are much faster when the number being factored has more than 2 prime factors. Further the http://en.wikipedia.org/wiki/General_number_field_sieve, the fastest known classical factoring algorithm, and http://en.wikipedia.org/wiki/Shor%27s_algorithm, the polynomial time quantum factoring algorithm, work equally well for non-semiprimes. In general, it seems much more important that the factors by http://en.wikipedia.org/wiki/Coprime than that they be prime. I think part of the reason for this is the decision version of factoring co-primes is most naturally described as a http://en.wikipedia.org/wiki/Promise_problem, and any way of removing the promise of the input being semiprime is to either introduce an indexing on the semiprimes (which in itself I suspect is as hard as factoring them), or by generalising the problem to include non-semiprimes. It seems likely that in the latter case the most efficient algorithm would solve FACT as well as RSA, though I have no proof of this. However, a proof is a little to much to ask for, since given an oracle for RSA proving that this cannot efficiently solve FACT amounts to proving that $P\neq NP$. Lastly it is worth pointing out that RSA (the cryptosystem, not the factoring problem you defined above) trivially generalizes beyond semi-primes.

Not quite a complete answer, but seems to be an improvement: The research papers cited above compare the problem of computing eth roots mod N, i.e. doing the private key operation in the RSA cryptosystem, to the problem of factoring, i.e. finding the private key, in both cases, using only the public key. In this case, the factoring problem is not the general case, but the semiprime case. In other words, they are considering a different question. I believe that it is known, see Knuth's AoCP, that most numbers N have prime factorizations whose bit lengths compare in bit length to that of N, on average something like 1/2, 1/4, 1/8, ..., or perhaps even falling off more sharply, as in 2/3, 2/9, 2/27, ... but maybe flattening out. So, for general random N of size small enough that the smaller factors can be expected to be found quickly by trial division or Lenstra's ECM, then what remains may be a semiprime, though an unbalanced one. This is a kind of reduction, but it depensds heavily on the distribution of factors, and it is a slow reduction, in that it invokes other factorization algorithms. Also, there is no known test for determining if a number is semiprime or not. This only means that if one just applied a semiprime factorization algorithm to a general number, and it always failed, then one has solved an unknown problem.

Wouldn't the following be a polynomial time algorithm for RSA: Start walking through the integers starting with 2 and stopping at sqrt(n) or even n if we want because it's still O(n) steps. (If we reach sqrt(n), return NONE because n is itself prime.) At each step test for whether i divides n, which takes O((ln(n)^2) time using school division. For the first number found that divides n, we know it is prime, so call it p. And we also have q (which needs to be tested) from the same division. Now if q is prime (same procedure), we return (p, q) and if not we return NONE. Won't that work and run in O(n * (ln(n)^2)) time?