Чтобы определить, является ли число простым, существуют различные методы. Одним из популярных вероятностных тестов простоты является тест простоты Миллера-Рабина. В этой статье мы углубимся в детали теста Миллера-Рабина, объясним его внутреннюю работу и предоставим примеры кода Python для его реализации. К концу вы получите четкое представление о тесте на простоту Миллера-Рабина и о том, как его использовать в своих проектах.

Содержание:

1. Что такое тест на простоту Миллера-Рабина?

2. Обзор алгоритма Миллера-Рабина

3. Реализация на Python
   а. Метод 1: базовая реализация
   b. Способ 2. Оптимизированная реализация

4. Примеры использования и тестовые примеры

5. Вывод

6. Что такое тест на простоту Миллера-Рабина?
   Тест на простоту Миллера-Рабина — это алгоритм, используемый для определения того, является ли данное число простым или составным. В отличие от детерминистических тестов, таких как Решето Эратосфена или пробное деление, тест Миллера-Рабина дает вероятностный результат с высоким уровнем точности.

7. Обзор алгоритма Миллера-Рабина:
   Алгоритм Миллера-Рабина основан на Малой теореме Ферма и опирается на концепцию чисел-свидетелей. Номер-свидетель — это число, которое может определить, является ли данное число составным. Алгоритм неоднократно применяет модульное возведение в степень для проверки различных чисел свидетелей и получения результата.

8. Реализация на Python:
   а. Способ 1: базовая реализация:

   def miller_rabin_test(n, k):
   if n == 2 or n == 3:
       return True
   if n <= 1 or n % 2 == 0:
       return False
   def check_composite(a, d, r, n):
       x = pow(a, d, n)
       if x == 1 or x == n - 1:
           return False
       for _ in range(r - 1):
           x = pow(x, 2, n)
           if x == n - 1:
               return False
       return True
   d, r = n - 1, 0
   while d % 2 == 0:
       d //= 2
       r += 1
   for _ in range(k):
       a = random.randint(2, n - 2)
       if check_composite(a, d, r, n):
           return False
   return True

б. Способ 2. Оптимизированная реализация:

def miller_rabin_test(n, k):
    if n == 2 or n == 3:
        return True
    if n <= 1 or n % 2 == 0:
        return False
    def check_composite(a, d, n):
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            return False
        while d != n - 1:
            x = pow(x, 2, n)
            d *= 2
            if x == 1:
                return True
            if x == n - 1:
                return False
        return True
    r = 0
    d = n - 1
    while d % 2 == 0:
        d //= 2
        r += 1
    for _ in range(k):
        a = random.randint(2, n - 2)
        if check_composite(a, d, n):
            return False
    return True

4. Примеры использования и тестовые примеры:

   # Example usage
   number = 997
   iterations = 5
   if miller_rabin_test(number, iterations):
   print(f"{number} is likely prime.")
   else:
   print(f"{number} is composite.")
   # Test cases
   assert miller_rabin_test(997, 5) == True
   assert miller_rabin_test(1000, 5) == False
   assert miller_rabin_test(2, 5) == True
   assert miller_rabin_test(1, 5) == False

5. В этой статье мы рассмотрели тест простоты Миллера-Рабина и его реализацию на Python. Мы предоставили как базовую, так и оптимизированную версию алгоритма, а также примеры использования и тестовые примеры. Тест Миллера-Рабина — мощный инструмент для вероятностного тестирования простоты, который можно использовать в различных приложениях, где требуется быстрая проверка простых чисел.