Тест простоти: відмінності між версіями

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[неперевірена версія][неперевірена версія]
Вилучено вміст Додано вміст
SieBot (обговорення | внесок)
м робот додав: no, pt, simple, sv
м робот додав: it:Test di primalità
Рядок 85: Рядок 85:
[[fr:Test de primalité]]
[[fr:Test de primalité]]
[[hu:Prímteszt]]
[[hu:Prímteszt]]
[[it:Test di primalità]]
[[ja:素数判定]]
[[ja:素数判定]]
[[no:Primtallstest]]
[[no:Primtallstest]]

Версія за 22:55, 22 грудня 2007

Тест простотиалгоритм перевірки, чи є дане число простим. Важливо наголосити на різниці між тестуванням простоти та факторизацією цілих чисел. Станом на 2006 рік, факторизація є обчислювально важкою проблемою, в той час як тестування простоти є порівняно простішим.

Наївні методи

Найпростіший тест простоти полягає в такому: коли задане число n, перевірити чи якесь ціле m від 2 до n-1 ділить n. Якщо n ділиться на певне m, то n складене, в іншому разі воно просте. Замість перевірки всіх m до n-1, досить лише перевірити m до : якщо n складене, то його можна розкласти на два множники, принаймні один з яких не перевищує . Можна також покращити ефективність, пропускаючи всі парні m , за винятком 2, бо коли якесь парне число ділить n , то 2 також ділить. Можна далі вдосконалити зауважуючи, що всі прості числа, за винятком 2 та 3, мають вигляд 6k + 1. Дійсно, всі цілі можна подати як (6k + i) для деякого k та для i = -1, 0, 1, 2, 3, або 4; 2 ділить (6k + 0), (6k + 2), (6k + 4); а 3 ділить (6k + 3). Спочатку перевіряємо чи n ділиться на 2 або 3, тоді пробігаємо всі числа вигляду 6k + 1. Це у 3 рази швидше від попереднього методу. Насправді, всі прості мають вигляд c#k + i lkz i<c# де i належить до чисел, взаємно простих з c#. Фактично, коли кількість значень, які c#k + i може набувати в певному діапазоні, зменшується, а, отже, час тестування зменшується. Для цього методу, слід ділити на всі прості менші ніж c. Спостереження, аналогічні до попереднього, можна застосувати рекурсивно, отримуючи решето Ератосфена. Вдалим способом пришвидшення цих методів (і всіх інших згаданих далі) є попередній обрахунок і зберігання списку всіх простих до певної межі, скажімо всіх простих до 200. (Такий список можна обчислити за допомогою решета Ератосфена). Тоді, перед тестуванням n на простоту з використанням серйозного методу, спочатку перевіряємо чи n не ділиться на якесь просте із цього списку.

Імовірнісні тести

Найбільш популярними тестами простоти є ймовірнісні тести. Ці тести використовують, крім тестованого числа n, деякі інші числа a , які випадково вибираються з певного набору; звичні рандомізовані тести простоти ніколи не оголошують прості числа складеними, але можливе для складених чисел оголошення їх простими. Імовірність помилки можна зменшити, повторюючи тест з ріними незалежно вибраними a; для двох найчастіше вживаних тестів, для будь-якого складеного n принаймні половина aвизначає складеність n , тому k повторень зменшують імовірність помилки до щонайбільше 2−k. Останню величину можна зробити як завгодно малою, збільшуючи k.

Базова структура рандомізованих тестів простоти є такою:

  1. Випадково вибрати число a.
  2. Перевірити певну рівність, що містить a та задане число n. Якщо рівність не виконується, то n є складене число, a називають свідченням складеності, і тест зупиняється.
  3. Виконувати крок 1, поки не буде досягнуто потрібної певності.

Після низки повторень, якщо не отримано, що n є складене число, то його можна оголосити імовірнісним простим.

Найпростішим імовірнісним тестом простоти є тест простоти Ферма. Це лише евристичний тест; деякі складені числа (числа Карміхаеля) будуть оголошені "імовірнісними простими" незалежно від того, яке свідчення вибране. Проте, він деколи використовується з метою швидкої перевірки числа, наприклад, на фазі утворення ключа криптографічного алгоритму з відкритим ключем RSA.

