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.
 A: 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.  
A: 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.
A: In the case of twin primes $p$ and $q = p+2$, we may express $n = p(p+2)$ as a difference of squares $a^2 - b^2 = (a-b)(a+b)$:
\begin{align}
  n &= p \cdot (p + 2) \\
    &= ((p + 1) - 1) \cdot ((p+1) + 1) \\
    &= (p+1)^2 - 1^2
\end{align}
Solving for $p$, we obtain:
$$p = \sqrt{n+1} - 1$$
And of course, as a twin prime, $q$ is:
$$q = \sqrt{n+1} + 1$$
That is, we are merely limited by the speed of taking a square root. (Which is reasonably fast.)
