Modular Multiplicative Inverse（模乘逆元）

本文主要是介绍Modular Multiplicative Inverse（模乘逆元），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

计算模乘逆元原理上有四种方法：

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 $a^{-1} \equiv x \pmod{m}.$

That is, it is the multiplicative inverse in the ring of integers modulo m. This is equivalent to $ax \equiv aa^{-1} \equiv 1 \pmod{m}.$

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 $ax \equiv 1 \pmod{m}.$ 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 bythe pair x and y of equation ax + by = gcd(a,b)*/
pair<int, pair<int, int> > 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 bythe pair x and y of equation ax + by = gcd(a,b)*/
pair<int, pair<int, int> > extendedEuclid(int a, int b) {if(a == 0) return make_pair(b, make_pair(0, 1));pair<int, pair<int, int> > 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, then a^p − 1 will be evenly divisible by m. That is $a^{m-1} \equiv 1 \pmod{m}.$ or $a^{m-2} \equiv a^{-1} \pmod{m}.$ 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 $a^{\varphi(m)} \equiv 1 \pmod{m}$ , where where φ(m) is Euler Totient Function. Therefore the modular multiplicative inverse can be found directly: $a^{\varphi(m)-1} \equiv a^{-1} \pmod{m}$ . The problem here is finding φ(m). If we know φ(m), then it is very similar to above method.

vector<int> inverseArray(int n, int m) {vector<int> 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;
}

这篇关于Modular Multiplicative Inverse（模乘逆元）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！