2
$\begingroup$

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.

  • 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.2011-10-09

3 Answers 3

6

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.

5

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.

0

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