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

перевірити чи якесь ціле ''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. Спостереження, аналогічні до попереднього, можна застосувати [[рекурсія|рекурсивно]], отримуючи [[решето Ератосфена]].

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

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

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

Існують певні теоретико-числові методи для тестування чи є число простим, зокрема [[тест Лукаса-Лемера]] та [[теорема Профа|тест Профа]]. Як правило, для цих тестів потрібний розклад ''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.

== Див. також ==