2.5 模乘逆元-二进制快速幂法

在说之前，我先讲讲欧拉定理Euler’s theorem，该死，又是欧拉。欧拉定理说的是，如果a和m互质，那么有：
$$a^{\varphi (m)}\equiv 1modm$$
公式中的$\varphi (m)$是欧拉函数，欧拉函数则属于提前学习的内容，如果需要了解，可以查看我的另一篇博文欧拉函数，则对于m为质数或卡迈克尔数，有费马小定理：
$$a^{m-1}\equiv 1modm$$
而模乘逆元的定义x是：
$$ax\equiv 1modm$$
所以模乘逆元很好求嘛。看m是个什么数，如果m是一个质数，那么就按费马小定理进行计算，如果a和m互质，那么就按欧拉定理计算。但是因为质数与任何不等于自己的整数互质，那么统一按欧拉定理计算就好了。况且，当一个数p是质数时，它的欧拉函数值等于本身减去1，也就是$\varphi (p)=p-1$。把欧拉定理展开：
$$a\cdot a^{\varphi (m)-1}\equiv 1modm$$
所以模乘逆元就是$a^{\varphi (m)-1}$，但是不满足以上两种情况该怎么办呢？如果不互质的话，则不存在模乘逆元。
但是这个数$a^{\varphi (m)-1}$也未免太大了啊。我们知道$a^{-1}$是一组同余类，所以需要把这个数字除于m然后取余，得到一个不太大的数字。
Python代码如下：

# _*_ coding:utf-8 _*_
def gcd(m, n):
    if m < n:
        m, n = n, m
    while m % n != 0:
        m, n = n, m % n
    return n


def binary_exponentiation(base, power):
    power_2 = 1
    r = 1
    p = base
    while power_2 <= power:
        if power_2 & power != 0:
            r *= p
        p = p * p
        power_2 = power_2 << 1
    return r


def euler_totient(n):
    phi = [i for i in range(0, n + 1)]
    for i in range(1, n + 1):
        # 把i后面的全部减去phi[i]
        for j in range(i << 1, n + 1, i):
            phi[j] -= phi[i]
    return phi[n]


def modular_inverse(a, m):
    if gcd(a, m) == 1:
        return binary_exponentiation(a, euler_totient(m) - 1) % m
    else:
        raise RuntimeError(f'{a},{m}不互质，没有模乘逆元')


if __name__ == '__main__':
    a, m = 3, 2
    x = modular_inverse(a, m)
    print(f'{a} * {x} % {m} = {a * x % m}')

    a, m = 1024, 997
    x = modular_inverse(a, m)
    print(f'{a} * {x} % {m} = {a * x % m}')
    print(modular_inverse(3, 6))

测试结果：

3 * 1 % 2 = 1
1024 * 517 % 997 = 1
Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "E:\JetBrains\PyCharm 2021.1.2\plugins\python\helpers\pydev\_pydev_bundle\pydev_umd.py", line 197, in runfile
    pydev_imports.execfile(filename, global_vars, local_vars)  # execute the script
  File "E:\JetBrains\PyCharm 2021.1.2\plugins\python\helpers\pydev\_pydev_imps\_pydev_execfile.py", line 18, in execfile
    exec(compile(contents+"\n", file, 'exec'), glob, loc)
  File "F:/learn/math-algorithm/src/main/python/com/youngthing/mathalgorithm/numbertheory/modular_inverse.py", line 46, in <module>
    print(modular_inverse(3, 6))
  File "F:/learn/math-algorithm/src/main/python/com/youngthing/mathalgorithm/numbertheory/modular_inverse.py", line 35, in modular_inverse
    raise RuntimeError(f'{a},{m}不互质，没有模乘逆元')
RuntimeError: 3,6不互质，没有模乘逆元