乘法逆元的计算

计算乘法逆元是学习加密算法的基础，在 RSA、ECC 和 AES 加密算法中都会用到，在网上提供的方法也有，比如扩展欧几里德算法等，看了以后要根据它提供的示例去推导也是有困难的，关键是自己太渣了。以前以为加密算法的基础是数学，后来才知道不是数学，而是数论。无路可逃啊！

乘法逆元的概念

模 n 乘法逆元：对于整数 a、n，如果存在整数 b，满足 ab mod n = 1，则说，b 是 a 的模 n 乘法逆元。a 存在模 n 的乘法逆元的充要条件是 gcd(a, n) = 1。

光看概念感觉不是太复杂，实际计算时还是有点绕，要找出一个给定 a 和 n 且能满足 (a * b - 1) / n = 0 中的 b 多少还是有点难度的。至少我这么觉得吧。

乘法逆元计算的流程

不过后来得到一个简单的流程，根据流程计算还是相对比较容易的。流程如下：

1. （x1, x2, x3) <- (1, 0, n); (y1, y2, y3) <- (0, 1, a)
2. 如果 y3 = 0，返回 x3 = gcd(a, n) 无逆元
3. 如果 y3 = 1， 返回 y3 = gcd(a, n)；y2 = a ^ -1 mod n
4. Q = max_int(x3 / y3)
5. (t1, t2, t3) <- (x1 - qy1, x2 - qy2, x3 - qy3)
6. (x1, x2, x3) <- (y1, y2,y3)
7. (y1, y2, y3) <- (t1, t2, t3)
8. 返回到 2

在上面的流程中的 3 可以看出，如果 y3 等于 1，那么 y2 就是乘法逆元，如果 y2 是负数，那么需要把 y2 + n 后再 mod n，就可以得到 a 模 n 的乘法逆元了。