ни Мерсенн так и не решили этой задачи, хотя могли сделать это следующим образом: можно .вычислить число 3 mod (2 + 1), выполнив 32 операции возведения в квадрат по модулю 2 -I- 1, и получить результат, равный 3029026160; поэтому (по теореме, открытой Ферма в том же 1640 году!) 2 + 1 - не простое число. Данный аргумент не дает никакого представления о том, чему равны множители, но является ответом на поставленный Ферма вопрос.

Теорема Ферма представляет собой мощное средство анализа, которое дает возможность определить, что данное число не является простым. Если число п не простое, то всегда можно найти такое значение х < п, что ж""" mod пф1. Опыт показывает, что такое значение почти всегда находится очень быстро. Существует несколько редких значений числа п, для которых а;"- mod п часто равно единице, но тогда п имеет множитель, меньший (упр. 9).

Этот метод может быть расширен для доказательства того, что большое число п действительно является простым, если использовать следующую идею. Есля имеется число х, для которого порядок х по модулю п равен п - 1, то п-простое число. (Порядок числа х по модулю п - это наименьшее положительно целое число к, такое, что ж* mod п = 1; см. раздел 3.2.1.2.) Из этого условия следует, что числа х modn, ж"- modn различны и взаимно просты с п, а следовательно, это должны быть числа 1, 2, п-1, расположенные в некотором порядке. Таки.м образом, п не имеет ни одного собственного делителя. Если п - простое число, то такое число х (называемое первообразным корнем числа п) всегда существует (см. упр. 3.2.1.2-16). В действительности таких первообразных корней довольно много. Существует p{n - 1) таких чисел, и это достаточно большое число, так как п/(/з(п - 1) = 0{\og\ogn).

Чтобы определить, будет ли порядок х равен п-1, совсем необязательно вычислять а;* mod п для всех А; < п - 1. Порядок х будет равен п - 1 тогда и только тогда, когда выполняются условия

i) а;"- modn = 1;

ii) а;"-)/ mod пф I для всех простых чисел р, которые делят п-1.

Следовательно, х mod п = 1 тогда и только тогда, когда s кратно порядку числа х по модулю п. Поэтому, если оба условия выполняются и если к есть порядок х по модулю п, к является делителем п - 1, но не является делителем числа (п - 1)/р ни для одного простого множителя р числа п - 1. Значит, остается единственная возможность - к = п - 1. Этим завершается доказательство того, что условий (i) и (ii) достаточно, чтобы установить, является ли число п простым.

В упр. 10 показано, что для каждого из простых р можно использовать различные значения а;, а п все еще будет оставаться простым числом. Можно ограничиться этими соображениями относительно простых чисел для х, поскольку порядок произведения uv по модулю п делит наименьшее общее кратное порядков и и V согласно результатам упр. 3.2.1.2-15. Соблюдение условий (i) и (ii) можно эффективно проверить при помощи быстрых методов вычисления степеней чисел, которые рассматриваются в разделе 4.6.3. Но необходимо знать простые множители числа п - 1, поэтому возникает интересная ситуация, когда разложение на простые множители числа п зависит от разложения на простые множители числа п - 1.

Пример. Разложение на простые множители достаточно большого числа помогает уяснить идеи, рассмотренные до сих пор. Попробуем найти простые множители 65-разрядного числа 2* + 1. Проявив некоторую сообразительность, процесс разложения на простые множители можно начать, приняв во внимание интересное свойство исходного числа

2"" + 1 = (21° - 2" + l)(2i° + 2" + 1); (15)

это частный случай разложения 4а;* + 1 = (2а; -I- 2а; -I- 1)(2а; - 2а; -- 1), о котором Эйлер сообщал Гольдбаху (Goldbach) в 1742 году [Р. Н. Fuss, Correspondance Math, et Physique 1 (1843), 145]. Задача заключается в исследовании каждого из 33-разрядных множителей в соотношении (15).

Компьютерная программа легко обнаруживает, что 2° - 2 -I-1 = 5 857 по,

по = 37 866 809 061660 057 264 219 253 397 (16)

есть 29-разрядное число, не имеющее ни одного простого множителя, меньшего 1 ООО. Вычисления с многократной точностью, выполняемые при помощи алгоритма 4.6.ЗА, показывают, что

3"°- mod По = 1,

так что есть основание предполагать, что по-простое число. Конечно, не может быть и речи о том, чтобы для проверки, является ли по простым числом, проанализировать 10 миллионов миллионов или около того возможных делителей, но рассмотренный выше метод вполне пригоден для такой проверки. Следующая задача - разложение на простые множители числа по - 1. Преодолев некоторые трудности, компьютер сообщит, что

По - 1 = 2 • 2 19 • 107 • 353 • П1, nj = 13 191 270 754 108 226 049 301.

Здесь 3">~modni ф 1, поэтому пу-не простое число. Продолжая выполнение алгоритма А или В, можно получить следующие множители:

щ = 91813 пз, П2 = 143675413657196977.

Теперь 3"2~ mod П2 = 1, поэтому можно попытаться доказать, что пз-простое число. Приняв во внимание, что множители < 1000, получаем

П2 - 1 = 2-2-2-2-3-3-547-пз,

где пз = 1824 032 775457. Так как 3"" modns ф 1, приходим к заключению, что пз -составное число, а при помощи алгоритма А находим, что пз = 1103 • П4, где П4 = 1653 701519. Число П4 ведет себя, как простое (т. е. 3"*" mod П4 = 1), поэтому

П4 - 1 = 2 • 7 • 19 23 • 137 • 1973.

Итак, выполнено первое полное разложение на простые множители. Теперь мы готовы вернуться к предыдущей подзадаче, а именно - к доказательству того, что П4

есть простое число. Воспользовавшись процедурой, предложенной в упр. 10, вычислим следующие значения.

(17)

(Здесь "(1)" означает результат, равный 1, который не требуется вычислять, так как он может быть выведен из предыдущих вычислений.) Таким образом, -простое число, а число Пг - 1 полностью разложено на простые множители. Аналогичные вычисления показывают, что и П2 является простым числом; такое же полное разложение числа По - 1 на простые множители показывает наконец, после вычислений еще и значений из табл. (17), что по - простое число.

Последние три строки в табл. (17) представляют процесс поиска целого числа X, удовлетворяющего соотношению а;"- х"*~ = 1 (по модулю П4). Если П4-простое число, то шансы на успех равны только 50/50, так что случай, когда р = 2, является, как правило, наиболее трудным для проверки. Можно обойти эту часть вычислений, используя закон квадратичной взаимности (упр. 23), который гласит, например, что Ь~)/ = 1 (по модулю q), когда q есть простое число ± 1 (по модулю 5). Выбрав значение х = Ь, нельзя убедиться в том, что число П4 простое. Это сразу показывает вычисление П4 mod 5. Тем не менее из результата упр. 26 действительно следует, что при проверке, является ли число п простым, вовсе нет необходимости рассматривать случай, когдар = 2, несмотря на то что п- 1 делится на большие степени 2. Таким образом, три последние строки в табл. (17) необязательны.

Следующая величина, подлежащая разложению на простые множители,-другая часть соотношения (15), т. е.

П5 = 2° + 2" + 1.

Поскольку 3"*"imodn5 ф 1, известно, что П5 не является простым числом, и выполнение алгоритма В показывает, что

П5 = 843589-Пб, где Пб = 92 343993140277293096491917.

К сожалению, З"""mod пе Ф 1, поэтому остается 27-разрядное непростое число. Повторное обращение к алгоритму В могло бы истощить наше терпение (но не бюджет - мы чаще тратим свободное время в выходные дни, чем "рабочее время"). Пришло время ввести в действие метод решета. Алгоритм D, реализующий этот метод, может разбить число щ на два множителя:

Пб = 8 174 912 477117-23 528 569 104 401.