Тест простоти Міллера — Рабіна

Визначення

Тест простоти Міллера — Рабіна (або тест Міллера – Рабіна) — це тест простоти, який визначає, чи є задане ціле число простим. Тест заснований на наступній теоремі:

Теорема (Маленька теорема Ферма)

Якщо n — просте число, а a — будь-яке ціле число, не кратне n, то a^(n-1) ≡ 1 (mod n).

Алгоритм

Алгоритм тесту простоти Міллера — Рабіна такий:

1. Виберіть випадкове число a у діапазоні [2, n-2].
2. Обчисліть x = a^(n-1) (mod n).
3. Якщо x = 1, то поверніть true (ймовірно, n — просте).
4. Для i від 1 до k (зазвичай k = 100):
   • Якщо x = n-1, то поверніть true (ймовірно, n — просте).
   • Інакше x = x^2 (mod n).
5. Поверніть false (ймовірно, n не є простим).

Детерміністична версія

Первинну версію тесту розробив професор Міллер, і вона була детерміністичною. Проте, її детермінізм покладався на недоведену узагальнену гіпотезу Рімана.

Імовірнісна версія

Міхаель Рабін модифікував тест, щоб отримати безумовний імовірнісний алгоритм. У цьому підході виконується кілька повторень алгоритму. Ймовірність того, що тест помилково визначить складене число як просте, зменшується з кожним повторенням.

Доказові приклади

• Якщо n — парне, то це не просте число.
• Якщо n непарне і n % 3 = 0, то це не просте число.
• Якщо тест пройдено k разів, то ймовірність того, що n не є простим, становить менше ніж 1/4^k.

Переваги та недоліки

Переваги:

• Швидкий і ефективний.
• Не вимагає глибоких математичних знань.
• Підходить для великих чисел.

Недоліки:

• Імовірнісний: може помилково визначити складене число як просте.
• Ймовірність помилки залежить від кількості повторень.

Висновки

Тест простоти Міллера — Рабіна є широко використовуваним і ефективним методом визначення простоти цілих чисел. Завдяки своїй швидкості та простоті він придатний для використання в різних додатках, таких як криптографія та теорія чисел.

Часті запитання

1. Чи є тест Міллера — Рабіна детерміністичним?
2. Яка ймовірність того, що тест помилково визначить складене число як просте?
3. Як визначити кількість повторень, необхідних для досягнення заданого рівня довіри?
4. Які переваги використання тесту Міллера — Рабіна для виявлення простих чисел?
5. Які обмеження тесту Міллера — Рабіна?

Залишити коментар

Опубліковано Максим на 15 04 2024. Поданий під Вікі. Ви можете слідкувати за будь-якими відповідями через RSS 2.0. Ви можете подивитись до кінця і залишити відповідь.