Python实现Miller-Rabin素性检测算法

Miller-Rabin素性检测是一种概率算法，用于判断一个大整数是否为素数。它基于费马小定理和二次探测定理，通过多次随机测试来提高判断的准确性。

算法原理：

对于一个奇整数n，我们首先将其表示为 n = 2^s * d + 1，其中d为奇数。2. 随机选择一个整数a (1 < a < n-1) 作为基。3. 进行以下测试： * 如果 a^d mod n = 1，则n可能是素数，继续进行下一步测试。 * 对于 r = 0, 1, ..., s-1，如果 a^(2^r * d) mod n = n-1，则n可能是素数，继续进行下一步测试。 * 否则，n是合数。4. 重复步骤2和3多次，如果每次测试都通过，则n很可能是素数。

**Python代码实现：**pythonimport random

def is_prime(n, k=5): ''' 使用Miller-Rabin素性检测算法判断一个整数是否为素数

参数：        n: 待判断的整数        k: 测试次数，默认为5

返回值：        如果n很可能是素数，则返回True，否则返回False    '''

if n <= 1:  # 小于等于1的数不是素数        return False    if n <= 3:  # 2和3是素数        return True    if n % 2 == 0:  # 偶数不是素数        return False

# 将n-1表示为2^s * d的形式    d = n - 1    s = 0    while d % 2 == 0:        d //= 2        s += 1

# 进行k次测试    for _ in range(k):        a = random.randint(2, n - 2)        x = pow(a, d, n)  # 计算a^d mod n

    if x == 1 or x == n - 1:            continue

    for _ in range(s - 1):            x = pow(x, 2, n)  # 计算a^(2^r * d) mod n            if x == n - 1:                break        else:            # 所有r都测试过，没有找到满足条件的，说明是合数            return False    # 所有测试都通过，说明n很可能是素数    return True

测试示例q = 9656184899794050073098614505490788837141112476549205418072011388278372195682566976277132351856116300104728124405389485440262266612903835574949734938773879p = 12253096079262730693787845304459770181159272160708761390419517461435886798119494973936186382645490774511179747402693066192362104144553287739427091488849987n = 1068394811940475700113916170772008310607904879176073274337669322446687936907143981238893756179197975634434673229920275765973807209412891205884402965483756254507691419368528133959132303476165747992107800736918701005971552264644185146124560027884795936191839406241406301141310602020436434278421529178345240902508007101551941438277539664839258109542374751444222500079818129540895166090788487787028178055561786822480872065405947357363186718845196587434430898650662917r = n / p / q

print(f'{p} is prime: {is_prime(p)}')print(f'{q} is prime: {is_prime(q)}')print(f'{int(r)} is prime: {is_prime(int(r))}')

代码说明:

is_prime(n, k=5) 函数接受两个参数：待判断的整数 n 和测试次数 k，默认为5。2. 函数首先处理一些特殊情况：小于等于1的数不是素数，2和3是素数，偶数不是素数。3. 然后，将 n-1 表示为 2^s * d 的形式，其中 d 为奇数。4. 接下来进行 k 次测试，每次测试都随机选择一个基 a，并进行费马小定理和二次探测定理的检验。5. 如果所有测试都通过，则认为 n 很可能是素数，返回 True，否则返回 False。

注意：

Miller-Rabin素性检测是一种概率算法，它并不能完全保证一个数是素数，只能说明一个数很可能是素数。测试次数 k 越多，判断的准确性越高，但同时也会增加计算时间。