資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學米勒-拉賓素性測試的步驟是什麼？
米勒-拉賓素性測試結合了費馬測試和費馬根測試，是一種經典的尋找強偽素數的方法。在這個測試中，可以將 n – 1 寫成奇數 m 和 2 的冪的乘積。
$$\mathrm{n-1=m\, x\, 2^{k}}$$
以 a 為底的費馬測試可以表示為：
$$\mathrm{a^{n-1}\, =\, a^{m\, x\, 2k}=\left [ a^{m} \right ]^{2k}=\left [ a^{m} \right ]\frac{2^{2}\cdot \cdot \cdot 2}{K\, 次}}$$
換句話說，與其一步計算 an−1(mod n)，不如分 k+1 步進行。使用 k + 1 的優點是每一平方根步驟都可以實現。如果平方根測試失敗，則可以停止並宣告 n 為合數。
在每一步中，如果可以訪問（如果結果為 1），則可以驗證費馬測試是否透過，並且所有相鄰步驟組中的平方根測試是否滿足。
初始化
可以選擇一個底數 a 並計算 $\mathrm{T\, =\, a^{m}}$，其中 $\mathrm{m\, =\, \frac{n-1}{2^{k}}}$
如果 T 為 +1 或 -1，則宣告 n 是強偽素數並停止。因為如果 T 為 ±1，T 在下一步將變為 1，並保持 1 直到透過費馬測試。此外，T 通過了平方根測試，因為 T 在下一步可以為 1，而 1 的平方根（在下一步）為 ±1。
如果 T 為其他值，則無法確定 n 是素數還是合數，因此可以繼續下一步。
步驟1：我們對 T 平方
如果結果為 +1，則肯定知道費馬測試將透過，因為 T 在隨後的測試中保持為 1。但平方根測試沒有透過。因為 T 在此步驟中為 1，而在前一步中為 ±1 以外的值，所以可以宣告 n 為合數並停止。
如果結果為 -1，則可以理解 n 最終將透過費馬測試。也可以理解它將透過平方根測試，因為 T 在此步驟中為 -1，並在下一步變為 1。可以宣告 n 為強偽素數並停止。
如果 T 為其他值，則無法確定它是否是素數。繼續下一步。
步驟2 到步驟 K – 1
此步驟和所有後續步驟將繼續進行，直到步驟 2 和步驟 K -1 等於步驟 1。
步驟 K
此步驟不是必需的。如果已到達此步驟且尚未做出決定，則此步驟將不會提供任何資訊。如果此步驟的結果為 1，則費馬測試透過，但由於前一步的結果不是 ±1，因此平方根測試未透過。在步驟 k -1 之後，如果尚未停止，則可以宣告 n 為合數。米勒-拉賓測試需要從步驟 0 到步驟 K-1。
464 次瀏覽
