Exercise 2.5.2 (The phi number must remain secret)

Question

Suppose that $m=pq$, and $\phi = (p-1)(q-1)$ where $p$ and $q$ are real numbers. Find a formula for $p$ and $a$, in terms of $m$ and $\phi$. Supposing that $m = 39,247,771$ is the product of two distinct primes, deduce the factors of $m$ from the information that $\phi(m) = 39,233,944$.

Richard Ganaye · Accepted Answer

\begin{proof} From $m = p q$, and $\phi = (p-1)(q-1) = pq - p -q +1$, we deduce
\begin{align*}
p + q &= m - \phi + 1,\
pq &= m.
\end{align*}
Therefore $p$ and $q$ are the roots of the polynomial
$$f(x) = x^2 - (m-\phi + 1) x + m.$$
The discriminant $\Delta$ of $f$ is
$$\Delta = (m-\phi + 1)^2 - 4m,$$
and $\Delta \geq 0$ since the roots of $f$ are the real numbers $p,q$.

Therefore
$$\{p,q\} = \left\{\frac{m-\phi+1 + \sqrt{(m-\phi+1)^2 - 4m}}{2},\frac{m-\phi+1 - \sqrt{(m-\phi+1)^2 - 4m}}{2}ight\}.$$

\bigskip
If $m = 39,247,771$ and $\phi = 39,233,944$,then
$$\{p,q\} = \{9839, 3989\}.$$

Check: $9,839 	imes 3,989 = 39,247,771$.
\end{proof}

Exercise 2.5.2 (The phi number must remain secret)

Answers

Comments

Exercise 2.5.2 (The phi number must remain secret)

Answers

Comments

Add answer