83. [Множитель найден?] Присвоить д <- gcd(a; - х, п). Если = 1, то перейти к шагу В4; в противном случае вывести д. Теперь, если д = п, алгоритм завершается (его выполнение прерывается, ибо нам известно, что п не является простым числом). В противном случае присвоить п <- п/д, х <- х mod п, х <- х mod п и возвратиться к шагу В2. (Заметим, что д может и не быть простым числом - это подлежит проверке. В каждом случае, когда д - не простое число, его простые множители не могут быть определены при помощи этого алгоритма.)

84. [Продвинуться.] Присвоить к <- к - 1. Если А; = О, то присвоить х <г- х, I <- 21, к<- I. Присвоить X <- (х + 1) mod п и возвратиться к шагу ВЗ.

В качестве примера алгоритма В попробуем снова разложить на простые множители число = 25 852. В результате третьей итерации шага ВЗ будет получен следующий результат: = 4 (не является простым). Еще после шести итераций алгоритм находит множитель = 23. В этом примере алгоритм не различил сам себя, но он, конечно же, был разработан для поиска больших простых множителей. Алгоритм А на поиск больших простых множителей затрачивает гораздо больше времени, но в том, что касается определения малых простых множителей, к нему нет никаких претензий. На практике сначала некоторое время вьшолняется алгоритм А, а затем запускается алгоритм В.

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

р = 999863 999883 999907 999917 999931 999953 999959 999 961 999979 999983 т{р) = 276 409 2106 1561 1593 1091 474 1819 395 814

Экспериментальным путем установлено, что среднее значение т{р) примерно равно 2vp и никогда не превышает 12р, когда р < 1000000. При р < 10® максимум т(р) равен т(874 771) = 7685. Максимум функции m{p)/s/p достигается при р = 290047 и т{р) = 6 251. На основании этих результатов почти все 12-разрядные числа можно разложить на простые множители быстрее чем за 2 ООО итераций алгоритма В (сравните с 75000 операций деления, требуемых для выполнения алгоритма А).

Время на каждой итерации алгоритма В, в основном, затрачивается на выполнение умножения и деления с многократной точностью на шаге В4 и на вычисление наибольшего общего делителя на шаге ВЗ. Выполнение этих операций может быть ускорено за счет применения методики "умножения Монтгомери" (см. упр. 4.3.1-41). Более того, в случае, когда операция нахождения наибольшего общего делителя вьшолняется медленно, Поллард предложил ускорить процесс путем накапливания произведения по модулю п, скажем, десяти последовательных значений {х - х) перед тем, как искать наибольший общий делитель. Таким образом, 90% операций нахождения наибольшего общего делителя заменяется одним умножением по модулю Л ценой некоторого увеличения вероятности того, что решение при этом не будет найдено. Поллард также предложил начинать вычисления на шаге В1 с m = д, а не с m = 1, где q равно одной десятой от количества итераций, которые планируется реализовать.

В тех редких случаях, когда для больших N результат не был найден, можно применить функцию f{x) = x+c при некотором с Ф О или 1. Следует избегать

также значения с = -2, поскольку рекуррентное уравнение x+i = ~ 2 имеет решение в виде Хт = г" + г~". Похоже, что другие значения параметра с не приводят к возникновению простых связей по модулю р и все они должны быть удовлетворительными при подходящих начальных значениях.

Ричард Брент применил эту модификацию алгоритма В для нахождения простого множителя 1238 926361552897 числа 2 + 1. [См. Math. Сотр. 36 (1981), 627-630; 38 (1982), 253-255.]

Метод Ферма. Другой подход к решению проблемы разложения чисел на простые множители, который в 1643 году предложил Пьер де Ферма (Pierre de Fermat), более подходит для поиска больших множителей, нежели малых. [Описание метода, данное самим Ферма и переведенное на английский язык, можно найти в книге Л. Е. Диксона (L. Е. Dickson) History of the Theory of Numbers 1 (Carnegie Inst, of Washington, 1919), 357.]

Допустим, что N = uv, где и < v. Для практических целей можно положить, что TV - нечетное число. Это означает, что и и v тоже нечетны. Можно также положить, что

