计算模乘逆元原理上有四种方法： 1.暴力算法 2.扩展欧几里得算法 3.费尔马小定理 4.欧拉定理 模乘逆元定义：满足 ab≡1（mod m)，称b为a模乘逆元。以下是有关概念以及四种方法及程序。 文章出处：Modular Multiplicative Inverse
The modular multiplicative inverse of an integer a modulo m is an integer x such that That is, it is the multiplicative inverse in the ring of integers modulo m. This is equivalent to 1. Brute Force
We can calculate the inverse using a brute force approach where we multiply a with all possible valuesx and find ax such that Here’s a sample C++ code: int modInverse(int a, int m) { a %= m; for(int x = 1; x < m; x++) { if((a*x) % m == 1) return x; } }
2. Using Extended Euclidean Algorithm
We have to find a number x such that a·x = 1 (mod m). This can be written as well as a·x = 1 + m·y, which rearranges into a·x – m·y = 1. Since x and y need not be positive, we can write it as well in the standard form, a·x + m·y = 1. Iterative Method /* This function return the gcd of a and b followed by the pair x and y of equation ax + by = gcd(a,b)*/ pair > extendedEuclid(int a, int b) { int x = 1, y = 0; int xLast = 0, yLast = 1; int q, r, m, n; while(a != 0) { q = b / a; r = b % a; m = xLast - q * x; n = yLast - q * y; xLast = x, yLast = y; x = m, y = n; b = a, a = r; } return make_pair(b, make_pair(xLast, yLast)); } int modInverse(int a, int m) { return (extendedEuclid(a,m).second.first + m) % m; }
Recursive Method /* This function return the gcd of a and b followed by the pair x and y of equation ax + by = gcd(a,b)*/ pair > extendedEuclid(int a, int b) { if(a == 0) return make_pair(b, make_pair(0, 1)); pair > p; p = extendedEuclid(b % a, a); return make_pair(p.first, make_pair(p.second.second - p.second.first*(b/a), p.second.first)); } int modInverse(int a, int m) { return (extendedEuclid(a,m).second.first + m) % m; }
3. Using Fermat’s Little Theorem
Fermat’s little theorem states that if m is a prime and a is an integer co-prime to m, thenap − 1 will be evenly divisible by m. That is or Here’s a sample C++ code: /* This function calculates (a^b)%MOD */ int pow(int a, int b, int MOD) { int x = 1, y = a; while(b > 0) { if(b%2 == 1) { x=(x*y); if(x>MOD) x%=MOD; } y = (y*y); if(y>MOD) y%=MOD; b /= 2; } return x; } int modInverse(int a, int m) { return pow(a,m-2,m); }
4. Using Euler’s Theorem
Fermat’s Little theorem can only be used if m is a prime. If m is not a prime we can use Euler’s Theorem, which is a generalization of Fermat’s Little theorem. According to Euler’s theorem, if a is coprime to m, that is, gcd(a, m) = 1, then, where where φ(m) is Euler Totient Function. Therefore the modular multiplicative inverse can be found directly:. The problem here is finding φ(m). If we know φ(m), then it is very similar to above method. vector inverseArray(int n, int m) { vector modInverse(n + 1,0); modInverse[1] = 1; for(int i = 2; i <= n; i++) { modInverse[i] = (-(m/i) * modInverse[m % i]) % m + m; } return modInverse; }