计算 e 在模 m 域上的逆元 d

为计算 e 在模 m 域上的逆元 d，需要使用扩展欧几里得算法。该算法可以计算出两个数的最大公约数，以及满足贝祖定理的一组解（即 ax + by = gcd(a,b)）。当且仅当 e 和 m 互质时，e 在模 m 域上才有逆元，此时可以使用扩展欧几里得算法计算出 e 在模 m 域上的逆元 d，满足 ed ≡ 1 (mod m)。

具体地，假设我们要计算的是 e 在模 m 域上的逆元 d，首先判断 e 和 m 是否互质，如果不互质，即 gcd(e,m) ≠ 1，则无法计算 e 在模 m 域上的逆元。如果 e 和 m 互质，则可以使用扩展欧几里得算法计算出一组解 (x,y)，使得 ex + my = 1。由于 ex ≡ 1 (mod m)，因此 x 即为 e 在模 m 域上的逆元 d。

以下是使用 Python 实现计算 e 在模 m 域上的逆元 d 的代码：

def ext_gcd(a, b):
    if b == 0:
        return (1, 0, a)
    else:
        x, y, gcd = ext_gcd(b, a % b)
        return (y, x - a // b * y, gcd)

def mod_inv(e, m):
    x, y, gcd = ext_gcd(e, m)
    if gcd != 1:
        # e 和 m 不互质，无法计算逆元
        return None
    else:
        # 返回 e 在模 m 域上的逆元
        return x % m

使用示例：

>>> mod_inv(3, 11)
4
>>> mod_inv(4, 8)
None

在上面的示例中，mod_inv(3, 11) 返回 4，表示 3 在模 11 域上的逆元为 4；mod_inv(4, 8) 返回 None，表示 4 和 8 不互质，无法计算逆元。