41
$\begingroup$

This is a cross-post from math.stackexchange.

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 $n = pq$ and $p,q$ are primes. That is, given $n$ find primes $p,q$ or NONE if there is no such factorization.

Clearly, RSA is an instance of FACT. Is FACT harder than RSA? Given an oracle that solves RSA in polynomial time, could it be used to solve FACT in polynomial time?

(A pointer to literature is much appreciated.)

Edit 1: Added the restriction on computational power to be polynomial time.

Edit 2: As pointed out in the answer by Dan Brumleve, there are papers arguing for and against RSA being harder (or easier) than FACT. I found the following papers so far:

D. Boneh and R. Venkatesan. Breaking RSA may be easier than factoring. EUROCRYPT 1998. http://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf

D. Brown: Breaking RSA may be as difficult as factoring. Cryptology ePrint Archive, Report 205/380 (2006) http://eprint.iacr.org/2005/380.pdf

G. Leander and A. Rupp. On the Equivalence of RSA and Factoring regarding Generic Ring Algorithms. ASIACRYPT 2006. http://www.iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

D. Aggarwal and U. Maurer. Breaking RSA Generically Is Equivalent to Factoring. EUROCRYPT 2009. http://eprint.iacr.org/2008/260.pdf

I have to go through them and find a conclusion. Is someone aware of these results, who can provide a summary?

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ if i remember correctly, then computing $\phi(n)$ or finding out d is equivalent to factoring but as such there might be some way that RSA is weaker than factoring. In short solving RSA may not imply solving the factoring problem. No formal proofs known for them being equivalent.(as far as i know) $\endgroup$
    – singhsumit
    May 24, 2011 at 8:28
  • 1
    $\begingroup$ Mohammad, why is FACT not reducible to RSA? $\endgroup$
    – Dan Brumleve
    May 24, 2011 at 10:13
  • 6
    $\begingroup$ How do you know that is what it amounts to? $\endgroup$
    – Dan Brumleve
    May 24, 2011 at 10:51
  • 7
    $\begingroup$ If there is no poly-time reduction between the two stated problems, then it's going to be hard to show this, right? To prove no poly-time reduction can exist requires that we prove $P\neq NP$. $\endgroup$
    – Fixee
    May 25, 2011 at 3:39
  • 2
    $\begingroup$ You've misunderstood what those papers are proving. By "RSA problem", they mean the problem of computing a modular $e$th root (mod $n$), and relating that to the difficulty of factoring $n$. In both cases $n$ is a RSA number, i.e., $n=pq$. So what you've defined as "RSA" is different from the standard meaning of the phrase "RSA problem", and I don't think those papers you cite are actually addressing the question you asked about. $\endgroup$
    – D.W.
    Nov 20, 2014 at 2:27

3 Answers 3

Reset to default
12
$\begingroup$

I found this paper entitled Breaking RSA May Be Easier Than Factoring. They argue that computing $e$th roots modulo $n=pq$ might be easier than factoring $n=pq$.

