Псевдопростые числа Ферма — составные числа, проходящие тест Ферма. Названы в честь французского математика Пьера Ферма. В теории чисел псевдопростые числа Ферма составляют важнейший класс псевдопростых чисел.
Определение
Псевдопростые числа
Составное число называется псевдопростым, если оно удовлетворяет некоторому необходимому (но не достаточному) условию простоты числа, то есть если оно обладает некоторыми свойствами простого числа.
Малая теорема Ферма
Малая теорема Ферма гласит, что если n — простое число, то для каждого числа a взаимно простого с n справедливо сравнение a n − 1 ≡ 1 ( mod n ) {displaystyle a^{n-1}equiv 1{pmod {n}}} .
Псевдопростые Ферма
Составное число n называется псевдопростым числом Ферма по основанию a (взаимно простому с n), если выполнено сравнение a n − 1 ≡ 1 ( mod n ) {displaystyle a^{n-1}equiv 1{pmod {n}}} . Иными словами, составное число называют псевдопростым, если оно проходит тест Ферма по основанию a. Число, являющееся псевдопростым Ферма по каждому взаимно простому с ним основанию, называется числом Кармайкла.
Вариации
Существуют некоторые вариации определения:
- Некоторые источники требуют, чтобы псевдопростое число было нечетным, так как четное число очевидно является составным.
- Каждое нечётное число q {displaystyle q} удовлетворяет a q − 1 ≡ 1 ( mod q ) {displaystyle a^{q-1}equiv 1{pmod {q}}} для a = q − 1 {displaystyle a=q-1} , поэтому в таком случае новой информации о числе q {displaystyle q} мы не получим. Это исключается в определении, данном Крэндаллом и Померансом: Составное число n {displaystyle n} является псевдопростым числом Ферма по основанию a {displaystyle a} , если a n − 1 ≡ 1 ( mod n ) {displaystyle a^{n-1}equiv 1{pmod {n}}} и 2 ≤ a ≤ n − 2. {displaystyle 2leq aleq n-2.}
Свойства
Распределение
Существует бесконечно много псевдопростых чисел по данному основанию (более того существует бесконечно много сильных псевдопростых и бесконечно много чисел Кармайкла), но они довольно редки. Есть только три псевдопростых Ферма по основанию 2 меньше 1000, 245 меньше одного миллиона, и только 21 853 меньше, чем 25 миллиардов.
Таблицы с некоторыми псевдопростыми числами Ферма
Наименьшие псевдопростые Ферма
Наименьшие псевдопростые Ферма для каждого основания a ≤ 200 приведены в таблице ниже; цвета различают числа по количеству различных простых делителей.
Числа Пуле
Псевдопростые Ферма по основанию 2 называют числами Пуле, по имени бельгийского математика Пола Пуле. Разложение на множители шестидесяти первых чисел Пуле, в том числе тринадцати чисел Кармайкла (выделены жирным шрифтом), ниже в таблице.
Число Пуле, все делители d которого делят также число 2d − 2, называется суперчислом Пуле. Существует бесконечно много чисел Пуле, не являющихся суперчислами Пуле.
Первые псевдопростые числа Ферма (до 10000) по основанию a
Более подробная информация о псевдопростых числах Ферма по основаниям 31 — 100 представлена в статьях A020159 — A020228 Энциклопедии целочисленных последовательностей.
Основания, по которым число является псевдопростым
Ниже приведена таблица всех оснований b< n, для которых n — псевдопростое число Ферма (все составные числа являются псевдопростыми по основанию 1, а для b > n решение просто сдвигается на k * n, где k > 0), если составное число n не указано в таблице, то оно является псевдопростым только по основанию 1, или по основаниям, которые сравнимы с 1 (mod n), то есть число оснований b равно 1. Таблица составлена для n < 180.
Нужно отметить, что если p — простое, то p2 есть псевдопростое Ферма по основанию b тогда и только тогда, когда p — простое число Вифериха по основанию b. Например, 10932 = 1 194 649 — псевдопростое Ферма по основанию 2.
Количество оснований b для n (для простых n, число оснований b должно быть равно n-1, так как все b удовлетворяют малой теореме Ферма):
1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 4, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 4, 1, 36, 1, 4, 1, 40, 1, 42, 1, 8, 1, 46, 1, 6, 1, … (последовательность A063994 в OEIS)Наименьшее основание b > 1, для которого n — псевдопростое (или простое):
2, 3, 2, 5, 2, 7, 2, 9, 8, 11, 2, 13, 2, 15, 4, 17, 2, 19, 2, 21, 8, 23, 2, 25, 7, 27, 26, 9, 2, 31, 2, 33, 10, 35, 6, 37, 2, 39, 14, 41, 2, 43, 2, 45, 8, 47, 2, 49, 18, 51, … (последовательность A105222 в OEIS).Слабые псевдопростые
Составное число n, для которого справедливо сравнение bn = b (mod n), называется слабым псевдопростым числом Ферма по основанию b (здесь b не обязано быть взаимно простым с n). Наименьшие слабые псевдопростые по основанию b:
4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 6, 4, 4, 6, 46, 4, 4, 10, … (последовательность A000790 в OEIS)Если требуется, чтобы n > b, тогда:
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, … (последовательность A239293 в OEIS)Приложения
Благодаря своей редкости, такие псевдопростые числа имеют важные практические применения. Например, для криптографических алгоритмов с открытым ключом, таких как RSA, требуется возможность быстро находить большие простые числа. Обычный алгоритм для генерации простых чисел должен генерировать случайные нечётные числа и проверять их на простоту. Тем не менее детерминированные тесты простоты работают медленно. Если мы готовы допустить сколь угодно малую вероятность того, что найденное число не простое, но псевдопростое, можно использовать гораздо более быстрый и простой тест Ферма.