Twin prime pair helping to factor large numbers quicker? 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!
 A: 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}$.
A: 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.$$
A: $p = \lfloor \sqrt{n} \rfloor$ and $q = p + 2$.
A: 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.
