10 389
редагувань
Відмінності між версіями «Тест простоти»
→Ймовірнісні тести
м (→Швидкі детерміновані тести: вікіфікація) |
|||
|
Після низки повторень, якщо не отримано, що ''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]].
[[Тест простоти Міллера-Рабіна]] та [[
Леонард Адлеман та Хуанг запропонували варіант без помилки (але лише з очікуваним поліноміальним часом виконання) [[тест простоти на основі еліптичних кривих|тесту простоти на основі еліптичних кривих]]. На відміну від інших імовірнісних тестів, цей алгоритм дає сертифікат простоти, а тому може бути використаний для доведення простоти числа. Цей алгоритм занадто повільний на практиці.
| |||