数据结构
网络
关系数据库管理系统 (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 次浏览
