Factoring a number $p^a q^b$ knowing its totient

Question

We are given: $n=p^aq^b$ and $\phi(n)$, where $p,q$ are prime numbers. I have to calculate the $a,b,p,q$, possibly using computer for some calculations, but the method is supposed to be symbolically valid and proper. I know that $\phi(n)=p^{a-1}q^{b-1}(p-1)(q-1)$, but I dont know what can I deduct from this.

Answer 1

Without loss of generality we can assume that $p<q$. I would first compute the greatest common divisor of $n$ and $\phi(n)$, $m=\gcd(n,\phi(n))$. There are two possibilities.

1) $m=p^{a-1}q^{b-1}$. This happens, if $p$ is not a factor of $q-1$. In this case we can calculate $$ \frac{n}{m}=pq,\qquad\text{and}\qquad \frac{\phi(n)}{m}=(p-1)(q-1)=pq-(p+q)+1. $$ In this case we know $r=p+q$ and $s=pq$, and can solve the primes $p$ and $q$ as the roots of the quadratic equation $$ 0=(x-p)(x-q)=x^2-(p+q)x+pq=x^2-rx+s. $$

2) $m=p^aq^{b-1}$. This happens, if $p$ is a factor of $q-1$. This time $$ \frac{n}{m}=q,\qquad\text{and}\qquad\frac{\phi(n)}{m}=\frac{(p-1)(q-1)}p. $$

I think that is possible to build a method from these bits alone. I would assume that we have the first case, and then check that it works in a separate verification step. The roots of the quadratic need to be integers, and we can keep on dividing $n$ with the roots to verify that the number $n$ is, indeed, of the form $p^aq^b$. If something goes wrong, then we must have case 2. This time we know $q$ directly, and can solve for $p$ from the equation $$ \frac1{q-1}\cdot\frac{\phi(n)}{m}=\frac1{q-1}\cdot\frac{(p-1)(q-1)}p=\frac{p-1}p=1-\frac1p, $$ because the LHS is known.

Undoubtedly there are alternative ways of exploiting these bits. The key is to compute $m$ first.