Given $\varphi (n)$ and $n$ for large values, can we know prime factors of $n$

Question

If a number is product of two primes, then given its totient function, we can know its prime factors, but how do we do this in generic case? If the number could have more than two prime factors can we still factorize the number given its totient function values?

Answer 1

This is essentially the same answer as the top one as @DavidG.Stork's link, but with some extra info.

Edit 2: Sagemath code example of the algorithm.

---

We may factor out even primes easily, so we assume $n$ is a product of odd primes. Then $\varphi(n)$ is divisible by $2$, so we may write $\varphi(n) = 2t$.

Pick a random integer $2<a<n$. If $\gcd(a,n)\neq 1$, then we have found a factor which reduces the problem (also see last part).

Assume instead that $\gcd(a,n)=1$. By Euler's Theorem, we know that $$ \begin{align} a^{2t} = a^{\varphi (n)} &\equiv 1 \pmod n\\ (a^t + 1)(a^t-1) &\equiv 0 \pmod n \end{align} $$ This means that the odd prime factors $p_i$ of $n$ each divide either $a^t+1$ or $a^t-1$. It cannot divide both, since $$ \gcd(a^t+1,a^t-1) = \gcd(2,a^t-1) $$ implies that $a^t+1$ and $a^t-1$ have a common factor of $2$ or none at all.

With high probability, either one of $$ \gcd(a^t+1 \pmod n,n),\quad \gcd(a^t-1 \pmod n,n) $$ will give a factor $1<d<n$, which reduces the problem. If this fails, we simply try another random $a$. This can only fail when $a^t+1\equiv 0\pmod n$ and $a^t-1\equiv 0\pmod n$, which I believe is at most $50\%$ chance (this is true for $n=pq$, not sure for multiple primes).

Edit 1: If $a^t-1\equiv 0 \pmod n$ and $t$ is even, we repeat the process: $$ (a^{t/2}+1)(a^{t/2}-1) \equiv 0 \pmod n $$ End_edit

The key here is for every $2$ tries, each of them easy to compute, we expect to get a random non-trivial factorization of $n$.

---

Whenever we find a prime factor $p$, we can divide out the maximum power $p^r$ from $n$ and $p^{r-1}(p-1)$ from $\varphi(n)$ and repeat the process. If the found factor $d$ is composite instead, write $n = dm$ and then repeat the process for $d$ and $m$ seperately using more random $a$'s: Since $$ (a^t+1)(a^t-1) \equiv 0 \pmod m $$ we can try $$ \gcd(a^t+1 \pmod m,m),\quad \gcd(a^t-1 \pmod m,m) $$