5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – François G. Dorais
    Commented May 25, 2011 at 3:37
  • $\begingroup$ @François: Well, fair enough. $\endgroup$
    – M.S.
    Commented May 25, 2011 at 3:44
  • 3
    $\begingroup$ 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...) $\endgroup$
    – KotelKanim
    Commented May 25, 2011 at 7:05
  • $\begingroup$ @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). $\endgroup$
    – M.S.
    Commented May 25, 2011 at 16:29

0

Reset to default