# Factor RSA modulus given many valid encryption decryption exponent pairs?

I have read Is sharing the modulus for multiple RSA key pairs secure?, which explains an algorithm for factoring an RSA modulus n given only one encryption and decryption exponent tuple. Given multiple such tuples, is there a more efficient way to compute p and q? It seems like we could set up a system of equations using the Chinese Remainder Theorem and then could solve for Euler's totient directly. Once we have Euler's totient, we could solve a system of two equations with N and totient(N) to obtain p and q.

It's a little trickier than that; one issue is that we may have $ed \not\equiv 1 \pmod{(p-1)(q-1)}$; hence what such a series of equations would give might not be $(p-1)(q-1)$, but instead $\text{lcm}(p-1, q-1)$. Now, in practice, $(p-1)(q-1)$ is extremely close to $N$, and hence it should be possible to give a good guess of $(p-1)(q-1)$ given $\text{lcm}(p-1, q-1) = (p-1)(q-1)/\gcd(p-1, q-1)$; however, it is nontrivial to write up an algorithm that will work in general. In contrast, the standard probabilitic method always works (ok, half the time...)