MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a repost. I could not get a precise answer on math.SE and cstheory.SE

Let FACT denote the integer factoring problem: 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}.$

Let RSA denote the special case of factoring problem where $k=2, e_i=1$ for all $i$. That is, given $n,$ find two primes $p,q,$ such that $n = pq$ or NONE if this factorization does not exist.

Obviously, RSA is an instance of FACT. Is FACT harder than RSA? Given an oracle that solves RSA in polynomial time, could we construct a polynomial time algorithm to solve FACT?

share|cite|improve this question

closed as no longer relevant by François G. Dorais May 25 '11 at 3:35

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

I closed your answer as 'no longer relevant.' The reason is that you didn't wait long enough before cross posting your question. Once you've waited a few days, flag your post for moderator attention and it will be reopened. – François G. Dorais May 25 '11 at 3:37
@François: Well, fair enough. – M.S. May 25 '11 at 3:44
I would very much want the question to be reopen but I don't want to argue about MO policy so I will just wait patiently. meanwhile, to clarify the question, what would the oracle return for an input which is not a pq number? will it return "false" or just run into an infinite loop? the question is whether you can use this oracle for detection of semi-primness as well as for factorization of semi-primes. (I have no idea what the answer is in neither of the cases...) – KotelKanim May 25 '11 at 7:05
@KotelKanim If $n$ is not decomposable into a product $pq$ of two primes, then RSA oracle will terminate (in polytime) with the answer NONE (or 'false' if you wish). – M.S. May 25 '11 at 16:29