n 是素數使得 n 未能通過 Miller-Rabin 檢驗 N 次的機率
我正在閱讀數學密碼學簡介，其中一個練習要求
假設我們對整數 n 執行 Miller-Rabin 檢驗 N 次，並且它未能證明 n 是合數。證明 n 是素數的機率滿足（近似）
镨( $ n $ 是素數 $ \mid $ 米勒-拉賓檢驗失敗 $ N $ 次） $ \geq 1 − \frac{ln(n)}{4^N} $ .
這是假設 Miller-Rabin 檢驗的準確率為 75%，並且機率 $ n $ 是素數是 $ \frac{1}{ln(n)} $ . 我認為“在數字上失敗”意味著他們將數字辨識為素數。（未能將其辨識為複合材料。）
基於假設，我發現以下內容：
讓 $ n $ 是 ” $ n $ 是素數”和 $ N $ 是“米勒-拉賓檢驗失敗 $ N $ 次”。因為測試總是在素數上失敗， $ P(N \mid n)=1 $ . $ P(n)=\frac{1}{ln(n)} $ 如上所述，和 $ P(N \mid n^c)=(\frac{1}{4})^N $ 因為測試將復合物辨識為素數 $ \frac{1}{4} $ 的時間。
由此，我可以使用以下事實 $ P(n \mid N)=\frac{P(N \mid n)P(n)}{P(N \mid n)P(n) + P(N \mid n^c)P(n^c)} $ 去尋找
$$ P(n \mid N)=\frac{\frac{1}{ln(n)}}{\frac{1}{ln(n)} + (\frac{1}{4^N})(1-\frac{1}{ln(n)})}\ =\frac{\frac{1}{ln(n)}}{\frac{1}{ln(n)} + \frac{1}{4^N}-\frac{1}{4^Nln(n)}}\ =\frac{\frac{4^N}{ln(n)}}{\frac{4^N}{ln(n)} + 1-\frac{1}{ln(n)}}\ =\frac{4^N}{4^N + ln(n)-1}\ $$ 但這似乎並沒有讓我到任何地方。我在這裡想念什麼？
再走一步，你的最後一個表情是
$$ \frac{4^N}{4^N +\ln(n)-1}=1-\frac{\ln n -1}{4^N+\ln n -1}\geq 1-\frac{\ln n -1}{4^N}\geq 1-\frac{\ln n}{4^N}. $$