資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究什麼是用於測試給定數字素數性的米勒-拉賓演算法？
米勒-拉賓是一種快速測試大數素數性的方法。該演算法被稱為拉賓-米勒素性檢驗，它決定一個數是否為素數，這與其他檢驗相同，包括費馬素性檢驗和索洛維-施特拉森素性檢驗。
此測試基於對素數值成立的等式或等式組，因此檢查它們是否對需要測試素數性的數字成立。
該演算法是最有用的已知素性測試演算法，可用於基於 RSA 加密的不同軟體庫，最好的例子是 OpenSSL。
米勒-拉賓驗證該數字是合數。因此，這被稱為合數檢驗而不是素數檢驗。米勒-拉賓檢驗識別所有合數。對於每個合數 n，至少有 3/4（米勒-拉賓）的數字 a 是 n 的合數的見證。
米勒-拉賓是費馬小定理的簡單擴充套件，它使我們能夠以比費馬小定理更大的機率測試素數性。
演算法：米勒-拉賓檢驗的虛擬碼 -
Miller-Rabin-Test (n, a) // n is the number; a is the base{
Find m and k such that n − 1 = m x 2k
T ← am mod n
If (T = ±1)return "a prime"
for (i ← 1 to k − 1) // k – 1 is the maximum number of steps{
T ← T2 mod n
if (T = ±1) return "a composite"
if (T = −1) return "a prime"
}
return "a composite"
}存在一個證明，每次一個數字透過米勒-拉賓檢驗時，它不是素數的機率為 1/4。如果該數字透過 m 次檢驗（使用 m 個不同的傳遞），則它不是素數的機率為 (1/4)m。
示例：使用基數 2 應用米勒-拉賓演算法來測試數字 341 是否為合數。
解決方案：使用米勒-拉賓演算法，我們可以如下測試數字 341 -
步驟 1：341 - 1 = 22 x 85。因此 p = 341，k = 2 且 q = 85
步驟 2：x = 2（給定）
步驟 3：S = xq mod p
= 285 mod 341 = (210) x 25 mod 341 8
= 210 mod 341 x 213 mod 341
= 1 x 8192 mod 341 = 8192 mod 341
= 8
步驟 4：由於 8 ≠ 1，我們轉到下一步。
步驟 5：對於 j = 1，S = x2q mod p
= 2170 mod 341 = (220)8 x 210 mod 341
= 220 mod 341 x 28 mod 341 x 210 mod 341
= 1 x 256 x 1 = 256
現在，= 256 ≠ 1
結果不確定
因此，341 不是合數。
優點
此演算法可用於測試高數字的素數性。
由於與其他素數檢驗相比速度更快，因此米勒-拉賓檢驗將成為多種密碼學應用的首選檢驗。
與尤拉和索洛維-施特拉森檢驗相比，米勒-拉賓更具動態性，並且其基本方面是降低了失敗的機率。
根據費馬檢驗，對於所有卡邁克爾數 n，存在太多說謊者，錯誤機率接近 1，米勒-拉賓避免了此缺點。
9K+ 次檢視
