[wtp]

Given: e,n
Solve for d

d*e mod n = 1

ex d * 21 mod 28 = 1

How do I solve this type of problem? I know how to solve power mods like 4^723 mod 13, but I'm not sure about this one. Hope someone can point me in the right direction.

[macosxnerd101]

By the way, you should be writing it as: de ≡ 1 (mod n).

You solve through the Extended Euclidean Algorithm to find gcd(21, 28), then work backwards. Note that a solution d exists if and only if gcd(21, 28) = 1.

If you've talked about reducing the exponent by the modulus, you may be familiar with Euler's Totient (phi) function. It counts the number of coprime congruence classes for a given modulus.