We want to factor $n=900$ using that $\varphi(n)=240$, and more generally factor $n$ knowing the Euler totient $\varphi(n)$.
Leaving aside trial division, we can use three techniques
- Taking the Greatest Common Divisor of these two givens, which if $n$ is divisible by a square, and some rare other cases, will reveal a factor of $n$, and (once the GCD itself is factored) will reveal all the factors of $n$, or leave a square-free $n$ to factor (that is $n$ the product of distinct primes).
- A technique applicable to $n$ the product of any number of distinct primes: knowing any (non-zero) multiple $f$ of $\lambda(n)$ (the Carmichael function), including $f=\varphi(n)$ or $f=e\,d-1$ in RSA, allows factoring $n$ with this algorithm .
- A simpler technique applicable to $n$ the product of two distinct primes $p$, $q$: we can find $\sigma=p+q=n-\varphi(n)+1$, then find $p$ and $q$ as the two roots of the quadratic equation $x^2-\sigma\,x+n=0$.
Using the GCD
Recall that if the factorization of $n$ is $n=\prod\left({p_i}^{k_i}\right)$ with distinct primes $p_i$, then $\varphi(n)=\prod\left(\left(p_i-1\right)\,{p_i}^{k_i-1}\right)$. Thus for all $i$ with $k_i>1$, ${p_i}^{k_i-1}$ divides $n$ and $\varphi(n)$.
This motivates computing $g:=\gcd(n,\varphi(n))$. If $g\ne1$ (which has extremely low probability if $n$ is an actual RSA modulus), then $g$ is a non-trivial factor of $n$ and we have made progress: we can factor $g$ and $n/g$ separately. Further, once we have found the factorization of $g$, we can pull these factors from $n$ leaving $n':=n/\prod\left({p_j}^{k_j}\right)$ to factor, and with known $\varphi(n'):=\varphi(n)/\prod\left(\left(p_j-1\right)\,{p_j}^{k_j-1}\right)$, and now $\gcd(n',\varphi(n'))=1$.
If $g=1$, then $n$ is square-free (that is every $k_i=1$, or equivalently $n$ is the product of distinct primes).
Here $\gcd(900,240)=60=2^2\cdot3\cdot5$. Pulling these factors $2$, $3$, $5$ out of $n$, we get it's complete factorization $900=2^2\cdot3^2\cdot5^2$ and the problem is solved.
Thus in the following we'll move to a larger example: factor $n=12790396087027$, knowing $\varphi(n)=11797951366656$.
$\gcd(12790396087027,11797951366656)=13$, and that's a prime factor of $n$. Pulling out $13$ and it's powers, we have simplified the problem into factoring $n'=n/13^2=75682817083$ knowing $\varphi(n')=\varphi(n)/\big(13\,(13-1)\big)=11797951366656/\big(13\cdot 12\big)=75627893376$. Now we need the further techniques.
General technique for square-free $n$
Knowing any (non-zero) multiple $f$ of $\lambda(n')$ (the Carmichael function) helps factoring square-free $n'$, by using the algorithm there. We have $f=75627893376=2^7\cdot590842917$ thus $s=7$, $t=590842917$.
- $a:=2$, $b=a^t\bmod n'=2^{590842917}\bmod 11797951366656=17605996164$
- $c:=b^2\bmod n'=17605996164^2\bmod 11797951366656=8570506209$, thus $b:=c$.
- $c:=b^2\bmod n'=8570506209^2\bmod 11797951366656=1$, success!
- $p:=\gcd(b-1,n')=\gcd(8570506209-1,11797951366656)=4327$ which is a prime factor of $n'$, $q:=n'/p=11797951366656/4327=17490829$ which is composite, and is not a square.
We are left with factoring $\tilde n=17490829$ knowing $\varphi(\tilde n)=\varphi(n')/(p-1)=17482176=\tilde\varphi$. We could again use the general technique above, but we can also hope this time $\tilde n$ has only two (distinct) prime factors $p$ and $q$.
$n$ product of two distinct prime factors $p$ and $q$
We know $p\,q=\tilde n=17490829$ and $(p-1)(q-1)=\tilde\varphi=17482176$. That's a system of two equations with two unknowns. It follows $p+q=\tilde n-\tilde\varphi+1=\sigma=8654$, thus $p$ and $q$ are the solutions of the second degree equation $x^2-\sigma\,x+\tilde n=0$, thus $p=(\sigma-\sqrt{\sigma^2-4\,\tilde n})/2=(8654-\sqrt{8654^2-4\cdot17490829})/2=3217$ and $q=(\sigma+\sqrt{\sigma^2-4\,\tilde n})/2=(8654+\sqrt{8654^2-4\cdot17490829})/2=5437$. Both $p$ and $q$ are prime, thus our hopes were founded, and in the end the desired factorization is $n=12790396087027=13^2\cdot3217\cdot4327\cdot5437$.
