Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thanks for any advice.

share|improve this question
    
The expression of $\varphi(n)$ for this specific case could help... –  Raymond Manzoni Oct 27 '12 at 15:52

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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