General solution for arbitrary e
Since d and e are modular inverses modulo m you
also have de-1 = cm for some constant
We also have k^m = 1 (mod n) when gcd(k,n) = 1,
and therefore also k^(de-1) = 1 (mod n).
m is at least divisible by 4 (since p and q are
odd) so split d*e-1 into t*2^s with t odd and
calculate k^t (mod n), when you square the result
s times (mod n) you will eventually reach 1, maybe
earlier than after s squarings.
The intermediate result just before you reach 1
can be -1 (mod n); if that happens try another
If you reach 1 from another number, say x, we
have found an x that is not 1 or -1 and x^2 = 1
(mod n). In other words x^2 -1 = (x-1)*(x+1) = 0
(mod n) and gcd(x-1,n) is a non trivial factor of
n (say q). Now you have found q and p=n/q and can
easily calculate m.
Special case for e=3
Assume that p,q > 3.
d and e=3 are modular inverses, so 3d-1=cm.
Since d < m we have immediately that c can only
be 1 or 2.
Furthermore, since e has a modular inverse, m
and therefore also p-1 and q-1 must not be
divisible by 3.
p and q are both not divisible by 3, this
leaves only the case that p and q are congruent to
2 (mod 3) and therefore p-1 and q-1 are congruent
to 1 (mod 3). But this makes also m congruent to 1
Taking the equation 3d-1=cm modulo 3 we have
0*d-1 = c*1 (mod 3) or c = 2 (mod 3). Since there
are only 2 possibilities for c just c=2
Therefore: m = (3d-1)/2