Algorithm for finding prime numbers of specific form

Question

Given the natural number $n$,who is in the form $p^2 \cdot q^2$,with $p$,$q$ prime numbers.Also $φ(n)$ is given.Describe a fast algorithm(polynomial time) that calculates the $p$ and $q$.Apply your algorithm to calculate the $p$,$q$ when $n=34969$ and $φ(n)=29920$

I found this problem on a mathematical competition on cryptography.I tried to find a solution alone and in the internet and i didn't conclude anywhere, can we find a solution?

Answer 1

Hint: $$\phi(n) = n^2 - n(p+q) - pq$$

Answer 2

Since $n$ is a perfect square, $pq = \sqrt{n}$. Now, as for the $\phi$ function: $$ \phi(p^2 q^2) = \phi(p^2)\phi(q^2) = (p - 1)(q - 1)pq$$

Thus, $$\dfrac{\phi(n)}{\sqrt{n}} = (p - 1)(q - 1) = pq - p - q + 1$$ And thus, you get: $$\sqrt{n} - \dfrac{\phi(n)}{\sqrt{n}} + 1= p + q = p + \dfrac{\sqrt{n}}{p}$$ Multiply both sides by $-p$: $$p^2 - p\left(\sqrt{n} - \dfrac{\phi(n)}{\sqrt{n}} + 1\right) + \sqrt{n} = 0$$

Let's try your example. Since $n = 34969$ and $\phi(n) = 29920$, then $\sqrt{n} = 187$ and the equation we have to solve for $p$ is: $$p^2 - p\left(187 - \dfrac{29920}{187} + 1\right) + 187 = 0$$ If we simplify: $$p^2 - 28p + 187 = 0$$ The solutions are $p = 11$ and $p = 17$. Actually, due to the symmetric relation between $p$ and $q$ in our previous equation, these two solutions for $p$ happen to be the solution for the pair $(p, q)$. You'd notice that $pq = 187$ if we assign $p = 11$ and $q = 17$.

So, an efficient algorithm is to solve the quadratic equation. The solution for the pair $(p, q)$ is then just both roots of the equation. This is $\mathcal{O}(1)$.