Відмінності між версіями «Тест простоти»

44 байти вилучено ,  11 років тому
м
робот косметичні зміни
м (робот косметичні зміни)
 
Найпростіший тест простоти полягає в такому: коли задане число ''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>&minus;k−k</sup>. Останню величину можна зробити як завгодно малою, збільшуючи ''k''.
 
Базова структура рандомізованих тестів простоти є такою:
Якщо вважається вірною [[узагальнена гіпотеза Рімана]], то тест Міллера-Рабіна можна звести до детермінованої версії з часом виконання O((log&nbsp;''n'')<sup>4</sup>). На практиці, цей алгоритм повільніший, ніж два інших для величин чисел, з якими можна реально оперувати.
 
У 2002, Маніндра Агравал, Нітін Саксена та Нірай Кайал описали новий детермінований тест простоти, [[AKS тест прототи]], який як доведено виконується за O((log&nbsp;''n'')<sup>12</sup>). Крім того, якщо вірна [[прості Софі Жермен|гіпотеза Харді-Літвулда]], яку вважають справедливою, то він виконується за O((log&nbsp;''n'')<sup>6</sup>). Отже, маємо перший детермінований тест простоти з доведеним [[поліноміальний час|поліноміальним часом виконання]]. На практиці, цей алгоритм повільніший, ніж імовірнісні методи.
 
== Складність ==
У [[теорія складності обчислень|теорії складності обчислень]], формальну мову, яка відповідає простим числам, позначають PRIMES. Неважко показати, що PRIMES належить до '''coNP''': її доповнення COMPOSITES належить до '''NP''', бо можна показати складеність недетерміновано вгадуючи дільник.
 
У 1975 [[Вауган Пратт]] показав існування сертифікату простоти, який перевіряється за поліноміальний час, і значить PRIMES належить до [[NP (складність)|NP]], а тому й до '''NP ? coNP'''. Деталі дивись у [[сертифікат простоти]].
 
== Теоретико-числові методи ==
Існують певні теоретико-числові методи для тестування чи є число простим, зокрема [[тест Лукаса-Лемера]] та [[теорема Профа|тест Профа]]. Як правило, для цих тестів потрібний розклад ''n'' + 1, ''n'' &minus; 1, або аналогічних чисел, а це означає, що вони не підходять для тестування простоти чисел загального вигляду, проте часто є досить потужним засобом, коли тестуємо число ''n'' спеціального вигляду.
 
Тест Лукаса-Лемера спирається на факт, що [[мультиплікативний порядок]] числа ''a'' за модулем ''n'' дорівнює ''n'' &minus; 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&ndash;158109–158. Chapter 4: Primality Proving, pp.159&ndash;190159–190. Section 7.6: Elliptic curve primality proving (ECPP), pp.334&ndash;340334–340.
* [[Donald Knuth]]. ''The Art of Computer Programming'', Volume 2: ''Seminumerical Algorithms'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Pages 391&ndash;396391–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&ndash;896887–896.
* [[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&ndash;793781–793.
 
== Див. також ==
* [[AKS тест простоти]]
{{Link FA|es}}
 
[[Категорія:Тести простоти|*]]
 
{{Link FA|es}}
 
[[ca:Test de primalitat]]
220 373

редагування