10
$\begingroup$

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?

4 Answers 4

10

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.

  • 0
    It seems like the first question then reduces to deciding whether two given primes are consecutive, allowing that super-polynomial (in log(n)) prime gaps may exist.2011-07-24
3

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

  • 0
    Does the first part (finding p=x-y and q=x+y with p*q=n) also depend on Cramér's conjecture? The bound given at http://en.wikipedia.org/wiki/Cram%C3%A9r's_conjecture#Proven_results_on_prime_gaps permits prime gaps larger than sqrt(n); am I right in thinking that this method of finding the factors may fail if the prime gap is too large?2011-07-23
  • 0
    Now I see that the upper bound is actually around sqrt(p) ~ n^(1/4), not sqrt(n), so that is that good enough to find p and q, given RH at least; but maybe all that's needed here is Bertrand's postulate? Anyway, how exactly do you prove that this method will find the factors of n, given that n is a product of two consecutive primes?2011-07-23
  • 0
    See the answer by Bill Dubuque below. The answer I gave is essentially Fermat's method (as I remembered it from an undergrad crypto class I taught last year). This is why in RSA you are supposed to choose two primes which are different orders of magnitude.2011-07-23
  • 0
    Hans, I'm still not understanding why one iteration is sufficient. http://en.wikipedia.org/wiki/Fermat's_factorization_method says that it will work for |p-sqrt(n)| < (4*n)^(1/4). Is p guaranteed to be in that range if p and q are consecutive? Does it depend on RH?2011-07-24
  • 0
    See my edited answer which hopefully explains things a bit better. All this is not a proof, of course. Whether this work in polynomial time depends indeed on distribution properties for gaps between consecutive primes.2011-07-24
-3

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

  • 0
    Yes but this algorithm is for general use, while this question addresses a specific factoring problem. Special conditions can make the difference between NP-completeness and membership P, or even computability and uncomputability.2011-07-25
-3

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.