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