乘法逆元，是指數學領域群G中任意一個元素a，都在G中有唯一的逆元a‘，具有性質a×a'=a'×a=e，其中e為該群的單位元。
基本介紹
- 中文名：乘法逆元
- 外文名：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 //整除
5。 (T1，T2，T3) := (X1 - Q*Y1，X2 - Q*Y2，X3 - Q*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;}