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

Перейти до навігації Перейти до пошуку
16 байтів вилучено ,  6 років тому
м
свідчення -> свідок
м (Removing Link FA template (handled by wikidata))
м (свідчення -> свідок)
 
#Випадково вибрати число ''a''.
#Перевірити певну рівність, що містить ''a'' та задане число ''n''. Якщо рівність не виконується, то ''n'' є [[складене число]], ''a'' називають ''свідченнямсвідком'' складеності, і тест зупиняється.
#Виконувати крок 1, поки не буде досягнуто потрібної певності.
 
 
[[Файл:брехуни_щодо_простоти.png|міні|right|200пкс|Розглянемо складене число 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|криптографічного алгоритму з відкритим ключем RSA]].
 
[[Тест простоти Міллера-Рабіна]] та [[тест простоти Соловея-Штрассена]] є вдосконаленими варіантами, які визначають всі складені числа (це означає: для ''кожного'' складеного числа ''n'', принаймні 3/4 (Міллер-Рабін) або 1/2 (Соловей-Штрассен) чисел ''a'' є свідченнямисвідками складеності ''n''). На ці методи часто падає вибір, бо вони набагато швидші, ніж інші загальні тести простоти.
 
Леонард Адлеман та Хуанг запропонували варіант без помилки (але лише з очікуваним поліноміальним часом виконання) [[тест простоти на основі еліптичних кривих|тесту простоти на основі еліптичних кривих]]. На відміну від інших імовірнісних тестів, цей алгоритм дає сертифікат простоти, а тому може бути використаний для доведення простоти числа. Цей алгоритм занадто повільний на практиці.
10 470

редагувань

Навігаційне меню