Тест простоти Міллера-Рабіна та Тест простоти Соловея-Штрассена є вдосконаленими варіантами, які визначають всі складені числа (це означає: для кожного складеного числа n, принаймні 3/4 (Міллер-Рабін) або 1/2 (Соловей-Штрассен) чисел a є свідченнями складеності n). На ці методи часто падає вибір, бо вони набагато швидші, ніж інші загальні тести прототи.

Леонард Адлеман та Хуанг запропонували варіант без помилки (але лише з очікуваним поліноміальним часом виконання) тесту простоти на основі еліптичних кривих. На відміну від інших імовірнісних тестів, цей алгоритм дає сертифікат простоти, а тому може бути використаний для доведення простоти числа. Цей алгоритм занадто повільний на практиці.

Швидкі детерміновані тести

Першим детермінованим тестом простоти значно швидшим, ніж наївні методи, був циклотомічний тест; для часу його виконання отримано оцінку O((log n)clog(log(log(n)))), де n тестоване на простоту число, а c константа, незалежна від n. Це повільніше, ніж поліноміальний час.

Для тесту простоти на основі еліптичних кривих можна отримати оцінку O((log n)6), але лише коли використовуємо деякі ще не доведені (але які як правило припускаються вірними) положення аналітичної теорії чисел. Це один з з найчастіше вживаних на практиці детермінованих тестів.

Реалізація цих двох методів досить важка, бо є великий ризик помилок при програмуванні; це одна з причин, чому їм не віддають перевагу.

Якщо вважається вірною узагальнена гіпотеза Рімана, то тест Міллера-Рабіна можна звести до детермінованої версії з часом виконання O((log n)4). На практиці, цей алгоритм повільніший, ніж два інших для величин чисел, з якими можна реально оперувати.

У 2002, Маніндра Агравал, Нітін Саксена та Нірай Кайал описали новий детермінований тест простоти, AKS тест прототи, який як доведено виконується за O((log n)12). Крім того, якщо вірна гіпотеза Харді-Літвулда, яку вважають справедливою, то він виконується за O((log n)6). Отже, маємо перший детермінований тест простоти з доведеним поліноміальним часом виконання. На практиці, цей алгоритм повільніший, ніж імовірнісні методи.

Складність

У теорії складності обчислень, формальну мову, яка відповідає простим числам, позначають PRIMES. Неважко показати, що PRIMES належить до coNP: її доповнення COMPOSITES належить до NP, бо можна показати складеність недетерміновано вгадуючи дільник.

У 1975 Вауган Пратт показав існування сертифікату простоти, який перевіряється за поліноміальний час, і значить PRIMES належить до NP, а тому й до NP ? coNP. Деталі дивись у сертифікат простоти.

Подальше відкриття алгоритмів Соловея-Штрассена та Міллера-Рабіна показало належність PRIMES до coRP. У 1992 алгоритм Адлемана-Хуанга звузив складність до ZPP = RP ? coRP, що є заміщенням результату Пратта.

Циклотомічний тест Адлемана, Померанце та Рамлі 1983р. показав належність PRIMES до QP (квазі-поліноміальний час), для якого невідоме порівняння із згаданими раніше класами.

Існування AKS тесту простоти, який остаточно розв'язав цю давню проблему, означає, що PRIMES належить до P.

Теоретико-числові методи

Існують певні теоретико-числові методи для тестування чи є число простим, зокрема тест Лукаса-Лемера та тест Профа. Як правило, для цих тестів потрібний розклад n + 1, n − 1, або аналогічних чисел, а це означає, що вони не підходять для тестування простоти чисел загального вигляду, проте часто є досить потужним засобом, коли тестуємо число n спеціального вигляду.

Тест Лукаса-Лемера спирається на факт, що мультиплікативний порядок числа a за модулем n дорівнює n − 1 для простого n, якщо a примітивний корінь за модулем n. Коли можемо показати, що a примітивний корінь для n, то можемо довести простоту n.

Зовнішні зв’язки

Література

Див. також

AKS тест простоти

Шаблон:Link FA