用sage编写Rabin-Miller算法对素数的检测

Sage是一个开源数学软件包，它提供了广泛的数学函数和工具，包括用于处理各种算法，如Rabin-Miller素数检验算法。Rabin-Miller算法是一种用于判断一个大整数是否可能是质数的概率性测试方法。以下是使用Sage如何实现该算法的一个简单示例：

from sage.crypto.number_theory.prime import is_prime

def rabin_miller_test(n, k=5):  # k通常是5次试验，可根据需要调整
    if n < 2 or (n % 2 == 0 and n != 2):
        return False, "Input must be an odd number greater than 1."
    
    # Miller-Rabin test implementation
    witnesses = []  # List of witness integers
    for _ in range(k):
        a = random.randint(2, n - 2)  # Choose a random integer as the witness
        x = pow(a, n - 1, n)  # Compute x = a^(n-1) mod n
        
        if x != 1 and x != n - 1:  # Not a trivial divisor
            for _ in range(log2(n)):  # Perform modular squaring
                x = x * x % n
                if x == n - 1:
                    break
            else:  # Squaring did not reach 1
                witnesses.append(False)
                return False, f"{a} is a witness that {n} might not be prime."
        
    if len(witnesses) == k:  # All tests passed
        witnesses.append(True)
        return True, None
    
    return witnesses, f"Possible witnesses: {witnesses}"

# 使用示例
num = int(input("Enter a number to test: "))
result, message = rabin_miller_test(num)
if result:
    print(f"{num} is probably prime ({message}).")
else:
    print(f"{num} is composite ({message}).")

在这个例子中，我们首先检查输入是否满足Rabin-Miller的要求，然后通过多次随机选择测试点（`a`），计算`a^(n-1) mod n`，如果结果不符合特定模式，则认为`n`不是素数。请注意，虽然这个测试可以提供很高的概率保证，但并非绝对确定。