However, they don't address the question you asked about: they don't consider whether or not factoring integers of the form $n=pq$ might be easier than factoring arbitrary integers. As a result, this answer is pretty much irrelevant to your particular question.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks! I found several other papers with related titles, cross-references. I will post links below. (Edit: links below are ugly. I can't get proper formatting in comments.) $\endgroup$
    – user17
    May 28, 2011 at 3:27
  • 2
    $\begingroup$ D. Boneh and R. Venkatesan. Breaking RSA may be easier than factoring. EUROCRYPT 1998. crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf D. Brown: Breaking RSA may be as difficult as factoring. Cryptology ePrint Archive, Report 205/380 (2006) eprint.iacr.org/2005/380.pdf D. Aggarwal and U. Maurer. Breaking RSA Generically Is Equivalent to Factoring. EUROCRYPT 2009. eprint.iacr.org/2008/260.pdf G. Leander and A. Rupp. On the Equivalence of RSA and Factoring regarding Generic Ring Algorithms. ASIACRYPT 2006. iacr.org/archive/asiacrypt2006/42840239/42840239.pdf $\endgroup$
    – user17
    May 28, 2011 at 3:27
  • 1
    $\begingroup$ I read the abstracts, and the Aggarwal and Maurer paper seems to be about a slightly differerent problem (factoring a semiprime vs. computing the phi function?) The others say explicitly that the problem is open. I suppose it still is unless there is a result more recent than 2006? $\endgroup$
    – Dan Brumleve
    May 28, 2011 at 3:45
  • 1
    $\begingroup$ It's probably worth mentioning that the Boneh and Venkatesan paper is about the hardness of factoring semiprimes vs. the hardness of breaking RSA. What the question calls "RSA" is in fact the problem of factoring semiprimes, which may be harder than breaking RSA (which is what the Boneh-Venkatesan paper suggests) $\endgroup$
    – Sasho Nikolov
    Nov 1, 2013 at 17:26
  • 5
    $\begingroup$ This answer is not correct. You've misunderstood what those papers are proving. By "RSA problem", they mean the problem of computing a modular $e$th root (mod $n$), and relating that to the difficulty of factoring $n$. In both cases $n$ is a RSA number, i.e., $n=pq$. So the papers you cite is not actually addressing the question you asked about. The confusion here comes because the question's "RSA problem" is not the same as what those papers refer to as "the RSA problem". $\endgroup$
    – D.W.
    Nov 20, 2014 at 2:29
21
$\begingroup$

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 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 General Number Field Sieve, the fastest known classical factoring algorithm, and Shor's algorithm, the polynomial time quantum factoring algorithm, work equally well for non-semiprimes. In general, it seems much more important that the factors by 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 promise problem, and any way of removing the promise of the input being semiprime is to either

  1. introduce an indexing on the semiprimes (which in itself I suspect is as hard as factoring them), or
  2. 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.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Joe, I think it would be reasonable to assume that factoring is not in $P$ (and therefore $P \neq NP$) for this question (and then the answer would not imply a break-through complexity result as you stated in the last paragraph). $\endgroup$
    – Kaveh
    May 26, 2011 at 4:06
  • 1
    $\begingroup$ @Kaveh: I don't think that is enough. We want to show whether or not $P^{RSA} = P^{FACT}$. This question has different answers depending on the assuptions you make. Imagine that in reality P=NP (actually we only need FACT in P, but I wanted to emphasise the connection to P v NP), but we make the assumption that FACT is not in P. Then it is possible to prove that $P^{RSA} = P^{FACT}$ by exhibiting a polynomial time algorithm for the reduction, or to prove that $P^{RSA} \neq P^{FACT}$ by exhibiting a polynomial time algorithm for RSA and using the assumption about the complexity of FACT. $\endgroup$
    – Joe Fitzsimons
    May 26, 2011 at 13:19
  • 1
    $\begingroup$ I interpreted the question as "$FACT \in P^{RSA}?$". Then if $FACT \in P$ then the answer is trivially yes. So we can assume that $FACT \notin P$, and if we are making a false assumption, then of course we can derive anything. :) $\endgroup$
    – Kaveh
    May 27, 2011 at 3:59
  • $\begingroup$ @Kaveh: I believe the two statements of the problem are equivalent in this case. My point is that that it is only potentially possible to prove that $FACT \in P^{RSA}$ without first deciding P vs NP, and not the converse. $\endgroup$
    – Joe Fitzsimons
    May 28, 2011 at 0:10
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The factorization algorithm would have to run in polynomial time, however. So really you're saying "if you had a poly-time factorization algorithm you'd have solved an unknown problem". Because one can use the naive factorization algorithm to find out if a number is a semiprime or not. $\endgroup$
    – Elliot Gorokhovsky
    Mar 29, 2015 at 19:52