3
$\begingroup$

My task is to factorize $n$ knowing it has two factors and $\varphi(n)$. How can I do it?

Thanks for any advice.

$\endgroup$
1
4
$\begingroup$

Assuming you mean $n=pq$ for distinct primes $p,q$, you know the values $pq$ and $(p-1)(q-1) = pq - p - q + 1,$ so you know $p+q$ as well. That is enough.

$\endgroup$
5
$\begingroup$

Let $n = pq$ for two distinct primes $p$ and $q$, and assume $n$ and $\phi(n)$ are known. Since $\phi(n) = (p - 1)(q - 1) = pq - p - q + 1$, we can compute $p + q = n - \phi(n) + 1$. So we know $pq$ and $p + q$. Now consider the following quadratic $f$: $$ \begin{align} f(x) &= x^2 - (n - \phi(n) + 1) x + n \\ &= x^2 - (p + q) x + pq \\ &= (x - p)(x - q). \end{align}$$ All coefficients of $f$ are known in the first line, so we can compute its roots, which are exactly $p$ and $q$, as shown in the last line.

$\endgroup$
3
$\begingroup$

It is very easy to prove that $\rm n$ can be factored in polynomial time given any multiple of $\rm \varphi(n),\:$ e.g. see Gary Miller: Riemann's hypothesis and tests for primality, 1976.

Note $\ $ This fact was well-known to the discoverers of RSA. Indeed they mention it explicitly in section IX of the original 1978 paper on RSA, which is quite readable.

$\endgroup$
0
$\begingroup$

Well, we have it that:

$x^2 - (p+q)x + pq$

This is in the form of a quadratic equation. Notice the similarities to the standard quadratic equation that we learned about in high school:

$ax^2 + bx + c \; = \; 0$

Again, like we learned in high school, you can solve for $x$ by using the quadratic formula:

$x \; = \; \frac{-b\pm\sqrt{b^2-4ac}}{2a}$

Where in this case:

$a \; = \; 1$

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

$c \; = \; p q \; = \; n$

Ergo, we have:

$p \; = \; \frac{(p+q) + \sqrt{(p+q)^2 - 4pq}}{2}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.