Тест простоти: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Ilya (обговорення | внесок) мНемає опису редагування |
Немає опису редагування |
||
Рядок 1:
'''Тест простоти''' — [[алгоритм]] перевірки, чи є дане [[число]] [[просте число|простим]].
Важливо наголосити на різниці між тестуванням простоти та [[факторизацією цілих чисел|факторизація]]. Станом на 2006 рік, факторизація є обчислювально важкою проблемою, в той час як тестування простоти є порівняно простішим.
== Наївні методи ==
Найпростіший тест простоти полягає в такому: Коли задане число ''n'',
перевірити чи якесь ціле ''m'' від 2 до ''n-1'' [[подільність|ділить]] ''n''. Якщо ''n'' ділиться на певне ''m'', то ''n'' складене, в іншому разі воно просте.
Замість перевірки всіх ''m'' до ''n-1'', досить лише перевірити ''m'' до <math>\sqrt n</math>: якщо ''n'' складене, то його можна розкласти на два множники, принаймні один з яких не перевищує <math>\sqrt n</math>.
Можна також покращити ефективність, пропускаючи всі парні ''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<math>\leq</math><math>\sqrt n</math>. Це у 3 рази швидше від попереднього методу. Насправді, всі прості мають вигляд c#k + i lkz i<c# де i належить до чисел, взаємно простих з c#. Фактично, коли <math>c \rightarrow \infty</math> кількість значень, які c#k + i може набувати в певному діапазоні, зменшується, а, отже, час тестування <math>n </math> зменшується. Для цього методу, слід ділити на всі прості менші ніж c. Спостереження, аналогічні до попереднього, можна застосувати [[рекурсія|рекурсивно]], отримуючи [[решето Ератосфена]].
Вдалим способом пришвидшення цих методів (і всіх інших згаданих далі) є попередній обрахунок і зберігання списку всіх простих до певної межі, скажімо всіх простих до 200. (Такий список можна обчислити за допомогою решета Ератосфена). Тоді, перед тестуванням ''n'' на простоту з використанням серйозного методу, спочатку перевіряємо чи ''n'' не ділиться на якесь просте із цього списку.
== Імовірнісні тести ==
Найбільш популярними тестами простоти є [[рандомізований алгоритм|ймовірнісні тести]]. Ці тести використовують, крім тестованого числа ''n'', деякі інші числа ''a'' , які випадково вибираються з певного набору; звичні рандомізовані тести простоти ніколи не оголошують прості числа складеними, але можливе для складених чисел оголошення їх простими. Імовірність помилки можна зменшити, повторюючи тест з ріними незалежно вибраними ''a''; для двох найчастіше вживаних тестів, для ''будь-якого'' складеного ''n'' принаймні половина ''a''визначає складеність ''n'' , тому ''k'' повторень зменшують імовірність помилки до щонайбільше 2<sup>−k</sup>. Останню величину можна зробити як завгодно малою, збільшуючи ''k''.
Базова структура рандомізованих тестів простоти є такою:
#Випадково вибрати число ''a''.
#Перевірити певну рівність, що містить ''a'' та задане число ''n''. Якщо рівність не виконується, то ''n'' є [[складене число]], ''a'' називають ''свідченням'' складеності, і тест зупиняється.
#Виконувати крок 1, поки не буде досягнуто потрібної певності.
Після низки повторень, якщо не отримано, що ''n'' є [[складене число]], то його можна оголосити [[імовірнісне просте|імовірнісним простим]].
Найпростішим імовірнісним тестом простоти є
[[тест простоти Ферма]]. Це лише евристичний тест; деякі складені числа ([[числа Карміхаеля]]) будуть оголошені "імовірнісними простими" незалежно від того, яке свідчення вибране.
Проте, він деколи використовується з метою швидкої перевірки числа, наприклад, на фазі утворення ключа [[RSA|криптографічного алгоритму з відкритим ключем RSA]].
[[Тест простоти Міллера-Рабіна]] та [[Тест простоти Соловея-Штрассена]] є вдосконаленими варіантами, які визначають всі складені числа (це означає: для ''кожного'' складеного числа ''n'', принаймні 3/4 (Міллер-Рабін) або 1/2 (Соловей-Штрассен) чисел ''a'' є свідченнями складеності ''n'').
На ці методи часто падає вибір, бо вони набагато швидші, ніж інші загальні тести прототи.
Леонард Адлеман та Хуанг запропонували варіант без помилки (але лише з очікуваним поліноміальним часом виконання) [[тест простоти на основі еліптичних кривих|тесту простоти на основі еліптичних кривих]]. На відміну від інших імовірнісних тестів, цей алгоритм дає сертифікат простоти, а тому може бути використаний для доведення простоти числа. Цей алгоритм занадто повільний на практиці.
== Швидкі детерміновані тести ==
Першим [[детермінований алгоритм|детермінованим]] тестом простоти значно швидшим, ніж наївні методи, був [[циклотомічний тест]]; для часу його виконання отримано оцінку [[Big O notation|O]]((log ''n'')<sup>''c''log(log(log(''n'')))</sup>), де ''n'' тестоване на простоту число, а ''c'' константа, незалежна від ''n''. Це повільніше, ніж поліноміальний час.
Для [[Тест простоти на основі еліптичних кривих|тесту простоти на основі еліптичних кривих]] можна отримати оцінку O((log ''n'')<sup>6</sup>), але лише коли використовуємо деякі ще не доведені (але які як правило припускаються вірними) положення аналітичної теорії чисел. Це один з з найчастіше вживаних на практиці детермінованих тестів.
Реалізація цих двох методів досить важка, бо є великий ризик помилок при програмуванні; це одна з причин, чому їм не віддають перевагу.
Якщо вважається вірною [[узагальнена гіпотеза Рімана]], то тест Міллера-Рабіна можна звести до детермінованої версії з часом виконання O((log ''n'')<sup>4</sup>). На практиці, цей алгоритм повільніший, ніж два інших для величин чисел, з якими можна реально оперувати.
У 2002, Маніндра Агравал, Нітін Саксена та Нірай Кайал описали новий детермінований тест простоти, [[AKS тест прототи]], який як доведено виконується за O((log ''n'')<sup>12</sup>). Крім того, якщо вірна [[прості Софі Жермен|гіпотеза Харді-Літвулда]], яку вважають справедливою, то він виконується за O((log ''n'')<sup>6</sup>). Отже, маємо перший детермінований тест простоти з доведеним [[поліноміальний час|поліноміальним часом виконання]]. На практиці, цей алгоритм повільніший, ніж імовірнісні методи.
== Складність ==
У [[теорія складності обчислень|теорії складності обчислень]], формальну мову, яка відповідає простим числам, позначають PRIMES. Неважко показати, що PRIMES належить до '''coNP''': її доповнення COMPOSITES належить до '''NP''', бо можна показати складеність недетерміновано вгадуючи дільник.
У 1975 [[Вауган Пратт]] показав існування сертифікату простоти, який перевіряється за поліноміальний час, і значить PRIMES належить до [[NP (складність)|NP]], а тому й до '''NP ? coNP'''. Деталі дивись у [[сертифікат простоти]].
Подальше відкриття алгоритмів Соловея-Штрассена та Міллера-Рабіна показало належність PRIMES до [[RP (складність)|coRP]]. У 1992 алгоритм Адлемана-Хуанга звузив складність до [[ZPP]] = '''RP''' ? '''coRP''', що є заміщенням результату Пратта.
Циклотомічний тест Адлемана, [[Померанце]] та Рамлі 1983р. показав належність PRIMES до '''QP''' ([[квазі-поліноміальний час]]), для якого невідоме порівняння із згаданими раніше класами.
Існування [[AKS тест простоти|AKS тесту простоти]], який остаточно розв'язав цю давню проблему, означає, що PRIMES належить до [[P (складність)|P]].
== Теоретико-числові методи ==
Існують певні теоретико-числові методи для тестування чи є число простим, зокрема [[тест Лукаса-Лемера]] та [[теорема Профа|тест Профа]]. Як правило, для цих тестів потрібний розклад ''n'' + 1, ''n'' − 1, або аналогічних чисел, а це означає, що вони не підходять для тестування простоти чисел загального вигляду, проте часто є досить потужним засобом, коли тестуємо число ''n'' спеціального вигляду.
Тест Лукаса-Лемера спирається на факт, що [[мультиплікативний порядок]] числа ''a'' за модулем ''n'' дорівнює ''n'' − 1 для простого ''n'', якщо ''a'' [[примітивний корінь за модулем n]]. Коли можемо показати, що ''a'' примітивний корінь для ''n'', то можемо довести простоту ''n''.
== Зовнішні зв’язки ==
*[http://webstore.ansi.org/ansidocstore/product.asp?sku=X9%2E80%2D2005 ANSI X9.80 - PRIME NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES]
*[http://cr.yp.to/primetests.html Distinguishing prime numbers from composite numbers], D.J. Bernstein
*[http://primes.utm.edu/ The Prime Pages]
*[http://www.bigprimes.net/primality_test.php Big Primes Database]
== Література ==
* {{cite book|author = [[Richard Crandall]] and [[Carl Pomerance]] | year = 2005 | title = Prime Numbers: A Computational Perspective | publisher = Springer | edition = 2nd edition | id = 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.
* {{cite book|author = [[Christos Papadimitriou]] | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st edition | id = ISBN 0-201-53082-1}} Section 10.2: Primality, pp.222–227.
* [[Manindra Agrawal]], [[Neeraj Kayal]], [[Nitin Saxena]], ''[http://www.cse.iitk.ac.in/users/manindra/primality_v6.pdf PRIMES is in P]'', Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
==Див. також==
Рядок 5 ⟶ 76:
{{math-stub}}
[[Категорія:Інформаційна безпека]]
[[Категорія:Криптографія]]
{{Link FA|es}}
| |||