# Factoring n, where n=pq and p and q are consecutive primes

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.

-
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
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

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.

-

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.

-