博客

miller_rabin

  • Post category:other

Miller-Rabin算法

Miller-Rabin算法是一种用于判断一个数是否为质数的算法。它是基于费马小定理和二次探测定理的，可以在多项式时间内完成判断。本文将提供一个完整攻略，介绍Miller-Rabin算法的原理和实现方法，并提供两个示例说明。

原理

Miller-Rabin算法的原理基于费马小定理和二次探测定理。费马小定理指出，如果p是一个质数，a是一个整数，那么a^(p-1) mod p = 1。二次探测定理指出，如果p是一个奇素数，那么对于任意一个整数a，存在一个整数x，使得x^2 mod p = a mod p。

Miller-Rabin算法的基本思想是，对于一个待判断的数n，我们随机选择一个整数a，然后判断a^(n-1) mod n是否等于1。如果等于1，那么n可能是一个质数；否则，我们继续计算a^(2(n-1)) mod n、a^(4(n-1)) mod n、a^(8(n-1)) mod n，直到计算出来的结果等于1或者n-1为止。如果最终结果等于1，那么n可能是一个质数；否则，n一定是一个合数。

实现

可以按照以下步骤实现Miller-Rabin算法：

  1. 将n-1分解为2^s * d的形式，其中d是一个奇数。
def decompose(n):
    s = 0
    while n % 2 == 0:
        s += 1
        n //= 2
    return s, n

在这个示例中，我们定义了一个名为decompose的函数，用于将n-1分解为2^s * d的形式。需要注意的是，我们使用了Python中的整数除法运算符//，以确保结果是一个整数。

  1. 判断a^(d*2^r) mod n是否等于1或者n-1。
def test(a, d, n, r):
    x = pow(a, d, n)
    if x == 1 or x == n - 1:
        return True
    for i in range(r - 1):
        x = pow(x, 2, n)
        if x == n - 1:
            return True
    return False

在这个示例中，我们定义了一个名为test的函数，用于判断a^(d*2^r) mod n是否等于1或者n-1。需要注意的是，我们使用了Python中的pow函数来计算幂运算，以确保结果是一个整数。

  1. 随机选择一个整数a，并进行多次测试。
import random

def is_prime(n, k=10):
    if n == 2 or n == 3:
        return True
    if n <= 1 or n % 2 == 0:
        return False
    s, d = decompose(n - 1)
    for i in range(k):
        a = random.randint(2, n - 2)
        if not test(a, d, n, s):
            return False
    return True

在这个示例中，我们定义了一个名为is_prime的函数，用于判断一个数是否为质数。需要注意的是，我们使用了Python中的random模块来生成随机数，以确保测试的随机性和多样性。

示例1：判断一个数是否为质数

在这个示例中，我们将使用Miller-Rabin算法判断一个数是否为质数。可以按照以下步骤实现：

n = 123456789
if is_prime(n):
    print(n, 'is prime')
else:
    print(n, 'is composite')

在这个示例中，我们使用了之前定义的is_prime函数来判断一个数是否为质数。需要注意的是，我们使用了Python中的if语句来根据测试结果输出相应的信息。

示例2：生成一定范围内的质数

在这个示例中，我们将使用Miller-Rabin算法生成一定范围内的质数。可以按照以下步骤实现：

def generate_primes(start, end, k=10):
    primes = []
    for n in range(start, end + 1):
        if is_prime(n, k):
            primes.append(n)
    return primes

primes = generate_primes(100, 200)
print(primes)

在这个示例中，我们定义了一个名为generate_primes的函数，用于生成一定范围内的质数。需要注意的是，我们使用了Python中的range函数来生成待测试的数，以及列表来存储测试通过的质数。

Tags: