In the article "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", the original RSA article, it is mentioned that Miller has shown that n (the modulus) can be factored using any multiple of φ(n).
Imagine I know the public and the private key. But what I really want is the factors of n, the p and q but I connot use any factorization algorithm in a large number of n.
In the Miller's article it is suppose to say how I can find the two factores, knowing the public and private key. But I cannot understand how exactly it is done. Does someone know? Or have a small example?
Appreciated
So you have as input $d,e$ and you want to factor $N.$ There is a probabilistic algorithm which will give you the factors with probability $\approx 1/2.$ Set $k=de-1\equiv (0\mod \phi(N))$ so there is $\lambda \in {\bf Z}$ such that $k=\lambda \phi(N).$ Since $\phi(N)$ is even we can write $k=2^ab$ with $b$ odd. Now,take a random $g\in {\bf Z}_N^{*},$ then $x=g^{k/2}$ is a root of unity $\mod N$ (from Euler's theorem). From CRT the roots of unity are 4, where two of them are the $\pm 1\mod N.$ Now if $x$ is different from $\pm 1\mod N$ you are done, since then $\gcd(x-1,N)$ is a non trivial factor of $N.$ If not take a new $g$ and compute $g^{k/2},g^{k/4},...,g^{k/2^{a}}$ all ${\mod N}.$ If we choose $g$ randomly, with probability $1/2,$ at least one of the previous is $\not= \pm 1 \mod N.$ So you are done.