## General solution for arbitrary e

Since d and e are modular inverses modulo m you
also have d*e-1 = c*m for some constant
c.

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
k.

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
(mod 3)

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
remains.

Therefore: m = (3d-1)/2