Miller-rabin算法
素数判定法则
辅助定理
Fermat’s little theorem（费马小定理)
如果p是素数, a是正整数且不能被p整除
$a^{p - 1}$ ≡ 1 (mod p)
这个定理和欧拉定理的结论一致
对于任意互素的两个数a和n，设𝜑(n)为小于n且与n互素的正整数的个数，则有
对于 P = 𝜑(n)
$a^{P}$ ≡ 1 (mod p)
性质的证明
对于小于p的正整数的集合x
{1,….,p-1}, p与集合中的所有元素互素
用a乘以x中的元素并对p取模，我们可以得到集合X。
这里a为定理中定义的整数
{a mod p, 2a mod p,…, (p-1)a mod p}
集合X的性质为
-
任意元素都小于p
-
所有元素不等于0，而且互不相等
这与x的定义相同，从而可以得出
也就是两个集合相等，从而两个集合中的元素相乘的后结果的对p模余也相等，可以得出等式
(p - 1)! mod p = $a^{p-1}$ * (p - 1) mod p
两边约去 (p - 1)!,从而得到等式
1 mod p = $a^{p-1}$ mod p。
自然语言描述的结果就是如果a与p互素，
$a^{p-1}$ 的结果与1的模余相同。
等式两边乘以 a， 得到定理的扩展:
a mod p = $a^{p}$ mod p
Miller-rabin 素数判定法则
欧拉函数
欧拉函数φ(n):
对于正整数n，小于或等于n且与n互质的正整数的个数。
比如φ(6)，不超过6并且跟6互质的有1和5两个数，则φ(6)=2。
对于任意素数p，所有小于p的正整数都跟它互质，所以φ(p)=p−1。
另外，如果p和q均为素数，那么对于整数n=pq，有
φ(n)=φ(p)φ(q)=(p−1)(q−1)。
欧拉定理
如果a和m都是整数，并且互质，那么有：
$a^{φ(m)}$ ≡ 1 (mod m)
判定法则
TODO
