歐幾里得演算法求逆
❶ 歐幾里德演算法是什麼啊
歐幾里德演算法
歐幾里德演算法又稱輾轉相除法，用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
證明：a可以表示成a = kb + r，則r = a mod b
假設d是a,b的一個公約數，則有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公約數
假設d 是(b,a mod b)的公約數，則
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公約數
因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證。
歐幾里德演算法就是根據這個原理來做的，其演算法用C++語言描述為：
void swap(int & a, int & b)
{
int c = a;
a = b;
b = c;
}
int gcd(int a,int b)
{
if(0 == a )
{
return b;
}
if( 0 == b)
{
return a;
}
if(a > b)
{
swap(a,b);
}
int c;
for(c = a % b ; c > 0 ; c = a % b)
{
a = b;
b = c;
}
return b;
}
參考資料：internet
❷ c語言，求一個數的逆的模n運算等於多少！
程序如下：
#include <conio.h>
#include <stdio.h>
int ExtEnclid(int d,int f)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,k;
if(d>f) d=d+f-(d=f); //交換d和f使得d<f
x1=1,x2=0,x3=f;
y1=0,y2=1,y3=d;
while(1)
{
if(y3==0)
{
return 0; //沒有逆元,gcd(d,f)=x3
}
if(y3==1)
{
return y2; //逆元為y2,gcd(d,f)=1
}
k=x3/y3;
t1=x1-k*y1, t2=x2-k*y2, t3=x3-k*y3;
x1=y1,x2=y2,x3=y3;
y1=t1,y2=t2,y3=t3;
}
}
int main()
{
int a, n, res;
printf("求 a^(-1) mod n 的值：\n");
printf("a = ");
scanf("%d", &a);
printf("n = ");
scanf("%d", &n);
res = ExtEnclid(a,n);
if (res == 0)
{
printf("Not Exist!\n");
getch();
return (0);
}
else if(res<0)
{
res = res + n;
}
printf("a^(-1) mod n = %d\n", res);
getch();
return (0);
}
計算1/x mod n =x^(-1) mod n
就是求y，滿足：
yx = 1 mod n
y是有限域F(n)上x的乘法逆元素
可用擴展的歐幾里得演算法求乘法逆元
擴展的歐幾里德演算法簡單描述如下：
ExtendedEuclid(d,f)
1 （X1,X2,X3):=(1,0,f)
2 (Y1,Y2,Y3):=(0,1,d)
3 if (Y3=0) then return d'=null//無逆元
4 if (Y3=1) then return d'=Y2 //Y2為逆元
5 Q:=X3 div Y3
6 (T1,T2,T3):=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3)
7 （X1,X2,X3):=(Y1,Y2,Y3)
8 (Y1,Y2,Y3):=(T1,T2,T3)
9 goto 3
❸ 歐幾里得演算法是什麼
歐幾里得演算法又稱輾轉相除法，是指用於計算兩個非負整數a，b的最大公約數。應用領域有數學和計算機兩個方面。計算公式gcd(a,b) = gcd(b,a mod b)。
輾轉相除法的演算法步驟為，兩個數中用較大數除以較小數，再用出現的余數除除數。
再用出現的余數（第二餘數）去除第一餘數，如此反復，直到最後余數是0為止。
輾轉相除法是利用以下性質來確定兩個正整數a和b的最大公因子的：
1、若r是a ÷ b的余數，且r不為0，則gcd(a,b) = gcd(b,r)。
⒉、a和其倍數之最大公因子為a。
另一種寫法是：
⒈、令r為a/b所得余數（0≤r），若r= 0，演算法結束；b即為答案。
⒉、互換：置a←b，b←r，並返回第一步。
❹ 歐幾里得輾轉相除法
輾轉相除法， 又名歐幾里德演算法（Euclidean algorithm），是求最大公約數的一種方法。它的具體做法是：用較大數除以較小數，再用出現的余數（第一餘數）去除除數，再用出現的余數（第二餘數）去除第一餘數，如此反復，直到最後余數是0為止。如果是求兩個數的最大公約數，那麼最後的除數就是這兩個數的最大公約數。 另一種求兩數的最大公約數的方法是更相減損法。輾轉相除法是用來計算兩個整數的最大公約數。假設兩個整數為a和b，他們的公約數可以表示為gcd(a,b)。如果gcd(a,b) = c,則必然a = mc和b = nc。a除以b得商和余數，余數r可以表示為r = a - bk，k這里是系數。因為c為 a和b的最大公約數，所以c也一定是r的最大公約數，因為r = mc - nck = (m-nk)c。
因此gcd(a,b) = gcd(b,r)，相當於把較大的一個整數用一個較小的余數替換了，這樣不斷地迭代，直到余數為0，則找到最大公約數。
舉例兩個整數為1071和462：
第一步：1071 / 462 = 2 * 462 + 147
第二步：462 / 147 = 3 * 147 + 21
第三步：147 / 21 = 7 * 21 + 0
此時余數為零，則21為兩個數的最大公約數。
貝祖公式表明對於任意兩個整數a和b，都可以找到一對可為負的整數x和y，可以使等式xa + yb = m，其中m為a和b的最大公約數，合理性稍加思考可得。如果m為1說明a和b互素。所以在互素的情況下，xa + yb = 1。這個等式對於求乘法逆元有很大的幫助。
那麼如何通過貝祖公式及擴展歐幾里得演算法來求乘法逆元呢？舉一個例子來描述什麼是乘法逆元。如果ab mod m = 1，或者可以表示為ab ≡ 1 mod m，這里b就是a關於模數m的乘法逆元。計算乘法逆元的方法就是擴展歐幾里得演算法，以下通過一個例子來幫助理解：
假設我們要求3 關於模26的乘法逆元(隱含了3和26的最大公約數為1，即互素)。當a = 3，b = 26，則根據貝祖公式，存在整數x和y，3x + 26y = 1。
思路就是等號兩邊同時mod 26，等式則變成(3x + 26y) mod 26 = 1 mod 26，根據模運算的性質(a + b) mod m = (a mod m + b mod m) mod m。
所以展開等式(3x mod 26 + 26y mod 26) mod 26 = 1 mod 26。化簡最終得到(3x mod 26) mod 26 = 1 mod 26。我們發現3x mod 26 = 1正好符合了乘法逆元的定義，所以歐幾里得演算法就是解x的關鍵。
下面將通過輾轉相除法來求x：
第一步：26 = 3 * 8 + 2
第二步：3 = 2 * 1 + 1
統一將余數換到等號左邊：
2 = 26 - 3 * 8
1 = 3 - 2 * 1
將第一行的2替換到第二行，保證等式左邊永遠為1，等式右邊變成僅由3x + 26y組成。
1 = 3 - (26 - 3 * 8) * 1 = 3 * 9 + (-1) * 26
可得x = 9
最後9就是3關於模26的乘法逆元。它可以應用於仿射加密。
附：仿射加密的公式e(x) = ax + b mod m， 其中a與m互素， b為移動距離。
仿射解密公式d(x) = a-1(x - b) mod m
❺ 擴展歐幾里得演算法求逆元演算法結果是負數
寫一句
d=(d%MOD+MOD)%MOD;
轉化成正數就可以了
❻ 急 歐幾里得演算法是什麼原理啊
在求兩個整數的最大公約數要用到歐幾里得演算法,簡單的說就是：
設A,B(A>B)最大公約數為k,則
A = k*A1
B = k*B1
所以
C = A-B*t = k*(A1-B1*t) (C<B)
得到
(A,B) == (C,B)
歐幾里德演算法
歐幾里德演算法又稱輾轉相除法，用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
證明：a可以表示成a = kb + r，則r = a mod b
假設d是a,b的一個公約數，則有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公約數
假設d 是(b,a mod b)的公約數，則
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公約數
因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證
歐幾里德演算法就是根據這個原理來做的，其演算法用C++語言描述為：
void swap(int & a, int & b)
{
int c = a;
a = b;
b = c;
}
int gcd(int a,int b)
{
if(0 == a )
{
return b;
}
if( 0 == b)
{
return a;
}
if(a > b)
{
swap(a,b);
}
int c;
for(c = a % b ; c > 0 ; c = a % b)
{
a = b;
b = c;
}
return b;
}
模P乘法逆元
對於整數a、p，如果存在整數b，滿足ab mod p =1，則說，b是a的模p乘法逆元。
定理：a存在模p的乘法逆元的充要條件是gcd(a,p) = 1
證明：
首先證明充分性
如果gcd(a,p) = 1，根據歐拉定理，aφ(p) ≡ 1 mod p，因此
顯然aφ(p)-1 mod p是a的模p乘法逆元。
再證明必要性
假設存在a模p的乘法逆元為b
ab ≡ 1 mod p
則ab = kp +1 ，所以1 = ab - kp
因為gcd(a,p) = d
所以d | 1
所以d只能為1
擴展歐幾里德演算法
擴展歐幾里德演算法不但能計算(a,b)的最大公約數，而且能計算a模b及b模a的乘法逆元，用C語言描述如下：
int gcd(int a, int b , int& ar,int & br)
{
int x1,x2,x3;
int y1,y2,y3;
int t1,t2,t3;
if(0 == a)
{//有一個數為0，就不存在乘法逆元
ar = 0;
br = 0 ;
return b;
}
if(0 == b)
{
ar = 0;
br = 0 ;
return a;
}
x1 = 1;
x2 = 0;
x3 = a;
y1 = 0;
y2 = 1;
y3 = b;
int k;
for( t3 = x3 % y3 ; t3 != 0 ; t3 = x3 % y3)
{
k = x3 / y3;
t2 = x2 - k * y2;
t1 = x1 - k * y1;
x1 = y1;
x1 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
if( y3 == 1)
{
//有乘法逆元
ar = y2;
br = x1;
return 1;
}else{
//公約數不為1，無乘法逆元
ar = 0;
br = 0;
return y3;
}
}
擴展歐幾里德演算法對於最大公約數的計算和普通歐幾里德演算法是一致的。計算乘法逆元則顯得很難明白。我想了半個小時才想出證明他的方法。
首先重復拙作整除中的一個論斷：
如果gcd(a,b)=d，則存在m,n，使得d = ma + nb，稱呼這種關系為a、b組合整數d，m，n稱為組合系數。當d=1時，有 ma + nb = 1 ，此時可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。
為了證明上面的結論，我們把上述計算中xi、yi看成ti的迭代初始值，考察一組數(t1,t2,t3)，用歸納法證明：當通過擴展歐幾里德演算法計算後，每一行都滿足a×t1 + b×t2 = t3
第一行：1 × a + 0 × b = a成立
第二行：0 × a + 1 × b = b成立
假設前k行都成立，考察第k+1行
對於k-1行和k行有
t1(k-1) t2(k-1) t3(k-1)
t1(k) t2(k) t3(k)
分別滿足：
t1(k-1) × a + t2(k-1) × b = t3(k-1)
t1(k) × a + t2(k) × b = t3(k)
根據擴展歐幾里德演算法，假設t3(k-1) = j t3(k) + r
則：
t3(k+1) = r
t2(k+1) = t2(k-1) - j × t2(k)
t1(k+1) = t1(k-1) - j × t1(k)
則
t1(k+1) × a + t2(k+1) × b
=t1(k-1) × a - j × t1(k) × a +
t2(k-1) × b - j × t2(k) × b
= t3(k-1) - j t3(k) = r
= t3(k+1)
得證
因此，當最終t3迭代計算到1時，有t1× a + t2 × b = 1，顯然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。
參考資料：
http://ke..com/view/795549.htm
❼ 擴展歐幾里得演算法求乘法逆元1234
Q X1 X2 X3 Y1 Y2 Y31 0 4321 0 1 12343 0 1 1234 1 -3 6191 1 -3 619 -1 4 6151 -1 4 615 2 -7 4153 2 -7 4 -307 1075 31 -307 1075 2 309 -1082 14321-1082=3239
❽ 用C語言編制的求模逆元的擴展歐幾里德演算法，只要能基本上實現這個功能就行
擴展歐幾里德演算法是用來在已知a, b求解一組x，y，使它們滿足貝祖等式： ax+by = gcd(a, b) =d（解一定存在，根據數論中的相關定理）。擴展歐幾里德常用在求解模線性方程及方程組中。
下面是一個使用C語言的實現：
intexGcd(inta,intb,int&x,int&y)
{
if(b==0)//當b==0時，得到解
{
x=1;y=0;
returna;
}
intr=exGcd(b,a%b,x,y);//遞歸調用自身，求解
intt=x;x=y;y=t-a/b*y;
returnr;
}
❾ 素數定理-歐幾里得演算法-乘法逆元
素數定理給出的是估計素數個數的方法：
設π(x)是小於x的素數的個數，則
π(x)≈x/lnx
eg：
64位二進製表示的素數的個數為
(1)歐拉定理
提及歐拉定理，需要先引出歐拉函數的定義：
歐拉函數Φ(n)是定義在正整數上的函數，Φ(n)的值等於序列0,1,2,3,…,n-1中與n互素的數的個數
歐拉函數的性質：
(1)m的素數時，有Φ(m)=m-1
(2)m=pq,且p和q均是素數時，有Φ(m)=Φ(p)Φ(q)=(p-1)(q-1)
(3)若m和n互素，則Φ(m×n)=Φ(m)×Φ(n)
(4)若p是一個素數，則Φ(p^e)=p^e-p^(e-1)
(5)
由歐拉函數可以延伸出歐拉定理的內容：
歐拉定理:
對於任何互素的兩個整數a和n，有
1(mod n)
如果n=p是素數,則有
1(mod p)
顯然歐拉定理可以看成是費馬定理的推廣形式。
歐拉定理可以用來簡化冪的模運算
Eg：
求 的後三位數字
解： (mod 1000)的結果
有 (mod 1000)
(2)費馬定理
如果p是素數，a是正整數，且gcd(a,p)=1，那麼
1(mod p)
另一種形式：
如果p是素數，a是任意正整數，則對gcd(a,p)=1,有
(mod p)
(3)二次探測定理
如果p是一個素數，且0<x<p,則方程 1(mod p)的解為 x = -1、p-1。
即如果符合 1(mod p)，那麼p很有可能是素數，但是仍不能肯定p就是素數。
(1)Wilson定理
對於給定的正整數n，判斷n是一個素數的充要條件是 -1(mod n)。
雖然是充要條件，且Wilson的定理有很高的的理論介質。因為帶有階乘，在檢測的時候計算量大，不適合檢測較大素數的檢測。
(2)米勒-拉賓演算法
米勒-拉賓演算法是一個多項式演算法，能以接近概率1保證判斷結果的正確性。
Miller-Rabin(n)
把n-1寫成 ，其中m是一個奇數
選取隨機整數a，使得
(mod n)
If (mod n)
Return (『n是素數』)
End
For i=0到k-1
If b≡-1(mod n)
Return (『n是素數』)
Else
b=b^2(mod n)
End
End
Return(『n是合數』)
歐幾里得演算法描述：
兩個整數用a，b表示，商用q表示，余數用r表示
Step1 取a，b較大者為a，較小者為b
Step2 做除法，計算並保留余數r=mod(a,b)
Step3 將原來的除數改做被除數，余數作為除數a=b,b=r
重復Step1和Step2直到r=0,返回b
乘法逆元的定義：
假設gcd(a,n)=1,則存在整數s，使得 (mod n)，即s是a(mod n)的乘法逆元素。
關於ax+by=d
設a和b是兩個正整數(至少有一個非零)，d=gcd(a,b),則存在整數x和y使得ax+by=d成立，如果a、b互素，那 么存在整數x和y使得ax+by=1成立，此時可以求出ax≡1(mod b)中的x，即為逆元。
擴展歐幾里得演算法：
構造兩個數列：
Eg：
求28mod75的乘法逆元(a=75,b=28)
gcd(28,75)=1 所以存在逆元
75=2×28+19
28=1×19+9
19=2×9+1
9=9×1+0
3×78+(-8)×28=1
所以28mod75的乘法逆元為-8
中國剩餘定理完整版
Eg：
已知下列同餘方程組，求解x
第一步：求M
M=2×3×5×7=210
第二步：求
第三步：求
1(mod )(i=1,2,...,k)
第四步:
(mod M)
(105×1×1+70×1×2+42×3×3+30×4×5)(mod 210)
173(mod 210)
❿ 用c語言編寫擴展歐幾里德演算法用來求乘法逆元ab=1 mod(n) 要求我輸入b，n，求出a。請編譯運行通過，謝謝啦
#include <stdio.h>
int ExtendedEuclid( int f,int d ,int *result);
int main()
{
int n,b,z;
z = 0;
printf("輸入兩個數：\n");
scanf("%d%d",&b,&n);
if(ExtendedEuclid(n,b,&z))
printf("%d和%d互素，乘法的逆元是：%d\n",b,n,z);
else
printf("%d和%d不互素，最大公約數為：%d\n",b,n,z);
return 0;
}
int ExtendedEuclid( int f,int d ,int *result)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;
x1 = y2 = 1;
x2 = y1 = 0;
x3 = ( f>=d )?f:d;
y3 = ( f>=d )?d:f;
while( 1 )
{
if ( y3 == 0 )
{
*result = x3; /* 兩個數不互素則result為兩個數的最大公約數，此時返回值為零 */
return 0;
}
if ( y3 == 1 )
{
*result = y2; /* 兩個數互素則resutl為其乘法逆元，此時返回值為1 */
return 1;
}
q = x3/y3;
t1 = x1 - q*y1;
t2 = x2 - q*y2;
t3 = x3 - q*y3;
x1 = y1;
x2 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
}
/*輸入兩個數：
5 14
5和14互素，乘法的逆元是：3
*/