Тест простоти

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

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

Найпростіший тест простоти полягає в такому: коли задане число n, перевірити чи якесь ціле m від 2 до n-1 ділить n. Якщо n ділиться на певне m, то n складене, в іншому разі воно просте. Замість перевірки всіх m до n-1, досить лише перевірити m до ${\sqrt {n}}$ : якщо n складене, то його можна розкласти на два множники, принаймні один з яких не перевищує ${\sqrt {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 $\leq$ ${\sqrt {n}}$ . Це у 3 рази швидше від попереднього методу. Насправді, всі прості мають вигляд c#k + i для i<c# де і належить до чисел, взаємно простих з c# (прайморіал). Фактично, коли $c\rightarrow \infty$ кількість значень, які c#k + i може набувати в певному діапазоні, зменшується, а, отже, час тестування $n$ зменшується. Для цього методу, слід ділити на всі прості менші ніж c. Спостереження, аналогічні до попереднього, можна застосувати рекурсивно, отримуючи решето Ератосфена. Вдалим способом пришвидшення цих методів (і всіх інших згаданих далі) є попередній обрахунок і зберігання списку всіх простих до певної межі, скажімо всіх простих до 200. (Такий список можна обчислити за допомогою решета Ератосфена). Тоді, перед тестуванням n на простоту з використанням серйозного методу, спочатку перевіряємо чи n не ділиться на якесь просте із цього списку.

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

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

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

Випадково вибрати число a.
Перевірити певну рівність, що містить a та задане число n. Якщо рівність не виконується, то число n — складене. a називають свідком^{[усталений термін?]} складеності, і тест зупиняється.
Виконувати крок 1, поки не буде досягнуто потрібної певності.

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

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

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

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

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

Близько початку 20 сторіччя дослідження показали, що тези з малої теореми Ферма можна використовувати для перевірки на простоту. Це призвело до появи тесту на простоту Поклінґтона. Однак, через те, що цей тест вимагає часткову факторизацію $n-1$ його часова складність у найгіршому випадку все ще дуже велика. Першим детермінованим тестом простоти значно швидшим, ніж наївні методи, був циклотомічний тест; для часу його виконання отримано оцінку O((log n)^{clog(log(log(n)))}), де n тестоване на простоту число, а c константа, незалежна від n. Це повільніше, ніж поліноміальний час.

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

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

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

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

Складність

У теорії складності обчислень, формальну мову, яка відповідає простим числам, позначають PRIMES. Неважко показати, що PRIMES належить до Co-NP: її доповнення 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.

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

Література

Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective. 2nd edition, Springer, 2005. ISBN 0-387-25282-7. Chapter 3: Recognizing Primes and Composites, pp.109–158. Chapter 4: Primality Proving, pp.159–190. Section 7.6: Elliptic curve primality proving (ECPP), pp.334–340.
Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Pages 391–396 of section 4.5.4.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.8: Primality testing, pp.887–896.
Manindra Agrawa], Neeraj Kayal, Nitin Saxena, PRIMES is in P, Annals of Mathematics 160 (2004), no. 2, pp. 781–793.

Див. також

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