Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
