Miller-Rabin 素性检测算法详解及 Python 代码实现

Miller-Rabin 素性检测是一种概率算法，用于判断一个数是否为素数。该算法的原理是利用费马小定理和二次探测定理，通过随机选择一个数作为测试基，判断该数是否满足相应的条件。

算法原理

费马小定理： 如果 p 是素数，a 是与 p 互质的整数，那么 a^(p-1) ≡ 1 (mod p)。

二次探测定理： 如果 p 是素数，并且 a 是 p 的二次非剩余，那么 a^((p-1)/2) ≡ -1 (mod p)。

Miller-Rabin 算法利用这两个定理，通过随机选择一个数作为测试基，判断该数是否满足上述条件。如果满足，则认为该数可能是素数；如果不满足，则认为该数一定不是素数。

代码实现

import random
import math

def is_prime(n):
    d = n - 1
    k = 0
    while d % 2 == 0:
        d //= 2
        k += 1

    # 判断是否为素数
    for _ in range(5):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(k - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False

    return True

q = 9656184899794050073098614505490788837141112476549205418072011388278372195682566976277132351856116300104728124405389485440262266612903835574949734938773879
p = 12253096079262730693787845304459770181159272160708761390419517461435886798119494973936186382645490774511179747402693066192362104144553287739427091488849987
n = 1068394811940475700113916170772008310607904879176073274337669322446687936907143981238893756179197975634434673229920275765973807209412891205884402965483756254507691419368528133959132303476165747992107800736918701005971552264644185146124560027884795936191839406241406301141310602020436434278421529178345240902508007101551941438277539664839258109542374751444222500079818129540895166090788487787028178055561786822480872065405947357363186718845196587434430898650662917
r = n / p / q

s1 = is_prime(p)
s2 = is_prime(q)
s3 = is_prime(int(r))

print(s1)
print(s2)
print(s3)
print(r)

代码解释

is_prime(n) 函数：
- 输入参数 n 是要判断的数。
- 函数首先将 n-1 赋值给 d，并初始化 k 为 0。
- 循环遍历 d，直到 d 为奇数，每循环一次将 d 除以 2，并将 k 加 1。
- 循环结束后，d 为 n-1 的最大奇数因子，k 为 n-1 的 2 的因子个数。
- 接着，循环 5 次（5 次迭代通常足够判断一个数是否为素数）。
  - 在每次迭代中，随机生成一个介于 2 和 n-2 之间的整数 a 作为测试基。
  - 计算 a^d mod n，并将结果赋值给 x。
  - 如果 x 等于 1 或 n-1，则跳过当前迭代。
  - 否则，循环 k-1 次，每次计算 x^2 mod n，并将结果赋值给 x。
    - 如果 x 等于 n-1，则跳出循环。
    - 否则，说明 n 不是素数，返回 False。
- 如果循环完成所有 5 次迭代，则认为 n 是素数，返回 True。
主程序：
- 定义三个变量 q、p 和 n，分别存储三个大数。
- 计算 r = n / p / q。
- 使用 is_prime() 函数判断 p、q 和 r 是否为素数，并分别将结果存储在 s1、s2 和 s3 中。
- 输出 s1、s2、s3 和 r 的值。

注意

Miller-Rabin 算法是一种概率算法，不能完全确定一个数是否为素数。但是，当测试基的个数足够多时，该算法的准确率会非常高。
在代码中，我们只进行了 5 次迭代，这只是一个示例。在实际应用中，需要根据需要调整迭代次数。
在实际应用中，还需要注意代码的性能优化，以提高程序的运行速度。

应用

Miller-Rabin 素性检测算法在密码学、信息安全、数据加密等领域有着广泛的应用。它可以用来生成随机的素数，用于构建加密算法的密钥。

希望本文对你理解 Miller-Rabin 素性检测算法有所帮助。