Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So in RSA, there is a modulus n which is the product of two primes. My question is regarding when p and q are consecutive primes, what would the time complexity be? So, n=pq and p and q are consecutive primes is the only information to work off of. Also would Fermat's factorization be an efficient way to factor such an n?

edit: I'n not actually trying to factor n or find p and q. I just want to know if Fermat's factorization method would be efficient given this information.

share|improve this question
2  
How is it hard to factor $n$ when $n = pq$ and $p$ and $q$ are consecutive primes? Just start at $a = \sqrt{n}$ and the first primes above and below $a$ are $p$ and $q$. –  TMM Oct 9 '11 at 15:16
2  
If you know they are consecutive, they must be very close to $\sqrt{n}$. A practical approach would be to start there and use trial division for each number that passes some very simple prime test (perhaps just $\neq 0 \pmod {2,3,5,7}$, for example). The bound for this may be hard to assess, but I'll bet it works well. –  Ross Millikan Oct 9 '11 at 15:17

2 Answers 2

Yes, variations on Fermat's method work more generally. Namely, if $\rm\ n = p\:q\ $ is a product of two "close" primes, i.e. $\rm\:|p-q| < n^{1/3},\:$ then $\rm\:n\:$ can be factored in polynomial time, see Robert Erra; Christophe Grenier. The Fermat factorization method revisited. 2009. See also their slides How to compute RSA keys? The Art of RSA: Past, Present, Future. See also this prior question.

share|improve this answer

The time complexity is very low.

Assuming $n>6$ so $p$ and $q$ are both odd, let $m=\lceil \sqrt n \rceil$. If $m^2-n$ is a square then candidates for $p$ and $q$ are $m\pm \sqrt{m^2-n}$; they will be factors of $n$ so they must be prime if the question is honest. That is probably enough, but in the unlikely event that it is not then replace $m$ by $m+1$ and repeat, and go on till you get your result, which you will soon.

For example, if $n=137134677353$ then $m=\lceil \sqrt n \rceil = 370317$ and $m^2-n = 3136 = 56^2$ so you look at $370317 \pm 56$, which gives $370261$ and $370373$ which are both prime, and you are done. Note that this prime gap of $112$ is a record for numbers of that size.

As far as I can see, the time complexity comes in taking the square root.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.