# Algorithm for factoring a number $n$ of a specific form given $n$ and $\varphi(n)$

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

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

• It's very easy to solve. The first step for you is to calculate le product p.q by a classical square root. Then try to use the form of the given Euler totient for this particular case, which allow to compute the sum (p+q), and then all follow. Jul 25, 2015 at 17:54

The (in my opinion) simplest way to proceed about this is: First compute the square root $m:=\sqrt n$ of $n$ in $\mathbb N$; this can, for instance, be done in time $\mathcal O(\log^3n)$ using a binary search.
The next step is to compute $\varphi(m)$ from $\varphi(n)$: by the properties of $\varphi$ we have $$\varphi(n) = (p-1)p(q-1)q=\varphi(m)\cdot m \text,$$ hence $\varphi(m)=\varphi(n)/m$.
Now you can apply the standard method to compute $p$ and $q$ from $m$ and $\varphi(m)$, as described in Dan Boneh's paper (proof of fact 1). Note that in the linked paper, one is assumed to be given a tuple $(m,e,d)$ with $ed\equiv1\pmod{\varphi(m)}$, but that's not actually necessary: choosing $k$ as any non-zero multiple of $\varphi(m)$ is sufficient.
• (And in any case, even if it were necessary we could just generate one since we know $\varphi(m)$.) Jul 25, 2015 at 20:48