Ⅰ 素数定理-欧几里得算法-乘法逆元
素数定理给出的是估计素数个数的方法：
设π(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 基本是抄的