Ⅰ 素數定理-歐幾里得演算法-乘法逆元
素數定理給出的是估計素數個數的方法：
設π(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)
Ⅱ 【總結】逆元的求法
即
由費馬小定理得：
那麼將就可以將 拆成 ，得：
根據逆元的定義 就是 的逆元
然而 就可以用快速冪來求
source:
根據上面對逆元的解釋：
利用擴展歐幾里得演算法：
那麼對於數 的逆元就是用擴歐找到一個 使
source:
以下公式都應該是在模p意義下的
因為
即
挪一下再調個邊
那麼
，這數學公式用的好爽！
參考博客： boshi 基本是抄的