Введение

Составное число, удовлетворяющее тесту Ферма на простоту.
В теории чисел псевдопростые числа Ферма образуют наиболее важный класс псевдопростых чисел, основанный на малой теореме Ферма.

Слабые псевдопримы

Составное число n, удовлетворяющее этому условию, называется слабым псевдопростым числом по основанию b. Псевдопростое число по основанию a (в обычном определении) удовлетворяет этому условию. И наоборот, слабое псевдопростое число, взаимно простое с основанием, является псевдопростым в обычном смысле, в противном случае это может и не быть так. Наименьшие слабые псевдопростые числа по основанию b = 1, 2: 4, 341, 6, 4, 4, 6, 6, 4, 6, 10, 4, 14, 6, 4, 4, 6, 6, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 6, 9, 4, 38, 6, 4, 6, 4, 6, 4, 6, 46, 4, 4, 10, …

Все члены меньше или равны наименьшему числу Кармайкла, 561. За исключением 561, в указанной последовательности могут встречаться только полупростые числа, но не все полупростые числа, меньшие 561, встречаются. Полупростое число pq (p ≤ q), меньшее 561, встречается в указанных последовательностях тогда и только тогда, когда p − 1 делит q − 1. (см.) Кроме того, наименьшее псевдопростое число по основанию n (также не обязательно превосходящее n) обычно также является полупростым, первый контрпример – (648) = 385 = 5 × 7 × 11. Если требуется n > b, то они (для b = 1, 2, …) следующие: 4, 341, 6, 6, 10, 10, 14, 9, 12, 15, 15, 22, 21, 15, 21, 20, 34, 25, 38, 21, 28, 33, 33, 25, 28, 27, 39, 36, 35, 49, 49, 33, 44, 35, 45, 42, 45, 39, 57, 52, 82, 66, 77, 45, 55, 69, 65, 49, 56, 51, …

Числа Кармайкла являются слабыми псевдопростыми числами для всех оснований. Наименьшее четное слабое псевдопростое число по основанию 2 равно 161038 (см.).

Псевдопримы Эйлера и Якоби

Другой подход заключается в использовании более точных понятий псевдопервичности, например, сильных псевдопростых чисел или псевдопростых чисел Эйлера — Якоби, для которых не существует аналогов чисел Кармайкла. Это приводит к вероятностным алгоритмам, таким как тест простоты Соловая — Страссена, тест простоты Бейли — PSW и тест простоты Миллера — Рабина, которые генерируют так называемые простые числа промышленного качества. Простые числа промышленного качества — это целые числа, для которых простота не была "сертифицирована" (то есть строго доказана), но они прошли тестирование, например, тест Миллера — Рабина, который имеет ненулевую, но сколь угодно малую вероятность ошибки.

Приложения

Редкость таких псевдопростых чисел имеет важные практические последствия. Например, алгоритмы криптографии с открытым ключом, такие как RSA, требуют возможности быстро находить большие простые числа. Обычно для генерации простых чисел генерируют случайные нечетные числа и проверяют их на простоту. Однако детерминированные тесты на простоту работают медленно. Если пользователь готов допустить сколь угодно малую вероятность того, что найденное число окажется не простым, а псевдопростым, можно использовать гораздо более быстрый и простой тест простоты Ферма.