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

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

Определение


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


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

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


 Малая теорема Ферма гласит, что если 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, требуется возможность быстро находитьбольшие простые числа. Обычный алгоритм для генерации простых чиселдолжен генерировать случайные нечётные числа и проверять их на простоту.Тем не менее детерминированные тесты простоты работают медленно. Если мыготовы допустить сколь угодно малую вероятность того, что найденноечисло не простое, но псевдопростое, можно использовать гораздо болеебыстрый и простой тест Ферма.