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