

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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.

share|cite|improve this question
Try asking it on cstheory. Someone might come up with an oracle result. – Yuval Filmus May 24 '11 at 1:25
@Yuval Filmus: Good idea! – user2468 May 24 '11 at 1:32
The answer is trivially "yes" since you didn't limit computational power in any way, and factorization is certainly decidable. – Fixee May 24 '11 at 5:49
@Fixee: Polynomial time. I edited the question. – user2468 May 24 '11 at 6:16
up vote 1 down vote accepted

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.

share|cite|improve this answer
I don't find your first reason convincing. There is no reason k=1 (or k-1=1) can't be a special case. (And we already know it is, in some sense.) And I don't understand the second reason — what does factoring pq+k have to do with factoring pq, or this question? – ShreevatsaR May 25 '11 at 3:31
ShreevatsaR, I think you already understand the first part, in some sense. The second part is just that there are no semiprimes anywhere near the number we are trying to factor, so even if there was an algorithm to factor numbers near semiprimes it wouldn't help in the general case. I am not convinced either! – Dan Brumleve May 25 '11 at 8:37

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.

share|cite|improve this answer
I like the prime testing, it made me laugh! – Eric Naslund May 24 '11 at 0:44

Your Answer

