8.1. Тест на основе малой теоремы Ферма

При построении вероятностных критериев простоты возникает ряд типичных вопросов, которые удобно рассмотреть на примере, в качестве которого выберем тест на основе малой теоремы Ферма. Как известно, эта теорема утверждает, что если – простое, то для всех, взаимно простых с, выполняется условие (сравнение Ферма):.

Таким образом, если сравнение Ферма не выполнено, хотя бы для одного числа из множества , то– составное.

Тест на основе малой теоремы Ферма заключается в следующем.

Псевдослучайно выбираем вычет и проверяем условие. Если это условие не выполнено, значит,– составное. Проверяем сравнение Ферма. Если оно не выполняется, то число– составное. Иначе, повторяем тест для другого значения.

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

8.1.1. Основные свойства псевдопростых чисел

Назовем составное нечетное число псевдопростым по основанию, если пара чиселудовлетворяет сравнению Ферма.

Оказывается, можно показать, что для любого существует бесконечно много псевдопростых чисел по основанию.

Основные свойства псевдопростых чисел таковы.

Теорема [17]. Пусть – нечетное составное число. Тогда:

1) - псевдопростое по основаниюв том и только том случае, когдаи;

2) если – псевдопростое по основаниями, то– псевдопростое по основаниями;

3) множество образует мультипликативную подгруппу в мультипликативной группеобратимых элементов кольца вычетов по модулю;

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

Заметим, что . Таким образом, если тест Ферма выявляет составноепри одном основании, то существует не менееоснований с аналогичным свойством.

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

Докажем свойство г). Пусть и– основание, по которомуне является псевдопростым. Тогда для любогопара чиселне удовлетворяет сравнению Ферма. Поэтому количество оснований, для которыхне является псевдопростым, не меньше, чем количество элементов в.

Следовательно, если , то общее число элементов вокажется больше, что невозможно.

Таким образом, можно заключить, что если существует (даже не известное нам) основание, по которому не является псевдопростым, то, при повторении теста Фермараз, вероятность-кратного выбора оснований из множестване превосходит. В этом случае вероятность ошибки теста стремится к нулю с увеличением.

Проблема может возникнуть лишь в том случае, если является псевдопростым для всех (ненулевых) оснований. Оказывается, такие числа существуют. Они называются числами Кармайкла. Например, числом Кармайкла является число.

8.1.2. Свойства чисел Кармайкла

Свойства чисел Кармайкла описываются следующей теоремой.

Теорема (Кармайкл). Пусть – нечетное составное число. Тогда

1) если ,, тоне является числом Кармайкла;

2) если ,для, то– число Кармайкла в том и только том случае, когда;

3) если ,для– число Кармайкла, то.

Числа Кармайкла являются достаточно редкими. В пределах до 100000 существует лишь 16 чисел Кармайкла: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657 52633, 62745, 63973, 75361.