0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Robert NACIRI Jul 25 '15 at 17:54
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ (And in any case, even if it were necessary we could just generate one since we know $\varphi(m)$.) $\endgroup$ – fkraiem Jul 25 '15 at 20:48
  • $\begingroup$ @fkraiem Right; I had intended to note this, but it seemed superfluous given the nature of the invoked procedure. $\endgroup$ – yyyyyyy Jul 25 '15 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.