博主是初学初等数论（整除+同余+原根），本意是想整理一些较难理解的定理、算法，加深记忆也方便日后查找；如果有错，欢迎指正。 我整理成一个系列：初等数论，方便检索。
费马小定理，对于 a ∈ Z , p a\in Z,p a∈Z,p为素数,有 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv 1(mod p) ap−1≡1(modp)
这是由已知素数推公式，那么如果已有公式呢？能推测p就一定是素数吗？这就是费马素性检测算法要告诉我们的内容，p是素数的概率。
伪素数：如果 n n n是奇合数，对于 b ∈ Z , b\in Z, b∈Z,有 b n − 1 ≡ 1 ( m o d n ) , b^{n-1}\equiv 1(mod n), bn−1≡1(modn),那么称 n n n是对于基 b b b的伪素数。(伪素数不能单独存在，一定是针对某一个基成立的性质)
算法流程： 给定某一奇整数 n ≥ 3 n\ge 3 n≥3和安全参数 k k k，即检测不超过 k k k次。
随机取某一整数 b b b,令 g = ( b , n ) g=(b,n) g=(b,n),如果 g ≠ 1 g\neq1 g=1,则" n n n为合数";令 h = b n − 1 ( m o d n ) h=b^{n-1}(mod n) h=bn−1(modn),如果 h ≠ 1 h\neq 1 h=1,则" n n n为合数";如果以上两条皆不满足，那么" n n n可能为素数";重复 k k k次，如果得到一次" n n n为合数"，则 n n n为合数；若每次都得到" n n n可能为素数",则 n n n为素数的概率为 1 − 1 2 k 1-\frac1{2^k} 1−2k1我有一个问题还没有解决，为什么是 1 2 k , \frac1{2^k}, 2k1,素数合数的分布是不均匀的，为什么能用 1 2 \frac{1}{2} 21来考虑呢？
答案来源于 Cryptography Theory and Practice
我们想计算的是 P r [ a ] [ b ] Pr[a][b] Pr[a][b]，利用贝叶斯定理，从 P r [ b ] [ a ] 和 P r [ a ] Pr[b][a]和Pr[a] Pr[b][a]和Pr[a]来推出。
P r [ b ] [ a ] ： Pr[b][a]： Pr[b][a]：假如奇整数 n n n是合数，那么“回答一次 n n n是素数”的概率 ≤ 1 / 2 \le 1/2 ≤1/2,“连续回答 m m m次 n n n是素数”的概率 ≤ 2 − m \le 2^{-m} ≤2−m,即 P r [ b ] [ a ] ≤ 2 − m Pr[b][a]\le 2^{-m} Pr[b][a]≤2−m P r [ a ] ： Pr[a]： Pr[a]：设 N ≤ n ≤ 2 N , N\le n\le2N, N≤n≤2N,需要知道的是 N ∼ 2 N N\sim2N N∼2N间共有多少个奇整数，又有多少个素数，再计算概率。 N ∼ 2 N N\sim 2N N∼2N奇整数个数： 2 N − N 2 = N 2 \frac{2N-N}{2}=\frac{N}{2} 22N−N=2N N ∼ 2 N N\sim 2N N∼2N素数个数：由素数定理，我们知“ ≤ N \le N ≤N的素数共有 N l n N \frac{N}{ln N} lnNN个”，所以： 2 N l n 2 N − N l n N = 2 N l n N + l n 2 − N l n N ( \\ \frac{2N}{ln 2N}-\frac{N}{ln N}\\ =\frac{2N}{ln N+ln 2}-\frac{N}{ln N}( ln2N2N−lnNN=lnN+ln22N−lnNN(因为 N ≫ 2 , N\gg 2, N≫2,所以 l n N + l n 2 ≈ l n N ln N+ln 2\approx ln N lnN+ln2≈lnN) ≈ 2 N l n N − N l n N = N l n N \\ \approx \frac{2N}{ln N}-\frac{N}{ln N}\\ =\frac{N}{ln N} ≈lnN2N−lnNN=lnNN n n n是合数的概率： P r [ a ] = 1 − N l n N N 2 = 1 − 2 l n N Pr[a]=1-\frac{\frac{N}{ln N}}{\frac{N}{2}}=1-\frac{2}{ln N} Pr[a]=1−2NlnNN=1−lnN2 P r [ a ] [ b ] ： Pr[a][b]： Pr[a][b]：由贝叶斯定理知： P r [ a ] [ b ] = P r [ a b ] P r [ b ] = P r [ b ] [ a ] ⋅ P r [ a ] P r [ b ] = P r [ b ] [ a ] ⋅ P r [ a ] P r [ b ] [ a ] ⋅ P r [ a ] + P r [ b ] [ a ′ ] ⋅ P r [ a ′ ] \\ Pr[a][b]\\ =\frac{Pr[ab]}{Pr[b]}\\ =\frac{Pr[b][a]·Pr[a]}{Pr[b]}\\ =\frac{Pr[b][a]·Pr[a]}{Pr[b][a]·Pr[a]+Pr[b][a']·Pr[a']} Pr[a][b]=Pr[b]Pr[ab]=Pr[b]Pr[b][a]⋅Pr[a]=Pr[b][a]⋅Pr[a]+Pr[b][a′]⋅Pr[a′]Pr[b][a]⋅Pr[a] 因为 P r [ b ] [ a ′ ] = 1 , P r [ a ′ ] = 2 l n N Pr[b][a']=1,Pr[a']=\frac{2}{ln N} Pr[b][a′]=1,Pr[a′]=lnN2,所以 P r [ a ] [ b ] = P r [ b ] [ a ] ⋅ ( 1 − 2 l n N ) P r [ b ] [ a ] ⋅ ( 1 − 2 l n N ) + ( 2 l n N ) = P r [ b ] [ a ] ⋅ ( l n N − 2 ) P r [ b ] [ a ] ⋅ ( l n N − 2 ) + 2 = l n N − 2 l n N − 2 + 2 P r [ b ] [ a ] ( 因 为 P r [ b ] [ a ] ≤ 2 − m ) ≤ l n N − 2 l n N − 2 + 2 m + 1 \\ Pr[a][b]\\ =\frac{Pr[b][a]·(1-\frac{2}{ln N})}{Pr[b][a]·(1-\frac{2}{ln N})+(\frac{2}{ln N})}\\ =\frac{Pr[b][a]·(ln N-2)}{Pr[b][a]·(ln N-2)+2}\\ =\frac{ln N-2}{lnN-2+\frac{2}{Pr[b][a]}}(因为Pr[b][a]\le 2^{-m})\\ \le\frac{ln N-2}{lnN-2+2^{m+1}} Pr[a][b]=Pr[b][a]⋅(1−lnN2)+(lnN2)Pr[b][a]⋅(1−lnN2)=Pr[b][a]⋅(lnN−2)+2Pr[b][a]⋅(lnN−2)=lnN−2+Pr[b][a]2lnN−2(因为Pr[b][a]≤2−m)≤lnN−2+2m+1lnN−2 当 m m m很大时， P r [ a ] [ b ] ≤ 2 − ( m + 1 ) Pr[a][b]\le 2^{-(m+1)} Pr[a][b]≤2−(m+1),与 2 − m 2^{-m} 2−m的差距很小，可以近似，即 P r [ a ] [ b ] ≤ 2 − m Pr[a][b]\le 2^{-m} Pr[a][b]≤2−m,所以 n n n为素数的概率 ≥ 1 − 2 − m \ge 1-2^{-m} ≥1−2−m