2
$\begingroup$

Say $n = pq$ where $p$ and $q$ is a twin prime pair $|p-q|=2 $. Explain how this information can help us factor n quickly. Use this method to factor $52012943$.

I am learning about modulus and trying to study for my upcoming exam and came across this question. I don't even know how to begin. Thanks for any and all help!

$\endgroup$
  • $\begingroup$ It is perhaps worth pointing out that an extension of the very basic principle at work here has been used to factor numbers that are products of two primes of roughly the same size, even when those primes aren't twin; see en.wikipedia.org/wiki/Fermat%27s_factorization_method $\endgroup$ – Steven Stadnicki Mar 19 '13 at 22:29
1
$\begingroup$

Call the primes $p$ and $q$. Without loss of generality we may assume that $p\gt q$.

We have $p-q=2$ and we know $pq$. Note that $$(p+q)^2=(p-q)^2+4pq$$ for any numbers $p$ and $q$ (just expand the squares).

We know the stuff on the right-hand side. So we can quickly calculate $p+q$. Since we know that $p-q=2$, finding $p$ and $q$ is very cheap.

Essentially the same idea works if we know that $p-q=a$, where $a$ is given.

The calculation: By what is written above, $(p+q)^2=(p-q)^2+4pq=4+4pq$. To find $(p+q)^2$, multiply your given $pq$ by $4$, and add $4$. But since $4+4pq=(p+q)^2$, we have $$\frac{p+q}{2}=\sqrt{1+pq}.$$ So just add $1$ to your given big number, and take the square root. You will have $\frac{p+q}{2}$. To extract $p$, note that $\frac{p-q}{2}=1$. Adding, we get $p$. We get the simple formula $$p=\sqrt{1+pq}+1.$$

$\endgroup$
  • $\begingroup$ I made a mistake in my question, it should be |p-q|=2 $\endgroup$ – Michael Mar 19 '13 at 22:01
  • $\begingroup$ Doesn't make any real difference to the calculations. You can name the primes $p$ and $q$, with the understanding that $p\gt q$. $\endgroup$ – André Nicolas Mar 19 '13 at 22:08
  • $\begingroup$ I'm sorry, I still cannot see how this affects the speed of how to factor a number such as 52012943. $\endgroup$ – Michael Mar 19 '13 at 22:28
  • $\begingroup$ Multiply your big number by $4$. Add $4$. Take the square root. By answer above, you now have $p+q$. Add $p-q$, that is, $2$. Now you have $2p$. Divide by $2$. Finished. We can save steps. Don't multiply your big number by $4$. Just add $1$. Take the square root. We get $\frac{p+q}{2}$. Add $\frac{p-q}{2}$, that is, $1$. We have $p$. (I will add to the post.) $\endgroup$ – André Nicolas Mar 19 '13 at 22:37
  • $\begingroup$ Again, I am very grateful for your help. I am starting to understand CRT and modulus more mainly thanks to you. Cheers :) $\endgroup$ – Michael Mar 19 '13 at 23:00
2
$\begingroup$

Let $r$ be the average of the primes: $$r = \frac{p+q}{2}$$

Then, $n = (r-1)(r+1) = r^2 - 1$. In other words, $r^2 = n + 1$.

It follows that $r = \sqrt{n + 1}$, and given how we defined $r$, the prime factors $p$ and $q$ are trivial to find.

Edit: Note that what Dan Brumleve mentions follows from this (assuming $p$ is the smaller prime): $n + 1$ is a perfect square, so $$\lfloor \sqrt{n+1} \rfloor = \sqrt{n+1} = r$$ and $$\lfloor \sqrt{n} \rfloor = r - 1 = p$$

The method I suggested also works for integers $n$ with prime factors $p, q$ whose difference is an arbitrary positive integer $a$; that is, the method is not limited to twin primes.

In the general case, $r$ is defined like before, but the way it relates to $n$ is a little different (same idea though), namely as follows. $$n = \left(r - \frac{a}{2}\right)\left(r + \frac{a}{2}\right) = r^2 - \frac{a^2}{4}$$ $$r^2 = n + \frac{a^2}{4}$$ $$r = \sqrt{n + \frac{a^2}{4}}$$ Assuming $p$ is the smaller prime factor, we have $p = r - \frac{a}{2}$ and $q = r + \frac{a}{2}$.

$\endgroup$
0
$\begingroup$

$p = \lfloor \sqrt{n} \rfloor$ and $q = p + 2$.

$\endgroup$
0
$\begingroup$

More generally, one can tweak Fermat's factorization method (by difference of squares) to quickly factor any $\rm\ n = p\:q\ $ that is a product of two "close" primes, namely if $\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, and their slides How to compute RSA keys? The Art of RSA: Past, Present, Future.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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