# Relation between factors and their sum on RSA

In RSA and other crypto based on prime factors. If I would know the sum of $$p+q$$, would it reveal any more information than just knowing $$p\cdot q$$?

Edit: I do not know either $$p$$ or $$q$$. The question relates to the fact that if I know the sum and the multiplication, can I find the factors $$p$$ and $$q$$ faster compared to when I don't know the sum?

• I'm not entirely sure, are you asking about the case where you just know $p+q$ (but not $p\cdot q$) or where you know $p+q$ and $p\cdot q$? – SEJPM Jan 3 at 12:41
• I guess you are asking the case where you knoe both $m=pq$ and $a=p+q$. In this case, you can find $p$ and $q$ by solving the quadratic equation $x^2-ax+m=0$. – Hhan Jan 3 at 12:48
• You can also directly compute $d = e^{-1} \pmod{n-(p+q)+1)}$. – Fractalice Jan 3 at 12:53
• yes I know p+q and p*q (but I don't know P or Q. Given that they are big int (>1024 bit) does knowing the sum make it easier to find P&Q? – ovanwijk Jan 3 at 13:14
• What is capital $P$ and $Q$? – kelalaka Jan 3 at 13:14

Let $$n = p \cdot q$$ be product of distinct primes $$p$$ and $$q$$, of arbitrary size as in the RSA setup.

The RSA public key $$(n,e)$$ contains both the modulus and the public exponent, so we assume both are known.

Let $$b = p +q$$. If $$b$$ is also known, then we can form a quadratic equation as

$$f(x) = x^2 - b x + n \label{1}\tag{1}$$ by using the following identity:

$$(x-p)(x-q) = x^2 - (p+q) x + (p\cdot q).$$

The solution of the quadratic equation (\ref{1}) is that $$p$$ and $$q$$ and can be found by the second-degree formulas using this equation:

$$p,q = \frac{ b \pm \Delta}{2}$$ where the discriminant $$\Delta = \sqrt{b^2 - 4n}.$$

It is also possible to directly find the private exponent too! Observe that:

$$\varphi(n) = (p-1)(q-1) = pq - p -q +1 = pq - (p +q) +1 = n - b + 1.$$

Since $$e \cdot d \equiv 1 \bmod \varphi(n)$$, you can solve for $$d$$ without computing $$p$$ and $$q$$, though those are also cheap to compute if you would still like to use them.

Example:

Let $$m = 35$$ and $$b = 12$$. We thus need to solve $$x^2 - 12x + 35$$, which gives us:

$$\Delta = \sqrt{12^2 - 4 \cdot 35} = \sqrt{144 - 140} = \sqrt{4} =2.$$

As a result:

$$p = \frac{12 + 2}{2} = 7 \text { and } q = \frac{12 - 2}{2} = 5.$$

• Please see my edit but: does this mean, that revealing the sum will expose $p$ and $q$? – ovanwijk Jan 3 at 13:51
• That is exactly what you need, call their sum $b$ and multiple as $n$ the modulus then it works, – kelalaka Jan 3 at 13:56
• Sorry I might not understand how exactly. Given p=5 and q=7, m=35 and s=12. How do I find 5 & 7 from f(35, 12) (other than brute force)? – ovanwijk Jan 3 at 14:06
• Ok I got it! Thnx! – ovanwijk Jan 3 at 14:11
• @ovanwijk added the example. – kelalaka Jan 3 at 14:21