1
$\begingroup$

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

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

4 Answers 4

Reset to default
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .