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

[неперевірена версія][неперевірена версія]
м (робот додав: nl:Priemgetaltest)
(Виправлено джерел: 2; позначено як недійсні: 0. #IABot (v2.0beta15))
 
(Не показано 22 проміжні версії 15 користувачів)
Рядок 1: Рядок 1:
 
'''Тест простоти''' — [[алгоритм]] перевірки, чи є дане [[число]] [[просте число|простим]].
 
'''Тест простоти''' — [[алгоритм]] перевірки, чи є дане [[число]] [[просте число|простим]].
Важливо наголосити на різниці між тестуванням простоти та [[факторизація|факторизацією цілих чисел]]. Станом на 2006 рік, [[факторизація]] є обчислювально важкою проблемою, в той час як тестування простоти є порівняно простішим.
+
Важливо наголосити на різниці між тестуванням простоти та [[факторизація|факторизацією цілих чисел]]. Станом на 2009 рік, [[факторизація]] є обчислювально важкою проблемою, в той час як тестування простоти є порівняно простішим (має [[Клас складності P|поліноміальну складність]]).
   
 
== Наївні методи ==
 
== Наївні методи ==
   
 
Найпростіший тест простоти полягає в такому: коли задане число ''n'',
 
Найпростіший тест простоти полягає в такому: коли задане число ''n'',
перевірити чи якесь ціле ''m'' від 2 до ''n-1'' [[подільність|ділить]] ''n''. Якщо ''n'' ділиться на певне ''m'', то ''n'' складене, в іншому разі воно просте.
+
перевірити чи якесь ціле ''m'' від 2 до ''n-1'' [[подільність|ділить]] ''n''. Якщо ''n'' ділиться на певне ''m'', то ''n'' складене, в іншому разі воно просте.
Замість перевірки всіх ''m'' до ''n-1'', досить лише перевірити ''m'' до <math>\sqrt n</math>: якщо ''n'' складене, то його можна розкласти на два множники, принаймні один з яких не перевищує <math>\sqrt n</math>.
+
Замість перевірки всіх ''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. Спостереження, аналогічні до попереднього, можна застосувати [[рекурсія|рекурсивно]], отримуючи [[решето Ератосфена]].
+
Можна також покращити ефективність, пропускаючи всі парні ''m'' , за винятком 2, бо коли якесь парне число ділить ''n'' , то 2 також ділить. Можна далі вдосконалити зауважуючи, що всі прості числа, за винятком 2 та 3, мають вигляд 6k ± 1. Дійсно, всі цілі можна подати як (6''k'' + ''i'') для деякого ''k'' та для ''i'' = -1, 0, 1, 2, 3, або 4; 2 ділить (6''k'' + 0), (6''k'' + 2), (6''k'' + 4); а 3 ділить (6''k'' + 3). Спочатку перевіряємо чи ''n'' ділиться на 2 або 3, тоді пробігаємо всі числа вигляду 6''k'' ± 1<math>\leq</math><math>\sqrt n</math>. Це у 3 рази швидше від попереднього методу. Насправді, всі прості мають вигляд ''c#k + i'' для ''i<c#'' де ''і'' належить до чисел, [[взаємно прості числа|взаємно простих]] з [[:en:Primorial|c#]] (приморіал) . Фактично, коли <math>c \rightarrow \infty</math> кількість значень, які ''c#k + i'' може набувати в певному діапазоні, зменшується, а, отже, час тестування <math>n </math> зменшується. Для цього методу, слід ділити на всі прості менші ніж ''c''. Спостереження, аналогічні до попереднього, можна застосувати [[рекурсія|рекурсивно]], отримуючи [[решето Ератосфена]].
 
Вдалим способом пришвидшення цих методів (і всіх інших згаданих далі) є попередній обрахунок і зберігання списку всіх простих до певної межі, скажімо всіх простих до 200. (Такий список можна обчислити за допомогою решета Ератосфена). Тоді, перед тестуванням ''n'' на простоту з використанням серйозного методу, спочатку перевіряємо чи ''n'' не ділиться на якесь просте із цього списку.
 
Вдалим способом пришвидшення цих методів (і всіх інших згаданих далі) є попередній обрахунок і зберігання списку всіх простих до певної межі, скажімо всіх простих до 200. (Такий список можна обчислити за допомогою решета Ератосфена). Тоді, перед тестуванням ''n'' на простоту з використанням серйозного методу, спочатку перевіряємо чи ''n'' не ділиться на якесь просте із цього списку.
   
== Імовірнісні тести ==
+
== Ймовірнісні тести ==
   
Найбільш популярними тестами простоти є [[рандомізований алгоритм|ймовірнісні тести]]. Ці тести використовують, крім тестованого числа ''n'', деякі інші числа ''a'' , які випадково вибираються з певного набору; звичні рандомізовані тести простоти ніколи не оголошують прості числа складеними, але можливе для складених чисел оголошення їх простими. Імовірність помилки можна зменшити, повторюючи тест з ріними незалежно вибраними ''a''; для двох найчастіше вживаних тестів, для ''будь-якого'' складеного ''n'' принаймні половина ''a''визначає складеність ''n'' , тому ''k'' повторень зменшують імовірність помилки до щонайбільше 2<sup>&minus;k</sup>. Останню величину можна зробити як завгодно малою, збільшуючи ''k''.
+
Найпопулярнішими тестами простоти є [[рандомізований алгоритм|ймовірнісні тести]]. Ці тести використовують, крім тестованого числа ''n'', деякі інші числа ''a'' , які випадково вибираються з певного набору; звичні рандомізовані тести простоти ніколи не оголошують прості числа складеними, але можливе для складених чисел оголошення їх простими. Імовірність помилки можна зменшити, повторюючи тест з різними незалежно вибраними ''a''; для двох найчастіше вживаних тестів, для ''будь-якого'' складеного ''n'' принаймні половина ''a'' визначає складеність ''n'' , тому ''k'' повторень зменшують імовірність помилки до щонайбільше 2<sup>−k</sup>. Останню величину можна зробити як завгодно малою, збільшуючи ''k''.
   
 
Базова структура рандомізованих тестів простоти є такою:
 
Базова структура рандомізованих тестів простоти є такою:
   
 
#Випадково вибрати число ''a''.
 
#Випадково вибрати число ''a''.
#Перевірити певну рівність, що містить ''a'' та задане число ''n''. Якщо рівність не виконується, то ''n'' є [[складене число]], ''a'' називають ''свідченням'' складеності, і тест зупиняється.
+
#Перевірити певну рівність, що містить ''a'' та задане число ''n''. Якщо рівність не виконується, то ''n'' є [[складене число]], ''a'' називають ''свідком'' складеності, і тест зупиняється.
 
#Виконувати крок 1, поки не буде досягнуто потрібної певності.
 
#Виконувати крок 1, поки не буде досягнуто потрібної певності.
   
 
Після низки повторень, якщо не отримано, що ''n'' є [[складене число]], то його можна оголосити [[імовірнісне просте|імовірнісним простим]].
 
Після низки повторень, якщо не отримано, що ''n'' є [[складене число]], то його можна оголосити [[імовірнісне просте|імовірнісним простим]].
   
  +
[[Файл:брехуни_щодо_простоти.png|міні|right|200пкс|Розглянемо складене число n&nbsp;=&nbsp;65 (=&nbsp;5&nbsp;×&nbsp;13). Брехуни Ферма для 65&nbsp;— {1, 8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57, 64}. Брехуни Ойлера для 65&nbsp;— {1, 8, 14, 18, 47, 51, 57, 64}, тоді як сильні брехуни для 65&nbsp;—{1, 8, 18, 47, 57, 64}.]]
Найпростішим імовірнісним тестом простоти є
 
[[тест простоти Ферма]]. Це лише евристичний тест; деякі складені числа ([[числа Карміхаеля]]) будуть оголошені "імовірнісними простими" незалежно від того, яке свідчення вибране.
+
Найпростішим ймовірнісним тестом простоти є [[тест простоти Ферма]]. Це лише евристичний тест; деякі складені числа ([[числа Кармайкла]]) будуть оголошені "ймовірнісними простими" незалежно від того, якого свідка обрати. Проте, він деколи використовується з метою швидкої перевірки числа, наприклад, на фазі утворення ключа [[RSA|криптографічного алгоритму з відкритим ключем RSA]].
Проте, він деколи використовується з метою швидкої перевірки числа, наприклад, на фазі утворення ключа [[RSA|криптографічного алгоритму з відкритим ключем RSA]].
 
   
[[Тест простоти Міллера-Рабіна]] та [[Тест простоти Соловея-Штрассена]] є вдосконаленими варіантами, які визначають всі складені числа (це означає: для ''кожного'' складеного числа ''n'', принаймні 3/4 (Міллер-Рабін) або 1/2 (Соловей-Штрассен) чисел ''a'' є свідченнями складеності ''n'').
+
[[Тест простоти Міллера-Рабіна]] та [[тест простоти Соловея-Штрассена]] є вдосконаленими варіантами, які визначають всі складені числа (це означає: для ''кожного'' складеного числа ''n'', принаймні 3/4 (Міллер-Рабін) або 1/2 (Соловей-Штрассен) чисел ''a'' є свідками складеності ''n''). На ці методи часто падає вибір, бо вони набагато швидші, ніж інші загальні тести простоти.
На ці методи часто падає вибір, бо вони набагато швидші, ніж інші загальні тести прототи.
 
   
 
Леонард Адлеман та Хуанг запропонували варіант без помилки (але лише з очікуваним поліноміальним часом виконання) [[тест простоти на основі еліптичних кривих|тесту простоти на основі еліптичних кривих]]. На відміну від інших імовірнісних тестів, цей алгоритм дає сертифікат простоти, а тому може бути використаний для доведення простоти числа. Цей алгоритм занадто повільний на практиці.
 
Леонард Адлеман та Хуанг запропонували варіант без помилки (але лише з очікуваним поліноміальним часом виконання) [[тест простоти на основі еліптичних кривих|тесту простоти на основі еліптичних кривих]]. На відміну від інших імовірнісних тестів, цей алгоритм дає сертифікат простоти, а тому може бути використаний для доведення простоти числа. Цей алгоритм занадто повільний на практиці.
Рядок 33: Рядок 31:
 
== Швидкі детерміновані тести ==
 
== Швидкі детерміновані тести ==
   
Першим [[детермінований алгоритм|детермінованим]] тестом простоти значно швидшим, ніж наївні методи, був [[циклотомічний тест]]; для часу його виконання отримано оцінку [[Big O notation|O]]((log&nbsp;''n'')<sup>''c''log(log(log(''n'')))</sup>), де ''n'' тестоване на простоту число, а ''c'' константа, незалежна від ''n''. Це повільніше, ніж поліноміальний час.
+
Близько початку 20 сторіччя дослідження показали, що тези з малої теореми Ферма можна використовувати для перевірки на простоту. Це призвело до появи [[Тест на простоту Поклінґтона|тесту на простоту Поклінґтона]]. Однак, через те, що цей тест вимагає часткову факторизацію <math>n-1</math> його часова складність у найгіршому випадку все ще дуже велика. Першим [[детермінований алгоритм|детермінованим]] тестом простоти значно швидшим, ніж наївні методи, був [[циклотомічний тест]]; для часу його виконання отримано оцінку [[Нотація Ландау|O]]((log&nbsp;''n'')<sup>''c''log(log(log(''n'')))</sup>), де ''n'' тестоване на простоту число, а ''c'' константа, незалежна від ''n''. Це повільніше, ніж поліноміальний час.
   
 
Для [[Тест простоти на основі еліптичних кривих|тесту простоти на основі еліптичних кривих]] можна отримати оцінку O((log&nbsp;''n'')<sup>6</sup>), але лише коли використовуємо деякі ще не доведені (але які як правило припускаються вірними) положення аналітичної теорії чисел. Це один з з найчастіше вживаних на практиці детермінованих тестів.
 
Для [[Тест простоти на основі еліптичних кривих|тесту простоти на основі еліптичних кривих]] можна отримати оцінку O((log&nbsp;''n'')<sup>6</sup>), але лише коли використовуємо деякі ще не доведені (але які як правило припускаються вірними) положення аналітичної теорії чисел. Це один з з найчастіше вживаних на практиці детермінованих тестів.
Рядок 41: Рядок 39:
 
Якщо вважається вірною [[узагальнена гіпотеза Рімана]], то тест Міллера-Рабіна можна звести до детермінованої версії з часом виконання O((log&nbsp;''n'')<sup>4</sup>). На практиці, цей алгоритм повільніший, ніж два інших для величин чисел, з якими можна реально оперувати.
 
Якщо вважається вірною [[узагальнена гіпотеза Рімана]], то тест Міллера-Рабіна можна звести до детермінованої версії з часом виконання O((log&nbsp;''n'')<sup>4</sup>). На практиці, цей алгоритм повільніший, ніж два інших для величин чисел, з якими можна реально оперувати.
   
У 2002, Маніндра Агравал, Нітін Саксена та Нірай Кайал описали новий детермінований тест простоти, [[AKS тест прототи]], який як доведено виконується за O((log&nbsp;''n'')<sup>12</sup>). Крім того, якщо вірна [[прості Софі Жермен|гіпотеза Харді-Літвулда]], яку вважають справедливою, то він виконується за O((log&nbsp;''n'')<sup>6</sup>). Отже, маємо перший детермінований тест простоти з доведеним [[поліноміальний час|поліноміальним часом виконання]]. На практиці, цей алгоритм повільніший, ніж імовірнісні методи.
+
У 2002, Маніндра Агравал, Нітін Саксена та Нірай Кайал описали новий детермінований тест простоти, [[AKS тест простоти]], який як доведено виконується за O((log&nbsp;''n'')<sup>12</sup>). Крім того, якщо вірна [[прості Софі Жермен|гіпотеза Харді-Літлвуда]], яку вважають справедливою, то він виконується за O((log&nbsp;''n'')<sup>6</sup>). Отже, маємо перший детермінований тест простоти з доведеним [[поліноміальний час|поліноміальним часом виконання]]. На практиці, цей алгоритм повільніший, ніж імовірнісні методи.
   
 
== Складність ==
 
== Складність ==
У [[теорія складності обчислень|теорії складності обчислень]], формальну мову, яка відповідає простим числам, позначають PRIMES. Неважко показати, що PRIMES належить до '''coNP''': її доповнення COMPOSITES належить до '''NP''', бо можна показати складеність недетерміновано вгадуючи дільник.
+
У [[теорія складності обчислень|теорії складності обчислень]], формальну мову, яка відповідає простим числам, позначають PRIMES. Неважко показати, що PRIMES належить до '''[[Co-NP]]''': її доповнення COMPOSITES належить до '''NP''', бо можна показати складеність недетерміновано вгадуючи дільник.
   
 
У 1975 [[Вауган Пратт]] показав існування сертифікату простоти, який перевіряється за поліноміальний час, і значить PRIMES належить до [[NP (складність)|NP]], а тому й до '''NP ? coNP'''. Деталі дивись у [[сертифікат простоти]].
 
У 1975 [[Вауган Пратт]] показав існування сертифікату простоти, який перевіряється за поліноміальний час, і значить PRIMES належить до [[NP (складність)|NP]], а тому й до '''NP ? coNP'''. Деталі дивись у [[сертифікат простоти]].
Рядок 50: Рядок 48:
 
Подальше відкриття алгоритмів Соловея-Штрассена та Міллера-Рабіна показало належність PRIMES до [[RP (складність)|coRP]]. У 1992 алгоритм Адлемана-Хуанга звузив складність до [[ZPP]] = '''RP''' ? '''coRP''', що є заміщенням результату Пратта.
 
Подальше відкриття алгоритмів Соловея-Штрассена та Міллера-Рабіна показало належність PRIMES до [[RP (складність)|coRP]]. У 1992 алгоритм Адлемана-Хуанга звузив складність до [[ZPP]] = '''RP''' ? '''coRP''', що є заміщенням результату Пратта.
   
Циклотомічний тест Адлемана, [[Померанце]] та Рамлі 1983р. показав належність PRIMES до '''QP''' ([[квазі-поліноміальний час]]), для якого невідоме порівняння із згаданими раніше класами.
+
Циклотомічний тест Адлемана, [[Померанце]] та Рамлі 1983 р. показав належність PRIMES до '''QP''' ([[квазі-поліноміальний час]]), для якого невідоме порівняння із згаданими раніше класами.
   
 
Існування [[AKS тест простоти|AKS тесту простоти]], який остаточно розв'язав цю давню проблему, означає, що PRIMES належить до [[P (складність)|P]].
 
Існування [[AKS тест простоти|AKS тесту простоти]], який остаточно розв'язав цю давню проблему, означає, що PRIMES належить до [[P (складність)|P]].
   
 
== Теоретико-числові методи ==
 
== Теоретико-числові методи ==
Існують певні теоретико-числові методи для тестування чи є число простим, зокрема [[тест Лукаса-Лемера]] та [[теорема Профа|тест Профа]]. Як правило, для цих тестів потрібний розклад ''n'' + 1, ''n'' &minus; 1, або аналогічних чисел, а це означає, що вони не підходять для тестування простоти чисел загального вигляду, проте часто є досить потужним засобом, коли тестуємо число ''n'' спеціального вигляду.
+
Існують певні теоретико-числові методи для тестування чи є число простим, зокрема [[тест Лукаса-Лемера]] та [[теорема Профа|тест Профа]]. Як правило, для цих тестів потрібний розклад ''n'' + 1, ''n'' 1, або аналогічних чисел, а це означає, що вони не підходять для тестування простоти чисел загального вигляду, проте часто є досить потужним засобом, коли тестуємо число ''n'' спеціального вигляду.
   
Тест Лукаса-Лемера спирається на факт, що [[мультиплікативний порядок]] числа ''a'' за модулем ''n'' дорівнює ''n'' &minus; 1 для простого ''n'', якщо ''a'' [[примітивний корінь за модулем n]]. Коли можемо показати, що ''a'' примітивний корінь для ''n'', то можемо довести простоту ''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]
+
*[https://web.archive.org/web/20060617203619/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://cr.yp.to/primetests.html Distinguishing prime numbers from composite numbers], D.J. Bernstein
 
*[http://primes.utm.edu/ The Prime Pages]
 
*[http://primes.utm.edu/ The Prime Pages]
Рядок 66: Рядок 64:
   
 
== Література ==
 
== Література ==
* [[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;158. Chapter 4: Primality Proving, pp.159&ndash;190. Section 7.6: Elliptic curve primality proving (ECPP), pp.334&ndash;340.
+
* 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&ndash;396 of section 4.5.4.
+
* 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&ndash;896.
+
* 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 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;793.
+
* Manindra Agrawa], Neeraj Kayal, Nitin Saxena, ''[https://web.archive.org/web/20060716131144/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.
   
==Див. також==
+
== Див. також ==
[[AKS тест простоти]]
+
* [[AKS тест простоти]]
   
[[Категорія:Інформаційна безпека]]
+
[[Категорія:Тести простоти|*]]
[[Категорія:Криптографія]]
 
[[Категорія:Математика]]
 
 
{{Link FA|es}}
 
 
[[ca:Test de primalitat]]
 
[[de:Primzahltest]]
 
[[en:Primality test]]
 
[[eo:Primeca provo]]
 
[[es:Test de primalidad]]
 
[[fr:Test de primalité]]
 
[[hu:Prímteszt]]
 
[[it:Test di primalità]]
 
[[ja:素数判定]]
 
[[nl:Priemgetaltest]]
 
[[no:Primtallstest]]
 
[[pl:Test pierwszości]]
 
[[pt:Teste de primalidade]]
 
[[ru:Тест простоты]]
 
[[simple:Primality test]]
 
[[sv:Primtalstest]]
 
[[vi:Kiểm tra tính nguyên tố]]
 
[[zh:素性测试]]
 

Поточна версія на 07:10, 28 липня 2019

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

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

Найпростіший тест простоти полягає в такому: коли задане число 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 для i<c# де і належить до чисел, взаємно простих з 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 є складене число, то його можна оголосити імовірнісним простим.

 
Розглянемо складене число n = 65 (= 5 × 13). Брехуни Ферма для 65 — {1, 8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57, 64}. Брехуни Ойлера для 65 — {1, 8, 14, 18, 47, 51, 57, 64}, тоді як сильні брехуни для 65 —{1, 8, 18, 47, 57, 64}.

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

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

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

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

Близько початку 20 сторіччя дослідження показали, що тези з малої теореми Ферма можна використовувати для перевірки на простоту. Це призвело до появи тесту на простоту Поклінґтона. Однак, через те, що цей тест вимагає часткову факторизацію   його часова складність у найгіршому випадку все ще дуже велика. Першим детермінованим тестом простоти значно швидшим, ніж наївні методи, був циклотомічний тест; для часу його виконання отримано оцінку 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 належить до 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.

Див. такожРедагувати