множители имеет вид

8616460 799= (х-у) (х +у) = 89 681-96079.

Это значение N интересно тем, что английским экономистом и логиком У. С. Дживонсом (W. S. Jevons) в хорошо известной книге оно было введено следующим образом: "По данным двум числам можно найти их произведение простым и надежным способом, но совсем другое дело, когда для большого числа необходимо найти его множители. Можно ли сказать, какие два числа были перемножены, чтобы получилось число 8 616 460 799? Я думаю, что вряд ли кто-либо, кроме меня, знает это". [The Principles of Science (Macmillan, 1874), Chapter 7.] Однако, как следует из вышесказанного. Ферма смог разложить это число на простые множители на обратной стороне конверта меньше чем за десять минут! Основная мысль Дживонса о сложности разложения чисел на простые множители по сравнению с их перемножением справедлива, но только в случае, когда мы имеем дело с произведением чисел, не настолько близких друг к другу.

Вместо модулей, рассматриваемых в уравнении (14), можно использовать любые степени различных простых чисел. Например, если взять 25 вместо 5, то возможные значения величины х mod 25 будут равняться О, 5, 7, 10, 15, 18 и 20. Это дает больше информации, чем (14). В общем случае можно получить больше информации, вьшолняя операции по модулю р, чем по модулю р, при нечетных р, если - 7V = О (по модулю р) имеет решение х.

Рассмотренный модулярный метод называется методом решета (сита) (sieve procedure), так как можно представить, что все целые числа проходят через "решето" , пропускающее только те значения, для которых х mod 3 = 0; затем эти числа просеиваются через другое сито, которое пропускает только числа, для которых X mod 5 = О, 2 или 3, и т. д. Каждое сито в отдельности отсеивает примерно половину оставшихся значений (см. упр. 6). Когда же просеивание ведется при помощи попарно взаимно простых модулей, то на основании китайской теоремы об остатках (теорема 4.3.2С) каждое сито работает независимо от остальных. Поэтому, если вьшолнять просеивание относительно, скажем, 30 различных простых чисел, то для того, чтобы определить, будет ли величина х" - N полным квадратом для у, достаточно из каждых 2° величин проверить только одну.

Алгоритм D {Разложение на простые множители методом решета). По данным нечетным числам N этот алгоритм определяет наибольший множитель числа 7V, меньший или равный y/N. В процедуре используются попарно взаимно простые модули ш1, тг, т, которые также взаимно просты с N. Предположим, что доступны г таблиц просеивания 5[г, j], О < j < mj, 1 < г < г, где

S[i,j] = [j - N = y (по модулю mj) имеет решение у].

D1. [Начальная установка.] Присвоить х <- \VN\ и ki <- {-х) mod mj при 1 <г <г. (Во время выполнения этого алгоритма индексные переменные ki, к2, ..., К будут установлены таким образом, что fcj = {-х) mod mj.)

D2. [Просеять.] Если 5[i, ki] = 1 при 1 < г < г, то перейти к шагу D4.

D3. [Найти х] Присвоить х <- х + 1 и fcj +- (fcj - 1) mod mj при 1 < г < г. Возвратиться к шагу D2.

