Тест простоти Ферма: відмінності між версіями

[перевірена версія][перевірена версія]
Вилучено вміст Додано вміст
Немає опису редагування
Немає опису редагування
Рядок 1:
'''Тест простоти Ферма''' — це [[увипадковлений алгоритм|імовірнісна]] перевірка для визначення чи є число [[ймовірноЙмовірно просте число|ймовірним простим]].
 
==Концепція==
Рядок 35:
 
==Вада==
Існує безкінечно багато значень <math>n</math> (відомі як [[Число Кармайкла|числа Кармайкла]]) для яких <u>всі</u> значення <math>a</math> для яких <math>gcd(a, n) = 1</math> — брехуни. Хоча чисел Кармайкла істотно менше ніж простих,,<ref>Erdös' upper bound for the number of Carmichael numbers is lower than the prime number function n/log(n)</ref> їх достатньо, щоб часто замість тесту Ферма використовували інші [[тест простоти|тести простоти]] такі як [[тест простоти Міллера-Рабіна]] та [[Тест Соловея — Штрассена|тест простоти Соловея-Штрассена]].
 
Загалом, якщо <math>n</math> не є числом Кармайкла, тоді щонайменше половина всіх