# Factoring a large integer where the factors are prime

Suppose I know the value of $n$ (where $n = pq$), and I also know $k = p-q$. How can I efficiently factor $n$?

Note that I don't know $p$ or $q$.

EDIT: Thank you for your answers. I understand that I could use basic algebra but would it be efficient to use that if $n$ was large? For example, if $n = 59305397$?

• $\rm n=pq=(q+k)q$ yields $\rm q^2+kq-n=0$, which is a quadratic equation.
– anon
Mar 5, 2013 at 4:33
• Are you computing by hand? Or by computer? Do you really mean numbers as small as 8 digits?
– user14972
Mar 5, 2013 at 6:04
• I am am computing using a standard scientific calculator, not a computer (or writing a program or anything of that sort). Mar 5, 2013 at 6:11

You have a system of two equations in two unknowns; you can appeal to high school algebra!

We assume that $p$ and $q$ are huge.

Note that $(p+q)^2=(p-q)^2+4pq$. We know $p-q$ and $pq$, so can compute $(p+q)^2$ cheaply. Now we can compute $p+q$ cheaply, by an adaptation of Newton's Method.

We now know $p-q$ and $p+q$. Calculate $\frac{1}{2}\left((p-q)+(p+q)\right)$.

Hint $\$ Since we have been given both the $\rm\color{#C00}{sum}$ and $\rm\color{#0A0}{product}$ of $\rm\,p\,$ and $\rm\,-q,\,$ we know the coefficients of the quadratic polynomial having $\rm\,p\,$ and $\rm\,-q\,$ as roots, namely

$$\rm (x-p)(x+q)\, =\, x^2 - (\color{#C00}{p\!-\!q})\, x \color{#0A0}{-pq}\ =\ x^2 - k\, x -n$$

Therefore, solving $\rm\ x^2 - k\, x -n\, =\, 0\$ yields the roots $\rm\:p\:$ and $\rm\:-q.$

Note that $p=k+q$, so $n=q(k+q)$ or $q^2+kq-n=0$. This is a quadratic in $q$.