Given $φ(n)$ how can we find any combinations for $p, q$ prime numbers

Question

Suppose i already have found that $φ(n) = 240$ for $n = 900$. How can i conclude that my $n = pq$ is of type $2^2\cdot3^2\cdot5^2$? What is $q$ and what is $p$ here?

To be more precise with my question: is it for all $n \in \Bbb N$ with only known $φ(n)$ , can i find the disassembly of $n$ to prime factors?

Edit(The calculation that i have done so far):

$φ(n) = (p - 1)(q - 1)$

$240 = pq - (p + q) + 1$

Substitute for $n$ :

$(p + q) = 900 - 240 + 1 = 661$

Find $(p - q)$:

$(p - q)^2 = (p + q)^2 - 4pq = (661)^2 - 4\cdot900 = ... = 433,321$ $(p - q) = 658.271$

From this point and on, adding $(p - q), (p + q)$ together obviously gives the wrong result for $n = pq$.

Answer 1

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

1. 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).
2. 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 .
3. 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$.