Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 30 down vote favorite
7

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 that there are papers arguing for and against RSA 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 can provide a summary?

share|improve this question
1  
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) – singhsumit May 24 '11 at 8:28
1  
Mohammad, why is FACT not reducible to RSA? – Dan Brumleve May 24 '11 at 10:13
1  
Maybe I am misunderstanding something basic. How to show that the existence of an algorithm to factor a semiprime in polynomial time doesn't imply the existence of an algorithm to factor a number with three prime factors in polynomial time? – Dan Brumleve May 24 '11 at 10:28
6  
How do you know that is what it amounts to? – Dan Brumleve May 24 '11 at 10:51
7  
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$. – Fixee May 25 '11 at 3:39
show 6 more comments

3 Answers

up vote 11 down vote accepted

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

share|improve this answer
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.) – user17 May 28 '11 at 3:27
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 – user17 May 28 '11 at 3:27
1  
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? – Dan Brumleve May 28 '11 at 3:45
My stated interpretation of the Aggarwal and Maurer paper is certainly incorrect (if we can factor the modulus then obviously we know its phi value). But I'm still not sure exactly what it is claiming. – Dan Brumleve May 28 '11 at 4:21
up vote 12 down vote

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.

share|improve this answer
2  
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). – Kaveh♦ May 26 '11 at 4:06
@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. – Joe Fitzsimons May 26 '11 at 13:19
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. :) – Kaveh♦ May 27 '11 at 3:59
@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. – Joe Fitzsimons May 28 '11 at 0:10
up vote -4 down vote

Wouldn't the following be a polynomial time algorithm for RSA: Start walking through the integers starting with 2 and stopping at sqrt(n) or even n if we want because it's still O(n) steps. (If we reach sqrt(n), return NONE because n is itself prime.) At each step test for whether i divides n, which takes O((ln(n)^2) time using school division. For the first number found that divides n, we know it is prime, so call it p. And we also have q (which needs to be tested) from the same division. Now if q is prime (same procedure), we return (p, q) and if not we return NONE. Won't that work and run in O(n * (ln(n)^2)) time?

share|improve this answer
3  
"Polynomial time" in this case means that it should run it a polynomial of log(n), not a polynomial of n. – Dan Brumleve May 24 '11 at 18:07
To add to Dan's comment, if $n$ is the input, then $log(n)$ is the size of the input (roughly, the number of bits in $n$). – user17 May 24 '11 at 18:34
ok, tx! now i understand what the difficulty is. – marshallf May 26 '11 at 2:59
5  
To be fair this is a very common mistake. I remember being confused about the same thing when I was first learning about numerical algorithms. – Huck Bennett May 26 '11 at 3:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.