Factors of RSA modulus

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 cannot 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 factors, knowing the public and private key. But I cannot understand how exactly it is done. Does someone know? Or have a small example?

• Please do not cross-post questions on multiple sites. Even if it fits on multiple. Only post on one. – mikeazo Jan 13 '15 at 20:23
• Ok, thanks for the advise. I did not know in which one should I post the question. – user3343768 Jan 14 '15 at 11:11

While the way that Robert showed can work if $e$ is small (and if $e \cdot d \equiv 1 \pmod{\phi(n)}$ (which is not necessarily true), there is a slightly more complicated method which will work in any case.

What we do is compute $\lambda = (e \cdot d - 1)/ 2^k$ odd (and $k$ is the integer that makes $\lambda$ odd. The special property that $\lambda$ has is that $(m^\lambda)^{2^k} \equiv 1 \pmod{n}$ for any $m$ relatively prime to $n$.

Here's how we use it; we pick a random $m$, and compute $m^\lambda \mod n$. If it is 1 or $n-1$, we go back and select another $m$.

If it is not, we repeatedly square the value ($\mod n$), and check if the value becomes 1 or $n-1$ (and because of $\lambda$'s property, it'll turn into one of the two in at most $k$ squarings, unless we happened to pick an $m$ which wasn't relatively prime to $n$); if the value became $n-1$, we go back, and pick another $m$. However, if it became 1, that means that the immediately previous value $z$ had the property $z^2 \bmod n = 1$, that means that $gcd(n,z-1)$ and $gcd(n,z+1)$ are the factors of $n$.

And, at least 1/2 of the possible $m$ values will result in a factorization, hence this method is practical.

• Is there a simple proof that at least 3/4 of the possible $m$ values will result in a factorization? – fgrieu Jan 14 '15 at 7:20
• @fgrieu: actually, the real figure is 1/2, not 3/4 (I've corrected my answer). As for a simple proof, well, one won't fit on this response, however here's how it works: if we look at the behavior of $(m^\lambda)^{2^i}) \pmod p$, we see that it has a probability 0.5 of turning into 1 at step $j$ (where $j$ is such that $(p-1)/j$ is odd), and a probability 0.5 of turning into 1 at some earlier step; and similarly with $q$. Now, $m$ will reveal a factorization if $p$ and $q$ turn into 1 on different steps. – poncho Jan 14 '15 at 14:43
• then method showned by Poncho is in fact a corrollary of Miller-Rabin primality test. In case of RSA, the prime factors have passed MR test and hence we understand the method.Solving the quadratic polynomial $z^2-1=0$ in Z/nZ would lead to 4 solutions, from which only two give modulus factorization. (quadratic polynomials have at most 2 solutions only in fields). Then probability of success is 0,5. This can be linked with the general problems of quadratic residue and the the Rabin Cryptosystem. – Robert NACIRI Jan 14 '15 at 16:58

Generally the public exponent is small. then if you know the public and private key, then you can compute $e.d=1+k.\phi(n)$. k is smaller than e and $\phi(n)$ is in the range of n. A direct method allow to make an exhaustive search on the small k which divide ed-1 in such a way that $\frac{e.d-1}{k}$ is an integer.

Then $\phi(n)= p.q -(p+q)+1$ allow to find $p+q$ and solving a quadratic equation gives directly p and q.

This is the simplest method, which can be easilly implemented.