§ 4. Простое или составное?

§ 4. Простое или составное?

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

Пусть N — исследуемое число. Выберем небольшое число а взаимно простое с N. Удобно в качестве числа а брать некоторое небольшое простое число, не являющееся делителем числа N, например, 2, 3 или 5. Если бы N было простым числом, то для него было бы справедливо сравнение

а^N-1 ? 1 (mod N), (8.4.1)

в соответствии с малой теоремой Ферма. Следовательно, если мы проверим это сравнение (8.4.1) и убедимся, что оно не выполняется, то можно утверждать, что число N является составным.

Пример. Возьмем N = 91 и выберем а = 2. Тогда

a^N-1 = 2⁹⁰ = 2⁶⁴ • 2¹⁶ • 2⁸ • 2²

Более того,

2⁸ = 256 ? -17 (mod 91),

2¹⁶ = (2⁸)² ? (-17)² = 289 ? 16 (mod 91),

2³² = (2¹⁶)² ? (16)² = 256 ? -17 (mod 91),

2⁶⁴ = (2³²)² ? (-17)² = 289 ? 16 (mod 91),

так что

2⁹⁰ = 2⁶⁴ • 2¹⁶ • 2⁸ • 2² ? 16 • 16 • (-17) • 4 ? 64 ? 1 (mod 91).

Отсюда делаем вывод, что число N составное. И действительно, 91 = 7 • 13.

Наш пример слишком прост, чтобы на нем увидеть действительную силу метода. Составив соответствующую программу для ЭВМ, можно таким способом установить, что некоторые очень большие числа являются составными. К сожалению, этот метод не указывает на то, какие именно множители имеет данное число, следовательно, во многих случаях мы знаем, что число составное, однако не имеем представления о его делителях.

В особенности это относится к числам Ферма

F_n = 2^2?+1,

которые мы обсуждали в § 3 главы 2. Как мы уже отмечали, они являются простыми для n = 0, 1, 2, 3, 4. Чтобы проверить число

F₅ = 2^2?5 + 1 = 2³² + 1 = 4294967297

с помощью теоремы Ферма, можно взять а = 3. Если бы F₅ было простым числом, мы бы имели, что

З^2?32 ? 1 (mod F₅). (8.4.2)

Чтобы вычислить остаток степени в левой части сравнения, мы должны возвести число 3 в квадрат 32 раза и всякий раз привести полученный результат по модулю F₅. Мы избавим читателя от подробностей. Можно найти, что сравнение (8.4.2) не выполняется, следовательно, число F₅ является составным. Известный множитель 641 был найден путем проб. Тот же самый метод был использован для того, чтобы показать, что несколько больших чисел Ферма не являются простыми. Для некоторых из них нам известны множители, а для других нет.

Если сравнение (8.4.1) выполняется для некоторого числа а, взаимно простого с числом N, то число N может как быть простым, так и не быть им. При этом случаи, когда сравнение выполняется для составного числа N, являются исключительными, поэтому при выполнении сравнения мы можем быть почти уверены в том, что число N — просто. Однако для многих целей хотелось бы знать наверняка, является ли данное число простым. Это удается сделать с помощью усовершенствованного метода, основанного на следующем замечании: N является простым числом в том случае, если сравнение (8.4.1) выполняется для степени N — 1, но не выполняется ни для какой степени, являющейся делителем числа N — 1.

Имеется другой подход, эффективный для не слишком больших чисел N. Возьмем а = 2. Американские математики Пуль и Лемер нашли с помощью ЭВМ все значения чисел N ? 100 000, исключительные в том смысле, что выполняется сравнение

2^N-1 ? 1 (mod N), (8.4.3)

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

С помощью таблиц Пуля и Лемера можно определить простоту любого числа N ^ 100 000 000. Сначала проверяется выполнимость сравнения (8.4.3). Если это сравнение не выполняется, то число N — составное. Если же это сравнение выполняется и число N есть в таблицах, то оно также составное, и мы можем прочесть в таблицах его простой множитель. И наконец, если сравнение (8.4.3) выполняется и числа N нет в таблицах, то оно простое.

Наименьшим составным числом, удовлетворяющим сравнению (8.4.3), является

N = 341 = 11 • 31.

В пределах 1000 существуют еще два таких числа,

а именно:

N = 561= 3 • 11 • 17,

N = 645 = 3 • 5 • 43.

Число 561 является замечательным, так как соответствующее сравнение (8.4.1) выполняется для каждого целого числа а, взаимно простого с числом N. Мы называем такие особые числа числами, имеющими свойство Ферма. По таким числам в последнее время было проведено огромное количество исследований.