How to determine in polynomial time if a number is a product of two consecutive or close primes?

Question

How to determine in polynomial time if a number is a product of two consecutive primes?

All I can figure out is that if Cramér's conjecture is true, then we can use the AKS primality test to find $p_i < \sqrt n < p_{i+1}$, then check if $p_i * p_{i+1} = n$. Is there some way to determine if a number is of this form in polynomial time that doesn't rely on any unproven assumptions?

Also, given that a number is of this form, what is the quickest way to factor it? How fast will modern general-purpose factoring algorithms such as the quadratic sieve factor a product of consecutive primes?

Answer 1

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.

Answer 2

Let $x =\lceil \sqrt{n} \rceil$. Check if $x^2 - n$ is a square. If $x^2 - n = y^2$, check if $x+y$ and $x-y$ are primes, using a suitable primality test. If they are, check if there are any primes between $x-y$ and $x+y$.

This also depends on Cramer's conjecture, of course.

Edit (7/24): Let $n = pq = (x+k)(x-k)$ where $p,> q$. Fermat's method is to compute $\sqrt{n+k^2}$ for many $k$ until one finds an integer. Then set $x = \sqrt{n+k^2}$ and $p = x+k, \, q = x-k$.

To see how this can be sped up, use the Taylor approximation $$ \sqrt{n+k^2} = \sqrt{n} \sqrt{1 + \frac{k^2}{n}} \approx \sqrt{n} \left( 1+ \frac{k^2}{2n}\right) = \sqrt{n} + \frac{k^2}{2\sqrt{n}} $$ to see that if $\frac{k^4}{n}$ is small, then $0 < \sqrt{n+k^2} - \sqrt{n} < 1$ or so and simply rounding up from $\sqrt{n}$ will produce $k$ immediately, in one step. That's the origin of the condition $k \le c n^{1/4}$ that appears elsewhere in the answers. This can work only when we are looking for a factorization into two close factors. If it works for a given odd $n$, it will produce a factorization into two factors whose difference is minimal and less that $2cn^{1/4}$, and it will only work for such $n$.

Answer 3

The fastest factorization method is Number Field Sieve (NFS). To factor a 1024 bit integer $N$, it takes around $2^{86}$ many steps.

Answer 4

well it all depends on the gap between the two consecutive primes. For twin primes, it's really easy but for two primes with gap of 10^10,000 I suppose it is much harder.