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