求解乘法逆元的方法

文章目录

• 取模公式
• 乘法逆元
• 费马小定理
• 欧拉函数
• 扩展欧几里得算法
• 线性求逆元

求解乘法逆元有三种常用方法：

1、费马小定理/欧拉函数

2、扩展欧几里德算法

3、线性求逆元

取模公式

( a + b )   m o d   p = ( a   m o d   p + b   m o d   p )   m o d   p (a+b)~mod~p=(a~mod~p+b~mod~p)~mod~p (a+b) mod p=(a mod p+b mod p) mod p

( a − b )   m o d   p = ( a   m o d   p − b   m o d   p + p )   m o d   p (a-b)~mod~p=(a~mod~p-b~mod~p+p)~mod~p (a−b) mod p=(a mod p−b mod p+p) mod p

( a × b )   m o d   p = ( a   m o d   p × b   m o d   p )   m o d   p (a\times b)~mod~p=(a~mod~p \times b~mod~p)~mod~p (a×b) mod p=(a mod p×b mod p) mod p

( a ÷ b )   m o d   p = ( a × b φ ( p ) − 1 )   m o d   p = ( a   m o d   p × b φ ( p ) − 1   m o d   p )   m o d   p (a\div b)~mod~p=(a\times b^{\varphi(p)-1})~mod~p=(a~mod~p\times b^{\varphi(p)-1}~mod~p)~mod~p (a÷b) mod p=(a×bφ(p)−1) mod p=(a mod p×bφ(p)−1 mod p) mod p

乘法逆元

为了对除法算式进行取模，我们引入了乘法逆元的概念：

若存在正整数 a 、 b 、 p a、b、p a、b、p满足 a b ≡ 1 ( m o d   p ) ab≡1(mod~p) ab≡1(mod p)，则称 a a a为 b b b的乘法逆元，或称 b b b为 a a a的乘法逆元

乘法逆元的存在性定理：

若 a a a与 p p p互质，则⼀定存在⼀个正整数解 b b b，满⾜ b b b < p p p。

若 a a a与 p p p不互质，则⼀定不存在正整数解 b b b。

费马小定理

在 p p p为素数时，对于任意整数 x x x都有 x p ≡ x ( m o d   p ) x^{p}≡x(mod~p) xp≡x(mod p)，此定理为费马小定理。

如果 x x x无法被 p p p整除，有 x p − 1 ≡ 1 ( m o d   p ) x^{p-1}≡1(mod~p) xp−1≡1(mod p)

等价为 x ∗ x p − 2 ≡ 1 ( m o d   p ) x*x^{p-2}≡1(mod~p) x∗xp−2≡1(mod p)

可以得到 x − 1 ≡ x p − 2 ( m o d   p ) x^{-1}≡x^{p-2}(mod~p) x−1≡xp−2(mod p)

结论：当 p p p为素数时，有 ( a ÷ b )   m o d   p = ( a   m o d   p × b p − 2   m o d   p )   m o d   p (a\div b)~mod~p=(a~mod~p\times b^{p-2}~mod~p)~mod~p (a÷b) mod p=(a mod p×bp−2 mod p) mod p

可以利用快速幂来求出逆元，复杂度为 O ( l o g n ) O(logn) O(logn)

欧拉函数

φ ( m ) = \varphi(m)= φ(m)=不超过 m m m并且和 m m m互素的数的个数

对于和 m m m互素的 x x x，有

x φ ( m ) ≡ 1   ( m o d   m ) x^{\varphi(m)}≡1~(mod~m) xφ(m)≡1 (mod m)

等价为 x ∗ x φ ( m ) − 1 ≡ 1   ( m o d   m ) x*x^{\varphi(m)-1}≡1~(mod~m) x∗xφ(m)−1≡1 (mod m)

根据逆元的定义式，有

x − 1 ≡ x φ ( m ) − 1   ( m o d   m ) x^{-1}≡x^{\varphi(m)-1}~(mod~m) x−1≡xφ(m)−1 (mod m)

结论： ( a ÷ b )   m o d   p = ( a × b φ ( p ) − 1 )   m o d   p = ( a   m o d   p × b φ ( p ) − 1   m o d   p )   m o d   p (a\div b)~mod~p=(a\times b^{\varphi(p)-1})~mod~p=(a~mod~p\times b^{\varphi(p)-1}~mod~p)~mod~p (a÷b) mod p=(a×bφ(p)−1) mod p=(a mod p×bφ(p)−1 mod p) mod p

求解 φ ( n ) \varphi(n) φ(n)的时间复杂度为 O ( n ) O(\sqrt n) O(n

​)，求出 φ ( n ) \varphi(n) φ(n)后可以利用快速幂来求出逆元，用这种方法求逆元的时间复杂度为 O ( n ∗ l o g n ) O(\sqrt n*logn) O(n

​∗logn)

