大素数生成算法python

大素数生成算法在Python中通常通过高效的随机化方法来实现，比如米勒-拉宾素数测试（Miller-Rabin Primality Test），配合一定的循环条件来找到质数候选。下面是一个简单的基于此方法的大素数生成示例：

import random

def is_prime(n, k=5):  # 米勒-拉宾测试，默认5次循环提高准确率
    if n < 2 or (n % 2 == 0 and n != 2):
        return False
    def witness(a):
        x = pow(a, n - 1, n)
        if x == 1 or x == n - 1:
            return True
        for _ in range(k):
            x = pow(x, 2, n)
            if x == n - 1:
                return True
        return False
    for _ in range(k):
        a = random.randint(2, n - 2)
        if not witness(a):
            return False
    return True

def generate_large_prime(bit_length):
    while True:
        candidate = 2 ** bit_length + 1  # 大于2^bit_length，增加奇数部分
        if is_prime(candidate):
            return candidate

# 使用示例
large_prime = generate_large_prime(100)  # 生成位长为100的素数
print("Generated large prime:", large_prime)