D4. [Проверить - N] Присвоить у <- [ч/ж - N\ или ["ч/ж - 7V]. Если = а; - 7V, то (а; - у) - искомый множитель. Завершить выполнение алгоритма; в противном случае возвратиться к шагу D3.

Ускорить выполнение этой процедуры можно различными способами. Например, выше было отмечено, что для случая N mod 3 = 2 значение х должно быть кратным 3; можно положить, что х = Зх, и использовать другое сито, соответствующее х, повысив скорость выполнения операций в три раза. Если N mod 9 = 1, 4 или 7, то X должно быть сравнимо с ±1, ±2 или ±4 (по модулю 9); так что можно, пропустив числа через два сита (одно для х, а другое - для х", где а; = 9а; -1- о и а; = 9а;" - а), повысить скорость в 4 раза. Если 7Vmod4 = 3, то а; mod 4 известно и скорость повысится еще в 4 раза; в другом случае, когда N mod 4=1, X должно быть нечетным, что повысит скорость в два раза. Еще один способ удвоения скорости (ценой расширения объема применяемой памяти) заключается в объединении пары модулей путем использования гпг-к гпк вместо тпк для 1 < к < г.

Еще более важный способ повышения скорости выполнения алгоритма D сос/то-ит в использовании булевых операций, которые реализованы в большинстве двоичных компьютеров. Будем считать, что MIX представляет собой двоичный компьютер с длиной слова 30 бит. Таблицы S[i,ki] можно хранить в памяти так, чтобы на каждую позицию приходился один бит; таким образом, в одном слове можно хранить 30 значений. Операцию AND, которая заменяет к-й бит накопителя нулем, если к-й бит заданного слова в памяти есть нуль для 1 < А; < 30, можно использовать для одновременной обработки 30 значений х\ Для удобства можно сделать несколько копий таблиц S[i, j] с тем, чтобы элементы таблицы для занимали 1ст(ш, 30) бит. Тогда таблицы просеивания для каждого модуля заполнят некоторое целое число слов. При таких предположениях выполнение основного цикла алгоритма D 30 раз эквивалентно такой последовательности команд.

По существу, количество циклов, необходимых для выполнения 30 итераций, равно 2 ч- 8г; в случае, если г = И, это означает, что на выполнение одной итерации

затрачивается три цикла, как и в алгоритме С, но в алгоритме С, кроме того, выполняется еще у = {v - и) итераций.

Если бы элементы в таблице для занимали не целое число слов, то на каждой итерации необходимо было бы выполнять сдвиг элементов таблицы, чтобы биты были расположены должным образом. Это привело бы к добавлению в основной цикл множества дополнительных команд и, вероятно, сделало бы выполнение программы слишком медленным для всех значений v/u > 100 по сравнению с алгоритмом С (упр. 7).

Процедуры просеивания можно применять к множеству других задач, не обязательно связанных с выполнением арифметических действий. Обзор этих методов выполнен Марвином Ч. Вундерлихом (Marvin С. Wunderlich) и приведен в JACM 14 (1967), 10-19.

В 19 веке для разложения чисел на простые множители Ф. У. Лоуренс (F. W. Lawrence) предложил конструкцию специальных просеивающих машин [Quart. J. of Pure and Applied Math. 28 (1896), 285-311], a в 1919 году Э. О. Карисан (Е. О. Carissan) дополнил такое устройство еще 14-ю модулями. [С интересной историей того, как были заново открыты и сохранены для потомства давно забытые сита Карисана, можно ознакомиться в работе Shallit, Williams, Morain, Math. Intelligencer 17,3 (1995), 41-47.] Много различных просеивающих машин было разработано и использовалось в течение 1926-1989 годов Д. Г. Лемером и его сотрудниками, которые начали с велосипедных цепей, а позже использовали фотоэлектронные элементы и другие технологии (см., например, АММ 40 (1933), 401-406). Электронное решето Лемера, использующее линию задержки, которое было запущено в эксплуатацию в 1965 году, обрабатывает один миллион чисел в секунду. К 1995 году стало возможным сконструировать машину, которая просеивает 6144 млн чисел в секунду, вьшолняя 256 итераций на шагах D2 и D3 за почти 5.2 не. [См. Lukes, Patterson, Williams, Meuw АгсЫе/voor Wiskunde (4) 13 (1995), 113-139.] Д. Г. Лемер и Эмма Лемер (D. Н. and Emma Lehmer) описали в Math. Сотр. 28 (1974), 625-635, другой способ разложения на простые множители с использованием решета.

Проверка принадлежности чисел к простым. Из всех рассмотренных до сих пор алгоритмов ни один не может эффективно определить, является ли большое число п простым. К счастью, существуют другие способы решения этой задачи. Эффективные способы были разработаны Э. Люка (Е. Lucas) и др., в частности Д. Г. Лемером [см. Bull. Amer. Math. Soc. 33 (1927), 327-340]. Согласно теореме Ферма (теорема 1.2.4F)

а;Р~ modp = 1,

когда р - простое число и а; не кратно р. При этом имеются эффективные методы вычисления а;"~ mod п, требующие только O(logn) операций умножения по модулю п. (Они будут исследоваться в разделе 4.6.3.) Поэтому зачастую можно определить, что п не является простым, убедившись, что данное условие не выполняется.

Например, однажды Ферма установил, что числа 2 -I-1, 2 --1, 2"* -I-1, 2* Ч-1 и 24-1 являются простыми. В письме Мерсенну (Mersenne), написанному в 1640 году. Ферма предположил, что 2 + 1-всегда простое число, и сообщил, что он не в состоянии определить, является ли простым число 4 294 967 297 = 2-1-1. Ни Ферма,