Псевдопростые числа Ферма — Википедия

Псевдопросты́е чи́сла Ферма́ — составные числа, проходящие тест Ферма. Названы в честь французского математика Пьера Ферма. В теории чисел псевдопростые числа Ферма составляют важнейший класс псевдопростых чисел.

Составное число называется псевдопростым, если оно удовлетворяет некоторому необходимому (но не достаточному) условию простоты числа, то есть если оно обладает некоторыми свойствами простого числа.

Малая теорема Ферма гласит, что если n — простое число, то для каждого числа a взаимно простого с n справедливо сравнение ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$.

Составное число n называется псевдопростым числом Ферма по основанию a (взаимно простому с n), если выполнено сравнение ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$. Иными словами, составное число называют псевдопростым, если оно проходит тест Ферма по основанию a^[1]. Число, являющееся псевдопростым Ферма по каждому взаимно простому с ним основанию, называется числом Кармайкла.

Существуют некоторые вариации определения:

• Некоторые источники требуют, чтобы псевдопростое число было нечетным^[2], так как четное число очевидно является составным.
• Каждое нечётное число ${\displaystyle q}$ удовлетворяет ${\displaystyle a^{q-1}\equiv 1{\pmod {q}}}$ для ${\displaystyle a=q-1}$, поэтому в таком случае новой информации о числе ${\displaystyle q}$ мы не получим. Это исключается в определении, данном Крэндаллом и Померансом^[3]: Составное число ${\displaystyle n}$ является псевдопростым числом Ферма по основанию ${\displaystyle a}$, если ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$ и ${\displaystyle 2\leq a\leq n-2.}$

Существует бесконечно много псевдопростых чисел по данному основанию (более того существует бесконечно много сильных псевдопростых^[4] и бесконечно много чисел Кармайкла^[5]), но они довольно редки^[6]. Есть только три псевдопростых Ферма по основанию 2 меньше 1000, 245 меньше одного миллиона, и только 21 853 меньше, чем 25 миллиардов^[4].

Наименьшие псевдопростые Ферма для каждого основания a ≤ 200 приведены в таблице ниже; цвета различают числа по количеству различных простых делителей^[7].

Псевдопростые Ферма по основанию 2 называют числами Пуле, по имени бельгийского математика Пола Пуле^{[англ.][8]}. Разложение на множители шестидесяти первых чисел Пуле, в том числе тринадцати чисел Кармайкла (выделены жирным шрифтом), ниже в таблице.

Число Пуле, все делители d которого делят также число 2^d − 2, называется суперчислом Пуле. Существует бесконечно много чисел Пуле, не являющихся суперчислами Пуле^[9].

Более подробная информация о псевдопростых числах Ферма по основаниям 31 — 100 представлена в статьях A020159 — A020228 Энциклопедии целочисленных последовательностей^[10].

Ниже приведена таблица всех оснований b< n, для которых n — псевдопростое число Ферма (все составные числа являются псевдопростыми по основанию 1, а для b > n решение просто сдвигается на k * n, где k > 0), если составное число n не указано в таблице, то оно является псевдопростым только по основанию 1, или по основаниям, которые сравнимы с 1 (mod n), то есть число оснований b равно 1. Таблица составлена для n < 180^[11].

Нужно отметить, что если p — простое, то p² есть псевдопростое Ферма по основанию b тогда и только тогда, когда p — простое число Вифериха по основанию b. Например, 1093² = 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, для которого справедливо сравнение bⁿ = b (mod n), называется слабым псевдопростым числом Ферма по основанию b (здесь b не обязано быть взаимно простым с n)^[13]. Наименьшие слабые псевдопростые по основанию 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, требуется возможность быстро находить большие простые числа^[14]. Обычный алгоритм для генерации простых чисел должен генерировать случайные нечётные числа и проверять их на простоту. Тем не менее детерминированные тесты простоты работают медленно. Если мы готовы допустить сколь угодно малую вероятность того, что найденное число не простое, но псевдопростое, можно использовать гораздо более быстрый и простой тест Ферма.

• Ричард Крэндалл, Карл Померанс. Простые числа: Криптографические и вычислительные аспекты. — Книжный дом "ЛИБРОКОМ", 2011. — P. 154—158, 438—441.
• Carl Pomerance; John L. Selfridge^[англ.], Samuel S. Wagstaff, Jr^[англ.]. The pseudoprimes to 25·10⁹ (англ.) // Mathematics of Computation^[англ.] : journal. — 1980. — July (vol. 35, no. 151). — P. 1003—1026. — doi:10.1090/S0025-5718-1980-0572872-7.

Эта статья входит в число добротных статей русскоязычного раздела Википедии.