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

• 為什么每次概率改變1/2

博主是初學初等數論（整除+同余+原根），本意是想整理一些較難理解的定理、算法，加深記憶也方便日后查找；如果有錯，歡迎指正。
我整理成一個系列：初等數論，方便檢索。

費馬小定理，對于$a\in Z,p$為素數,有$a^{p?1}\equiv 1(modp)$

這是由已知素數推公式，那么如果已有公式呢？能推測p就一定是素數嗎？這就是費馬素性檢測算法要告訴我們的內容，p是素數的概率。

偽素數：如果$n$是奇合數，對于$b\in Z,$有$b^{n?1}\equiv 1(modn),$那么稱$n$是對于基$b$的偽素數。(偽素數不能單獨存在，一定是針對某一個基成立的性質)

算法流程：
給定某一奇整數$n\ge 3$和安全參數$k$，即檢測不超過$k$次。

• 隨機取某一整數$b$,
• 令$g=(b,n)$,如果$g=1$,則"$n$為合數";
• 令$h=b^{n?1}(modn)$,如果$h=1$,則"$n$為合數";
• 如果以上兩條皆不滿足，那么"$n$可能為素數";
• 重復$k$次，如果得到一次"$n$為合數"，則$n$為合數；若每次都得到"$n$可能為素數",則$n$為素數的概率為$1?\frac{1}{2^k}$

我有一個問題還沒有解決，為什么是$\frac{1}{2^k},$素數合數的分布是不均勻的，為什么能用$\frac{1}{2}$來考慮呢？

答案來源于 Cryptography Theory and Practice

為什么每次概率改變1/2

• 事件$a$：奇整數$n$是合數
• 事件$a^{\prime }$：奇整數$n$是素數
• 事件$b$：連續回答$m$次“$n$是素數”

我們想計算的是$Pr[a][b]$，利用貝葉斯定理，從$Pr[b][a]和Pr[a]$來推出。

• $Pr[b][a]：$假如奇整數$n$是合數，那么“回答一次$n$是素數”的概率$\le 1/2$,“連續回答$m$次$n$是素數”的概率$\le 2^{?m}$,即$Pr[b][a]\le 2^{?m}$
• $Pr[a]：$設$N\le n\le 2N,$需要知道的是$N～2N$間共有多少個奇整數，又有多少個素數，再計算概率。
  • $N～2N$奇整數個數：$\frac{2N?N}{2}=\frac{N}{2}$
  • $N～2N$素數個數：由素數定理，我們知“$\le N$的素數共有$\frac{N}{lnN}$個”，所以：$$\begin{gathered} \frac{2N}{ln2N}?\frac{N}{lnN} \\ =\frac{2N}{lnN+ln2}?\frac{N}{lnN}( \end{gathered}$$因為$N?2,$所以$lnN+ln2\approx lnN$)$$\begin{gathered} \approx \frac{2N}{lnN}?\frac{N}{lnN} \\ =\frac{N}{lnN} \end{gathered}$$
  • $n$是合數的概率：$Pr[a]=1?\frac{\frac{N}{lnN}}{\frac{N}{2}}=1?\frac{2}{lnN}$
• $Pr[a][b]：$由貝葉斯定理知：$$\begin{gathered} 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^{\prime }]?Pr[a^{\prime }]} \end{gathered}$$
  因為$Pr[b][a^{\prime }]=1,Pr[a^{\prime }]=\frac{2}{lnN}$,所以$$\begin{gathered} Pr[a][b] \\ =\frac{Pr[b][a]?(1?\frac{2}{lnN})}{Pr[b][a]?(1?\frac{2}{lnN})+(\frac{2}{lnN})} \\ =\frac{Pr[b][a]?(lnN?2)}{Pr[b][a]?(lnN?2)+2} \\ =\frac{lnN?2}{lnN?2+\frac{2}{Pr[b][a]}}(因為Pr[b][a]\le 2^{?m}) \\ \le \frac{lnN?2}{lnN?2+2^{m+1}} \end{gathered}$$
  當$m$很大時，$Pr[a][b]\le 2^{?(m+1)}$,與$2^{?m}$的差距很小，可以近似，即$Pr[a][b]\le 2^{?m}$,所以$n$為素數的概率$\ge 1?2^{?m}$

總結

以上是生活随笔為你收集整理的初等数论--同余--Fermat素性检测算法（为什么每次概率改变1/2）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。