数据结构
网络
关系型数据库管理系统
操作系统
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+ 次查看
