Тест простоти: відмінності між версіями

[неперевірена версія][неперевірена версія]
Вилучено вміст Додано вміст
Рядок 31:
== Швидкі детерміновані тести ==
 
Близько початку 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>), але лише коли використовуємо деякі ще не доведені (але які як правило припускаються вірними) положення аналітичної теорії чисел. Це один з з найчастіше вживаних на практиці детермінованих тестів.