写在前面
上一节介绍了离散之模运算规则，其中有两个遗留问题：
-
模运算与取余运算区别
-
模运算除法运算规则
因为这两个都涉及到除法运算，且有不少差别，所以单独写一节，以便更好说明。
模运算与取余运算区别
取余是数学中定义的，但是计算机中不同语言实现 % 并不完全一样。对取余和取模不同语言实现有一个不同点：
在涉及到除数和被除数符号不同的时候，即一正一负的情况
取余运算在计算商值向0方向舍弃小数位
取模运算在计算商值向负无穷方向舍弃小数位
举例说明下，8 % -3
-
取余运算
8/-3=-2.66... 结果舍弃小数点，商取-2， 故余数为8-（-2）*（-3）=2
-
取模运算 8/-3=-2.66... 结果向上接近的大负数，商取-3， 故余数为8-（-3）*（-3）=-1
有个规律，a%b 当a,b符号不同时，取余运算结果与a同号，取模运算结果与b同号，可自行验证！。
小结：二者在数学上是一样的，只是取模运算倾向于计算机科学实现，本质是因为根据求余运算定义导致余数不唯一时不同程序设计语言采用了不同的结果。
所以有其他文章指出：程序移植时要当心这种差别，特别是当两个整数含有负数的情况。应该小心。
好在主流语言大都实现了同种方式：求余方式。
经过实践，Python上% 采用的是取模的实现， 其他主流语言如Java,JS，C#，C++ 采用求余方式，更多语言自行尝试。
模运算逆元求法
模运算的除法 b/a mod m， 通过转化为b *$a^{-1}$ mod m 来计算。
问题转化为求$a^{-1}$ mod m即a的模逆元问题。
逆元含义如下：
对于整数a ,m 如果ax≡1 (mod m),则称最小整数解x是a模m的逆元。求解x有如下几种方法：
-
费马小定理解法
前提条件是：m 是质数，a与m互质。[注：由于m是质数，所以只要a不是m的倍数即可]
根据费马小定理，$a^{m-1}$ ≡ 1 mod m,可得：a*$a^{m-2}$ ≡ 1 mod m, 所以$a^{m-2}$ mod m 即使所求解。
这里可以使用快速幂取模算法：
long pow_mod(long a,long b,long m){
long ans = 1;
long base = a%c;
while(b){
if(b & 1) ans = (ans*base)%c;
base = (base*base)%c;
b >>= 1;
}
return ans;
}
上式得到$a^b$ mod m 的结果。这里用到了前一文章中提到的乘法模运算规则：
(ab) mod c = ((a mod c)(b mod c)) mod c
这里我们在给base赋值的时候就运行了一次。
-
扩展欧几里得解法
前提条件是：a与m互质 m不一定为质数
由于如果ax≡1 (mod m) 可以转化为方程：ax+my=1=gcd(a,m)，之前的文章介绍过扩展欧几里算法，这样方程必有整数解，可以求出x即是a模m的逆。同理y是m模a的逆。具体算法参考扩展欧几里算法。
注意如果算出x是负数，一般转为正数，(x+m)%m
注意一点，如果调用该方法前没有判断a,m是否互质， 则需要检查该方法返回的gcd结果是否为1，若是不为1，则为无逆元情况，得到逆元值为0。
-
欧拉定理解法
前提条件是：a与m互质即可
说到欧拉定理，先得说说欧拉函数：
对于正整数m,在1到m ([1,m])中,与m互质的正整数(包括1)的个数，记作φ(m)。欧拉定理公式表示为：$a^{φ(m)}$ ≡ 1 mod m
参考代码如下：
int eurler_phi(int n) {
int res = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
res = res / i * (i - 1);
while (n % i == 0) {
n /= i;
}
}
}
if (n != 1) {
res = res / n * (n - 1);
}
return res;
}
计算出φ(m)后，再使用上面的快速幂取模算法即可的模m的逆，
另外，当m是素数时候， 欧拉函数φ(m)=m-1, 欧拉定理演变为费马小定理。
关于欧拉定理与费马小定理后续单独介绍。
- 递推求法：
前提条件是：m是素数
设 m=aq+r ， 即 q=m/a, r= m%a， 两边同时取模m得：
m mod m ≡ 0 ≡ aq+r (mod m) 移项得, a=-r inv(q) (mod m)
两边取逆，inv(a)= -q inv(r) (mod m)
将q=m/a, r= m%a代入，得出：
inv(a)= -m/a * inv(m%a) (mod m)
起始1的逆元是1 ，即inv(1)=1, 可以得到递推算法如下：
int recursiveModReversion(int a,int m) {
int[] inv = new int[a + 1];
inv[1] = 1;
for (int i = 2; i <= a; i++) {
inv[i] = (m - m / i) * inv[m % i] % p;
}
return inv[a];
}
这种方法时间复杂度是O(n), 占用内存较大，适合a ,m 数字不是很大的情况。 经过实践，如果m是合数时，只要a不是m的乘因子且m%a不等于因子的倍数，也是可以使用的。
例：当m=217,不是素数，有因子7，21等，当求10 mod 217的逆元时， 217% 10=21 是因子7的倍数， 使用该方法求逆元的是0，是不正确的。
总结
并不是所有a,m 都存在模逆元，只有当a与m互质才有乘法模逆元存在。这个可以通过扩展欧几里得方法来证明。实际数论或密码学中模m 基本都是素数，所以前两种方法应用最多。
说明一点：文中出现质数， 素数，可以理解一样的意义，尽管二者有细微差别。
好了到此，模运算的规则都讲清楚了。但是这里面依然有很多其他知识点，如本文中欧拉定理， 费马定理等，这些相关的依赖知识打算在《区块链数学篇》介绍快完毕的时候，单独章节详细介绍，以求知识体系的完备。如果只是零散的学习，没有系统体系，就无法融会贯通，相互印证。
所以后续还会有很多相关章节，下一节计划讲我们之前多次提到的RSA算法。
欢迎关注公众号：blocksight
