Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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!
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.$$
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}$.
$p = \lfloor \sqrt{n} \rfloor$ and $q = p + 2$.
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.
