Factoring Phi
Crypto: Factoring Phi
Challenge Description
Φ(N) = 201,100,838,400 N = 201,140,760,239
Find P and Q. Flag format; RISC{P_Q}
Approach
This is really just a math question.
For primes $(P, Q)$,
$$ N=PQ,\qquad\varphi(N)=(P-1)(Q-1) $$ $$ \begin{align*} \varphi(N) &= (P-1)(Q-1) \\ &= PQ-(P+Q)+1\\ &=N-(P+Q)+1. \end{align*} $$Rearrange to get the sum of the primes:
$$ \begin{align*} S &= P + Q\\ &= N - \varphi(N) + 1. \end{align*} $$Once we know $S$ and $N = PQ$, $P$ and $Q$ are the roots of:
$$x^2 - Sx + N = 0.$$As to why this is the case, if a quadratic has roots $P$ and $Q$, then it factors as:
$$ (x-P)(x-Q) = 0 $$And we can easily expand this to
$$ \begin{align*} &x^2-(P+Q)x+PQ=0 \\ \implies &x^2-Sx+N=0 \end{align*} $$We know $S$ and $N$, we just need to solve for $x$, for which we can apply the quadratic formula:
$$x=\frac{S+\sqrt{\Delta}}{2},\quad x=\frac{S-\sqrt{\Delta}}{2}.$$And since those are the roots of the polynomial, those are also our values for P and Q!
Working through the math
First, we find $S$:
$$ \begin{align*} S &= N - \varphi(N) + 1 \\ &= 201{,}140{,}760{,}239 - 201{,}100{,}838{,}400 + 1 \\ &= 39{,}921{,}840. \end{align*} $$Next, compute the discriminant:
$$ \begin{align*} \Delta &= S^2 - 4N \\ &= 39{,}921{,}840^2 - 4\cdot 201{,}140{,}760{,}239 \\ &= 1{,}592{,}948{,}745{,}944{,}644, \\ \sqrt{\Delta} &= 39{,}911{,}762. \end{align*} $$Now recover the primes:
$$ \begin{align*} P &= \frac{S+\sqrt{\Delta}}{2} = \frac{39{,}921{,}840 + 39{,}911{,}762}{2} = 39{,}916{,}801, \\ Q &= \frac{S-\sqrt{\Delta}}{2} = \frac{39{,}921{,}840 - 39{,}911{,}762}{2} = 5{,}039. \end{align*} $$(Fun side note: $39{,}916{,}801 = 11!+1$, and $5{,}039 = 7!-1$.)
Verification
$$ \begin{align*} P\cdot Q &= 39{,}916{,}801 \times 5{,}039 = 201{,}140{,}760{,}239 = N, \\ (P-1)(Q-1) &= 39{,}916{,}800 \times 5{,}038 = 201{,}100{,}838{,}400 = \varphi(N). \end{align*} $$Flag
RISC{39916801_5039}