1. 歐幾里德演算法是什麼啊
歐幾里德演算法
歐幾里德演算法又稱輾轉相除法，用於計算兩個整數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
2. 擴展歐幾里得演算法求乘法逆元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
3. 在有限域中怎麼求一個多項式的逆元
把生成這個有限域的生成多項式作為模多項式，用輾轉相除法（歐幾里得演算法）不停模生成多項式得余式直到1（肯定是1啊，因為給出的多項式有逆元，和模多項式互質的）。（可能模多項式次數比給出的多項式次數高，第一步除以模多項式，商式是0，余式是給出的多項式）
然後如同求ax=1(mod m)一樣反向進行，把1用模多項式和給出的多項式的「線性組合」表示出來，給出的多項式的「系數」多項式就是這個多項式的逆元啦。
可以檢查一下算錯沒有，求出逆元後和給出的多項式在模生成多項式下相乘，看是否等於1。
過程中涉及多項式長除法，挺費紙的。
我在網路搜到幾篇博客，都是通過mod（x^(n/2)）找到與mod(x^n)的關系，求解方法還涉及FFT,這應該屬於偏工程的演算法吧，沒仔細看不是很清楚。
4. 歐幾里得輾轉相除法
輾轉相除法， 又名歐幾里德演算法（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
5. 【總結】逆元的求法
即
由費馬小定理得：
那麼將就可以將 拆成 ，得：
根據逆元的定義 就是 的逆元
然而 就可以用快速冪來求
source:
根據上面對逆元的解釋：
利用擴展歐幾里得演算法：
那麼對於數 的逆元就是用擴歐找到一個 使
source:
以下公式都應該是在模p意義下的
因為
即
挪一下再調個邊
那麼
，這數學公式用的好爽！
參考博客： boshi 基本是抄的
6. 用c語言編寫擴展歐幾里德演算法用來求乘法逆元ab=1 mod(n) 要求我輸入b，n，求出a。請編譯運行通過，謝謝啦
這是一個錯誤的演算法啊
7. 點的逆元怎麼求
1、首先可以使用擴展歐幾里得演算法求點的逆元。
2、其次可以使用費馬小定理或者歐拉定理求點的逆元。
3、最後可以使用遞推求點的逆元。
8. 素數定理-歐幾里得演算法-乘法逆元
素數定理給出的是估計素數個數的方法：
設π(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)
9. 用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;
}