Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers

up vote 10 down vote accepted

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.

share|improve this answer
    
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. –  Dan Brumleve Jul 24 '11 at 1:23
add comment

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

share|improve this answer
    
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 en.wikipedia.org/wiki/… 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? –  Dan Brumleve Jul 23 '11 at 21:17
    
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? –  Dan Brumleve Jul 23 '11 at 21:40
    
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. –  Hans Engler Jul 23 '11 at 22:11
    
Hans, I'm still not understanding why one iteration is sufficient. 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? –  Dan Brumleve Jul 24 '11 at 2:23
    
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. –  Hans Engler Jul 24 '11 at 12:05
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
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. –  chazisop Jul 25 '11 at 13:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.