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