-
乘法逆元
鎖定
- 中文名
- 乘法逆元
- 外文名
- Multiplicative inverse modulo
- 適用領域
- 數學領域
- 定 義
- 羣G中任意一個元素a
- 例 如
- 4關於1模7的乘法逆元為多少
乘法逆元定義內容
羣G中任意一個元素a，都在G中有唯一的逆元a‘,具有性質aa'=a'a=e，其中e為羣的單位元。
乘法逆元舉例説明
例如：4關於1模7的乘法逆元為多少？
4X≡1 mod 7
這個方程等價於求一個X和K，滿足
4X=7K+1
其中X和K都是整數。
若ax≡1 mod f, 則稱a關於1模f的乘法逆元為x。也可表示為ax≡1(mod f)。
當a與f互素時，a關於模f的乘法逆元有解。如果不互素，則無解。如果f為素數，則從1到f-1的任意數都與f互素，即在1到f-1之間都恰好有一個關於模f的乘法逆元。
例如，求5關於模14的乘法逆元：
14=5*2+4
5=4*1+1
説明5與14互素，存在5關於14的乘法逆元。
1=5-4=5-(14-5*2)=5*3-14
因此，5關於模14的乘法逆元為3。
其求法可用歐幾里德算法：
Extended Euclid (d，f) //算法求d關於模f的乘法逆元d-1 ，即 d* d-1 mod f = 1
1 。(X1，X2，X3) := (1，0，f)； (Y1，Y2，Y3) := (0，1，d)
2。 if (Y3=0) then return d-1 = null //無逆元
3。 if (Y3=1) then return d-1 = Y2 //Y2為逆元
4。 Q := X3 div Y3 //整除
6 。(X1，X2，X3) := (Y1，Y2，Y3)
7。 (Y1，Y2，Y3) := (T1，T2，T3)
8。 goto 2
常用於加密算法中，如仿射算法。
求此算法還可以使用費馬小定理
只不過侷限性比較大，要求模數是素數
a^(p-1)
1(mod p)
p要求是素數
那麼a^(p-2)就是a的乘法逆元
乘法逆元代碼實現
//C++:
inline long long extend_gcd(long long a, long long b, long long &x, long long &y)
{
if (a == 0 && b == 0)
return -1ll;
if (b == 0)
{
x = 1ll;
y = 0ll;
return a;
}
long long d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
inline long long mod_reverse(long long a, long long n)
{
long long x, y, d = extend_gcd(a, n, x, y);
if (d == 1)
{
if (x % n <= 0)
return x % n + n;
else
return x % n;
}
else
return -1ll;
}
//Python:
def ext_euclid(a, b):
old_r, r = a, b
old_s, s = 1, 0
old_t, t = 0, 1
if b == 0:
return 1, 0, a
else:
while (r != 0):
q = old_r // r
old_r, r = r, old_r - q * r
old_s, s = s, old_s - q * s
old_t, t = t, old_t - q * t
return old_s, old_t, old_r
def inv(a, p):
_a, _, _ = ext_euclid(a, p)
return ((_a % p) + p) % p