x = iu + v)/2, y = iv-u)/2, (12)

N = x -у, 0<y<x<N. (13)

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

Алгоритм С {Разложение на простые множители при помощи операций сложения и вычитания). По данному нечетному числу N этот алгоритм определяет наибольший множитель числа iV, меньший или равный л/N.

С1. [Начальная установка.] Присвоить х <- 2[\/N\ -\- I, у <- 1, г <- [\/N\ - N. (Во время выполнения этого алгоритма величины х,у,г отвечают соответственно величинам 2х -t 1, 2у -t 1, х - у -~ N в уравнении (13). Должно соблюдаться условие г < x и у < х.)

С2. [Выполнено?] Если г = О, то выполнение алгоритма завершается. Имеем

N={{x-y)/2){{x + y-2)/2),

а {х - у)/2 - наибольший множитель для iV, меньший или равный VN. СЗ. [Шаг по X.] Присвоить r<-r-txHx<-x-t2. С4. [Шаг по у.] Присвоить г<-г-уиу*-у--2.

С5. [Проверить г.] Если г > О, то возвратиться к шагу С4, иначе возвратиться к шагу С2. I

Возможно, читатель сочтет небезынтересным поиск вручную простых множителей числа 377 при помощи этого алгоритма. Число шагов, необходимых для нахождения множителей и и v числа TV = uv, по существу, пропорционально

(х + у-2)/2 - [VTVJ =и - [VTVJ;

это, конечно, может оказаться очень большой величиной, хотя каждый шаг на большинстве компьютеров может выполняться очень быстро. Р. Ш. Леман

(R. S. Lehman) [Math. Сотр. 28 (1974), 637-646] усовершенствовал алгоритм таким образом, что в худшем случае для его выполнения требуется только 0{N/) операций.

Называть алгоритм С методом Ферма не совсем правильно, поскольку Ферма использовал несколько более обтекаемый подход. В компьютерах основной цикл алгоритма С выполняется довольно быстро, но для вычислений вручную он мало пригоден. На самом деле Ферма не сохранял текущиеначения у; он рассматривал величину - N и, исходя из наименее значимых разрядов, делал вывод о том, является ли эта величина полным квадратом. (Последние два разряда полного квадрата должны быть 00, el, е4, 25, об или е9, где е - четная, а о - нечетная цифра.) По этой причине он избегал операций, которые выполнялись на шагах С4 и С5, заменяя их при помощи специальных приемов операцией определения числа, не являющегося полным квадратом.

Предложенный Ферма способ просмотра правых крайних разрядов можно, конечно, обобщить, используя другие модули. Предположим для ясности, что Л = 8 616 460 799 (историческое значение этого числа описывается ниже), и рассмотрим следующую таблицу.

Если величина х - N есть полный квадрат у, то она должна иметь остаток по модулю т, соответствующий этому факту. Например, если N = 8616460 799 и X mod 3 7 О, то (ж - N) mod 3 = 2, т. е. величина х - N не может быть полным квадратом. Поэтому х должно быть кратным 3 для всех значений N = х" - у. Из таблицы видно, что

X mod 3=0;

X mod 5 = О, 2 или 3;

X mod 7 = 2, 3, 4 или 5; (14)

X mod 8=0 либо 4 (отсюда х mod 4 = 0); X mod И = 1, 2, 4, 7, 9 или 10.

Это значительно сокращает процесс поиска х. Пусть, например, х должно быть кратно 12. Тогда должно быть х > \VN] = 92 825 и наименьшим числом, кратным 12, является число 92 832. Это значение дает в остатке (2,5,3) по модулю (5,7,11) соответственно, поэтому оно не удовлетворяет уравнению (14) по отношению к модулю И. Увеличив а; на 12, можно заменить остаток по модулю 5 на 2, по модулю 7 на 5 и по модулю 11 на 1. Поэтому легко увидеть, что первое значение величины X > 92 825, удовлетворяющее всем условиям в уравнении (14), есть х = 92 880. Теперь 92880 - N = 10 233601, и, вычислив вручную квадратный корень, получаем, что 10 233 601 = 3199 действительно является полным квадратом. Таким образом получено искомое решение х = 92880, у = 3199, а разложение на простые