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

м
нема опису редагування
м (робот косметичні зміни)
м
 
[[Тест простоти Міллера-Рабіна]] та [[Тест простоти Соловея-Штрассена]] є вдосконаленими варіантами, які визначають всі складені числа (це означає: для ''кожного'' складеного числа ''n'', принаймні 3/4 (Міллер-Рабін) або 1/2 (Соловей-Штрассен) чисел ''a'' є свідченнями складеності ''n'').
На ці методи часто падає вибір, бо вони набагато швидші, ніж інші загальні тести прототипростоти.
 
Леонард Адлеман та Хуанг запропонували варіант без помилки (але лише з очікуваним поліноміальним часом виконання) [[тест простоти на основі еліптичних кривих|тесту простоти на основі еліптичних кривих]]. На відміну від інших імовірнісних тестів, цей алгоритм дає сертифікат простоти, а тому може бути використаний для доведення простоти числа. Цей алгоритм занадто повільний на практиці.
Якщо вважається вірною [[узагальнена гіпотеза Рімана]], то тест Міллера-Рабіна можна звести до детермінованої версії з часом виконання O((log&nbsp;''n'')<sup>4</sup>). На практиці, цей алгоритм повільніший, ніж два інших для величин чисел, з якими можна реально оперувати.
 
У 2002, Маніндра Агравал, Нітін Саксена та Нірай Кайал описали новий детермінований тест простоти, [[AKS тест прототипростоти]], який як доведено виконується за O((log&nbsp;''n'')<sup>12</sup>). Крім того, якщо вірна [[прості Софі Жермен|гіпотеза Харді-Літвулда]], яку вважають справедливою, то він виконується за O((log&nbsp;''n'')<sup>6</sup>). Отже, маємо перший детермінований тест простоти з доведеним [[поліноміальний час|поліноміальним часом виконання]]. На практиці, цей алгоритм повільніший, ніж імовірнісні методи.
 
== Складність ==
35 547

редагувань