初等數論--同餘--Fermat素性檢測算法（為什麼每次機率改變1/2）

• 為什麼每次機率改變1/2

部落客是初學初等數論（整除+同餘+原根），本意是想整理一些較難了解的定理、算法，加深記憶也友善日後查找；如果有錯，歡迎指正。

我整理成一個系列：初等數論，友善檢索。

費馬小定理，對于 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

為什麼每次機率改變1/2

• 事件 a a a：奇整數 n n n是合數
• 事件 a ′ a' a′：奇整數 n n n是素數
• 事件 b b b：連續回答 m m m次“ n n n是素數”

我們想計算的是 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−2N​lnNN​​=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]2​lnN−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