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

м
м (→‎Ймовірнісні тести: replaced: Найбільш популярними → Найпопулярнішими)
== Швидкі детерміновані тести ==
 
Першим [[детермінований алгоритм|детермінованим]] тестом простоти значно швидшим, ніж наївні методи, був [[циклотомічний тест]]; для часу його виконання отримано оцінку [[BigНотація O notationЛандау|O]]((log&nbsp;''n'')<sup>''c''log(log(log(''n'')))</sup>), де ''n'' тестоване на простоту число, а ''c'' константа, незалежна від ''n''. Це повільніше, ніж поліноміальний час.
 
Для [[Тест простоти на основі еліптичних кривих|тесту простоти на основі еліптичних кривих]] можна отримати оцінку O((log&nbsp;''n'')<sup>6</sup>), але лише коли використовуємо деякі ще не доведені (але які як правило припускаються вірними) положення аналітичної теорії чисел. Це один з з найчастіше вживаних на практиці детермінованих тестів.
10 389

редагувань