Почему моя реализация алгоритма Миллера-Рабина не в состоянии обнаружить некоторые простые числа?

Question

Я пытаюсь реализовать проверку простоты Миллера-Рабина для какого-то проекта, который я работаю.Однако алгоритм не работает для простых чисел, таких как 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)

ваш код будет работать - но довольно медленно для больших чисел. Чтобы улучшить код:

1. Используйте более простой метод вычисления odd_num и power_of_two
2. Используйте 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. Обработка ошибок не предназначена для обычного потока управления.