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

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

Определение


Псевдопростые числа


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

Малая теорема Ферма


 Малая теорема Ферма гласит, что если n — простое число, то для каждого числа a взаимно простого с n справедливо сравнение an11(modn).

Псевдопростые Ферма


 Составное число n называется псевдопростым числом Ферма по основанию a (взаимно простому с n), если выполнено сравнение an11(modn). Иными словами, составное число называют псевдопростым, если оно проходит тест Ферма по основанию a. Число, являющееся псевдопростым Ферма по каждому взаимно простому с ним основанию, называется числом Кармайкла.

Вариации


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

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

Свойства


Распределение


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

Таблицы с некоторыми псевдопростыми числами Ферма


Наименьшие псевдопростые Ферма


 Наименьшие псевдопростые Ферма для каждого основания a ≤ 200 приведены в таблице ниже; цвета различают числа по количеству различных простых делителей.
colspan=3 Основания b, по которым число n является псевдопростым
n
9
15
21
25
27
28
33
35
39
45
49
51
52
55
57
63
65
66
69
70
75
76
77
81
85
87
91
93
95
99
105
111
112
115
117
119
121
123
124
125
129
130
133
135
141
143
145
147
148
153
154
155
159
161
165
169
171
172
175
176
177

 Нужно отметить, что если p — простое, то p2 есть псевдопростое Ферма по основанию b тогда и только тогда, когда p — простое число Вифериха по основанию b. Например, — псевдопростое Ферма по основанию 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, \ldots
  Наименьшее основание b \textgreater 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, \ldots .

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


 Составное число 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, \ldots
  Если требуется, чтобы n \textgreater 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, \ldots

Приложения


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