# How do I retrieve a number which has been multiplied with a random number?

I have a 1024-bit number $$n$$ obtained by multiplying two 512-bit randomly generated prime numbers $$p$$ and $$q$$.

Then there's $$\phi = (p-1)(q-1)$$, which is another 1024-bit number.

I do not have $$\phi$$ but I do have the result obtained by multiplying $$\phi$$ with a random 1024-bit number.

I need to retrieve $$p$$ and $$q$$. I know how to get to $$p$$ and $$q$$ values starting from $$\phi$$ but I don't know how to extract $$\phi$$ from the product I have.

Is it even possible?

• Do you need the original $\varphi$ or can you also make do with some multple of $\varphi$? (In the latter case you don't need to recover $\varphi$...) – SEJPM Oct 29 at 10:03
• Very nearly a duplicate of Algorithm for factoring knowing RSA private key and Why is it important that phi(n) is kept a secret, in RSA?. Hint: One way is to factor $n$, then compute $\phi$. A concise description of Miller's algorithm to solve this is Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem, proof of fact 1. – fgrieu Oct 29 at 12:34
• Also: depending on the smoothness of the random number and $\phi$, there may be other ways noticing that $n\approx\phi$. – fgrieu Oct 29 at 14:15
• I need to retrieve $p$ and $q$ and in order to do that I need to somehow extract $\phi$ from the number I have. @fgrieu if I could factor $n$ then I would not need to compute $\phi$ as I would already have $p$ and $q$. Also, the Miller's algorithm seems to not be applicable to this problem as I do not have $d$ or $e$. It is not an RSA problem. – Combiner_85 Oct 31 at 0:10
• @SEJPM In fact I already have a multiple of $\phi$, can I extract $p$ and $q$ directly from it? – Combiner_85 Oct 31 at 0:11