Consider RSA public-key encryption with public modulus $N=3953$.
Suppose we know that the public keys $e_1=337$ and $e_2=23$ correspond with the decryption information $d_1=3385$ and $d_2=2663$. That is: $e_1d_1=e_2d_2=1$ mod $\phi(N)$ and $m^{e_1d_1}=m^{e_2d_2}=m$ mod $N$, for all integers $m$ that are relatively prime to $N$.
How do I find the prime factorization of $N$ from the above information? I want to find the prime factorization without any brute-force method.
I have noticed that $m^{e_1d_1-e_2d_2}=1$ mod $N$. I have also noted that $e_1d_1-1$ is a multiple of $\phi(N)$. Does this say somehting about the prime factorization of $N$?
Edit:
$gcd(e_i,\phi(N))=1$ and $e_id_i=1$ mod $\phi(N)$ by assumption, for $i=1,2$.