为什么我的 Miller-Rabin 算法无法检测到某些素数？

Question

我正在尝试为一些正在进行的项目实施 Miller-Rabin primality checker。但是，该算法不适用于101、103、107、109等素数......我无法弄清楚问题出在哪里。预先感谢所有帮助。

def miller_rabin_is_prime(number, k=10):

    if number < 2:
        return False
    elif number <= 3:
        return True

    else:
        odd_num, power_of_two, factor_out = 0, 0, number - 1

        while number != (2 ** power_of_two)*odd_num + 1:
            if factor_out / 2 == int(factor_out / 2):
                power_of_two += 1
                factor_out /= 2
            else:
                odd_num = (number - 1) / (2 ** power_of_two)

        for _ in range(k):
            random = randint(2, number - 2)
            checker = (random**odd_num) % number

            if (checker == 1) or (checker == number - 1):
                continue
            try:
                for loop in range(power_of_two - 1):
                    checker = (checker**2) % number
                    if checker == number - 1:
                        raise TypeError
            except TypeError:
                continue
            return False

        return True

我希望 101 的输出为 True，但实际输出为 False。

Answer 1

如果你更换

 odd_num = (number - 1) / (2 ** power_of_two)

来自

 odd_num = (number - 1) // (2 ** power_of_two)

您的代码可以工作 -- 但对于较大的数字来说相当慢。改进代码：

使用更简单的方法计算odd_num和power_of_two
使用 pow() 进行模幂运算。

类似于：

from random import randint
def miller_rabin_is_prime(number, k=10):

    if number < 2:
        return False
    elif number <= 3:
        return True

    else:
        odd_num = number - 1
        power_of_two = 0

        while odd_num % 2 == 0:
            power_of_two += 1
            odd_num //= 2

        for _ in range(k):
            random = randint(2, number - 2)
            checker = pow(random,odd_num, number)

            if (checker == 1) or (checker == number - 1):
                continue
            try:
                for loop in range(power_of_two - 1):
                    checker = pow(checker,2,number)
                    if checker == number - 1:
                        raise TypeError
            except TypeError:
                continue
            return False

        return True

然后，例如，miller_rabin_is_prime(1000003) 将几乎立即评估为 True，而您的原始代码（即使在 / 被 // 替换之后）将花费大约15 秒，因为非模幂。

最后一点，您正在对非错误条件使用错误处理（显然 checker == number - 1 时没有类型错误）。重构主循环使其不使用 try--except 会更清晰。错误处理不适用于普通控制流。

为什么我的 Miller-Rabin 算法无法检测到某些素数？

Why is my implementation of the Miller-Rabin algorithm not able to detect some primes?

python

math

primes

python-3.x