求解欧拉函数值的代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int euler_phi(int n)
{
	int res = n;
	for (int i = 2; i * i <= n; i++){
		if (n % i == 0){
			res = res / i * (i - 1);
			for ( ; n % i == 0; n /= i);
		}
	}	
	if (n != 1)
		res = res / n * (n - 1);
	return res;
}

int main(void)
{
	int n;
	cin >> n; 
	int ans = euler_phi(n);
	cout << ans << endl;
	return 0;
}
           

扩展欧几里得算法

常用于求 a x + b y = g c d ( a , b ) ax + by=gcd(a,b) ax+by=gcd(a,b)的一组可行解。返回值为 g c d ( a , b ) gcd(a,b) gcd(a,b)，同时计算出 x x x和 y y y。

可以用于求解逆元，根据逆元的定义： a x ≡ 1 ( m o d   b ) ax≡1(mod~b) ax≡1(mod b)

可以得出不定方程： a x + b y = 1 ax+by=1 ax+by=1

当 g c d ( a , b ) = 1 gcd(a,b)=1 gcd(a,b)=1时，上述方程一定有解，所以一定存在一个 x x x为 a a a的乘法逆元。

将 a 、 b a、b a、b的值代入方程 a x + b y = 1 ax+by=1 ax+by=1，就可以利用扩展欧几里得算法解出这个方程，解出的 x x x即为 a a a的乘法逆元。

用该算法求出的 ∣ x ∣ + ∣ y ∣ |x|+|y| ∣x∣+∣y∣是最小的。如果 a b ≠ 0 ab\neq 0 ab​=0，还可以知道 ∣ x ∣ ≤ b 且 ∣ y ∣ ≤ a |x|\leq b且|y|\leq a ∣x∣≤b且∣y∣≤a，但并不能保证 x x x是正数，需要进行 x = ( b + x % b ) % b x=(b+x\%b)\%b x=(b+x%b)%b这样的操作来得到最小正整数 x x x

这个算法的时间复杂度为 O ( l o g n ) O(logn) O(logn)

扩展欧几里得算法求逆元的代码

#include <cstdio>
#include <iostream>
using namespace std;

int exgcd(int a, int b, int& x, int& y)
{
	int d = a;
	if (b != 0){
		d = exgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else{
		x = 1;
		y = 0;
	}
	return d;
}

int main(void)
{
	int a, b, x, y;
	cin >> a >> b;
	cout << exgcd(a, b, x, y) << endl;
	x = (b + x % b) % b;
	cout << x << endl;
	 
	return 0;
}
           

线性求逆元

此部分内容转载自：https://www.cnblogs.com/qdscwyy/p/7795368.html

设 p = k ∗ i + r ， ( r < i ， 1 < i < p ) p=k*i+r，(r<i，1<i<p) p=k∗i+r，(r<i，1<i<p)

将式子放到 m o d   p mod ~p mod p意义下，有

k ∗ i + r ≡ 0   ( m o d   p ) k*i+r≡0~(mod~p) k∗i+r≡0 (mod p)

两边同乘 i − 1 ∗ r − 1 i^{-1}*r^{-1} i−1∗r−1，得

k ∗ r − 1 + i − 1 ≡ 0   ( m o d   p ) k*r^{-1}+i^{-1}≡0~(mod~p) k∗r−1+i−1≡0 (mod p)

移项，得

i − 1 ≡ − k ∗ r − 1   ( m o d   p ) i^{-1}≡-k*r^{-1}~(mod~p) i−1≡−k∗r−1 (mod p)

用已知的 p 、 i p、i p、i表示 k 、 r k、r k、r，得

i − 1 ≡ − ⌊ p i ⌋ ∗ ( p   m o d   i ) − 1   ( m o d   p ) i^{-1}≡-\lfloor \frac{p}{i} \rfloor*(p~mod~i)^{-1}~(mod~p) i−1≡−⌊ip​⌋∗(p mod i)−1 (mod p)

根据上面推出的公式，可以用前面的逆元推出当前的逆元

用式子表示时，负数取模的值等于加模数到正数后再取模的值，而写程序时不能直接用负数来计算，需要先加一个模数使其为正，就像下面这样

此方法适用于求从1——n连续的逆元，时间复杂度为 O ( n ) O(n) O(n)

线性求解逆元的代码

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 3e6 + 5;
typedef long long ll;

ll inv[N];

void pre(int p)
{
	inv[1] = 1;
	for (int i = 2; i <= N - 5; i++)
		inv[i] = ((p - p / i) * inv[p % i]) % p;
}

int main(void)
{
	int n, p;
	scanf("%d%d", &n, &p);
	pre(p);
	for (int i = 1; i <= n; i++)
		printf("%lld\n", inv[i]);
	
	return 0;
}