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

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

редагувань