Тест простоты Ферма в теории чисел — это тест простоты натурального числа n, основанный на малой теореме Ферма.
Если n — простое число, то оно удовлетворяет сравнению для любого a, которое не делится на n.
Выполнение сравнения является необходимым, но не достаточным признаком простоты числа. То есть, если найдётся хотя бы одно a, для которого , то число n — составное; в противном случае ничего сказать нельзя, хотя шансы на то, что число является простым, увеличиваются. Если для составного числа n выполняется сравнение , то число n называют псевдопростым по основанию a . При проверке числа на простоту тестом Ферма выбирают несколько чисел a. Чем больше количество a, для которых , тем больше шансы, что число n простое. Однако существуют составные числа, для которых сравнение выполняется для всех a, взаимно простых с n — это числа Кармайкла. Чисел Кармайкла — бесконечное множество, наименьшее число Кармайкла — 561. Тем не менее, тест Ферма довольно эффективен для обнаружения составных чисел.
При использовании алгоритмов быстрого возведения в степень по модулю время работы теста Ферма для одного a оценивается как O(log2n × log log n × log log log n), где n - проверяемое число. Обычно проводится несколько проверок с различными a.
Для улучшения этой статьи по математике желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .