Is the factorization problem harder than RSA factorization ($n = pq$)?

Question

Let $n \in \mathbb{N}$ be a composite number, and $n = pq$ where $p,q$ are distinct primes. Let $F : \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$ (*) be an algorithm which takes as an input $x \in \mathbb{N}$ and returns two primes $u, v$ such that $x = uv,$ or returns FAIL if there is no such factorization ($F$ uses, say, an oracle). That is, $F$ solves the RSA factorization problem. Note that whenever a prime factorization $x = uv$ exists for $x,$ $F$ is guaranteed to find it.

Can $F$ be used to solve the prime factorization problem in general? (i.e. given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $e_i \in \mathbb{N},$ such that $n = \prod_{i=0}^{k} p_{i}^{e_i}$)

If yes, how? A rephrased question would be: is the factorization problem harder than factoring $n = pq$?

(*) abuse of the function type notation. More appropriately $F : \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N} \bigcup \mbox{FAIL} $

---

Edit 1: $F$ can determine $p,q,$ or FAIL in polynomial time. The general factoring algorithm is required to be polynomial time.

Edit 2: The question is now cross-posted on cstheory.SE.

Answer 1

I don't see any way to use a two-prime oracle to do general factorization. I note that it would solve the primality-testing problem - just feed $2n$ to the oracle, and if you don't get FAIL, then you know $n$ is prime.

Answer 2

Two vague reasons I think the answer must be "no":

If there were any inductive reason that we could factor a number with k prime factors in polynomial time given the ability to factor a number with k-1 prime factors in polynomial time, then the AKS primality test has already provided a base case. So semiprime factorization would have to be considered as a new base case for anything like this to work.

The expected number of prime factors is on the order of log(log(n)) which is unbounded although it is very slow. So for sufficiently large n there is unlikely to be a prime or a semiprime which differs from it by less than any given constant. For large enough k, it seems like the ability to factor p*q won't help us factor (p*q)+k, similarly to how the ability to prove p is prime won't help us factor p+k.

Interesting question. I hope someone more knowledgeable than me can answer this with a reference and a decisive statement.

EDIT: I found this paper entitled Breaking RSA May Be Easier Than Factoring which argues for a "no" answer and states the problem is open.