前言
为了《密码学》这破事，不得不看书看试卷准备考试，面向试卷复习果然快多了。
在看了几道题目后，发现 “乘法逆元” 这一名词的出现频率相当之高，于是产生好奇心，想搞清它到底是干啥的
乘法逆元的概念
先看两个例子
- 13 关于模 5 运算的乘法逆元是 2，因为 (13 * 2) mod 5 = 1
- 14 关于模 3 运算的乘法逆元是 2，因为 (14 * 2) mod 3 = 1
从中总结规律
X 关于模 Y 运算的乘法逆元是 Z，因为 (X * Z) mod Y = 1
翻译成人话
“x 关于模 y 的乘法逆元“ 就是找到一个与 x 相乘除以 y 余 1 的数
乘法逆元的性质
为什么需要乘法逆元？这是因为模 x 运算等于 1 的数，具有一个非常有趣的性质。
模 x 运算等于 1 的数，乘以任何一个数，都不会改变该数模 x 的结果
比如说：
- 26 mod 5 = 1, 那么 52 mod 5 = (26 * 2) mod 5 = 2 mod 5，78 mod 5 = (26 * 3) mod 5 = 3 mod 5 ...
- 肤浅证明： 26 * n mod 5 = [(5 * 5) + 1] * n mod 5 = [(5 * 5 * n) + n] mod 5 = n mod 5，可以看到前 26 * n mod 5, 后 n mod 5，直接约去了 26 (这个模 5 运算等于 1 的数)
乘法逆元的应用
大数求模的化简
比方说：
100 mod 12 = ?
- 首先，找到 mod 12 等于 1 的数，一一枚举
- 13，不是 100 的因数，继续，25，是 100 的因数，打住
- 因为 25 mod 12 = 1，所以 100 mod 12 = (25 * 4) mod 12 = 4 mod 12 = 4
简而言之，就是面对 X mod Y = ? 的问题，尽可能多地约去 X 中 mod Y 为 1 的因数
分数取模
比如 1 / 3 mod 26，就等于 1 * (3 对 26 的逆元),即 1 * 9 = 9
验证一下， 1 / 3 mod 26 = (1 + 26) / 3 mod 26 = 9
简单证明：
设 b 对 c 的逆元是 d
a / b mod c = (a / b) * (bd) mod c = ad mod c
乘法逆元的求解方法
扩展的欧几里得算法
假设需求 a 关于 b 的逆元，
设 ax + by = 1，求解 x, y
(a b) (1 f)
(1 0) 类似矩阵消元不断迭代，直到 a b 有一方为 1，(x h)，得到 x, y
(0 1) (y, i)
如果 x, y 中有一个为负数，那么 +ab - ab 再化得正数即可
实用解法
利用扩展的欧几里得算法原理，用矩阵形式消元化简
费马小定理
a 是整数，p 是质数，且 gcd(a, p) = 1 那么有 a^p = a(mod p), 有 a^(p-1) = 1(mod p)
例子：
7^101 (mod 11)
11 是质数，所以 7^10 = 1(mod 11)
7^101 (mod 11)
= (7^10)^10 * 7
= (1^10) * 7 (mod 11)
= 7后话
为什么密码学这么喜欢求乘法逆元？
讲到《密码学》，就要讲到同余方程组求解，
讲到同余方程组的求解，就要讲到中国余数定理，
中国余数定理，就是代一条公式解同余方程组，
这条公式用到了乘法逆元，所以乘法逆元的就成了该课的基本功
学好乘法逆元，是理解《密码学》的重中之重
暂无评论