knowledge of n and phi(n) allows factoring of n

**mathisthebestpuzzle** · February 17th 2009, 10:00 AM

How would one factor a product of two primes (n), if they know both n and phi(n)?

**o_O** · February 17th 2009, 10:11 AM

Let $n = p_1p_2 \ \Leftrightarrow \ p_2 = \frac{n}{p_1} \qquad {\color{red}\star}$ .

Then: $\varphi (n) = \varphi (p_1p_2) = \varphi(p_1)\varphi(p_2) = (p_1 - 1)(p_2 - 1)$

So we have: $\varphi (n) = (p_1 - 1) (\frac{n}{p_1}-1)$ by ${\color{red}\star}$

All that we have to do now is solve for $p_1$ .

Thread: knowledge of n and phi(n) allows factoring of n

LinkBack

Thread Tools

Display

knowledge of n and phi(n) allows factoring of n

Similar Math Help Forum Discussions

I need some background knowledge on linear algebra?

Flawed Knowledge of Reduction Formulas

integrating by assumed knowledge

knowledge q.

Search Tags