Math. 117 (1983), 173-206.] X. В. Ленстра (мл.) (Н. W. Lenstra, Jr.) усовершенствовал этот метод, благодаря чему он стал выполняться еще быстрее, что подтвердила практика применения метода Г. Кохеном (Н. Cohen) и А. К. Ленстрой (А. К. Lenstra) [Math. Сотр. 42 (1984), 297-330; 48 (1987), 103-121].

Позже Эдлеман и Минг-Дех А. Хуанг (Ming-Deh А. Huang) предложили способ строгого доказательства принадлежности числа к простому для всех простых п. С высокой вероятностью время выполнения этого алгоритма пропорционально log п [Lecture Notes in Math. 1512 (1992)]. Однако их метод, кажется, представляет только чисто теоретический интерес.

Разложение на простые множители при помохци цепных дробей. Камнем преткновения для методов разложения на простые множители, рассмотренных выше, является разложение чисел, содержащих 30 и более разрядов, поэтому для их разложения нужна другая идея, которая позволила бы идти дальше в этом направлении. К счастью, такая идея существует; точнее, есть две такие идеи, предложенные А. М. Лежандром (А. М. Legendre) и М. Крайчиком (М. Kraitchik). Основываясь на них, Д. Г. Лемер и Р. Е. Пауэре (R. Е. Powers) много лет назад разработали новый подход к решению этой задачи [Bull. Amer. Math. Soc. 37 (1931), 770-776]. Однако некоторое время данный метод не применялся из-за трудностей, связанных с его реализацией на настольных арифмометрах. Негативное мнение об этом методе было преодолено к концу 60-х годов, когда Джон Бриллхарт (John Brillhart) обнаружил, что приближение Лемера-Пауэрса можно "воскресить" благодаря тому, что метод очень хорошо подходит для компьютерного программирования. Действительно, чуть позже он вместе с Майклом А. Моррисоном (Michael А. Morrison) разработал алгоритм, ставший в 70-е годы непревзойденным средством разложения на простые множители с использованием формата многократной точности. Их программа обрабатывала на компьютере IBM 360/91 произвольные 25-раарядные числа за 30 с, а 40-разрядные числа - за 50 мин [см. Math. Сотр. 29 (1975), 183-205]. Первый триумфальный успех был достигнут в 1970 году, когда был продемонстрирован результат: 2 + 1 = 59 649 589 127 497 217 • 5 704 689 200 685 129 054 721.

Основная идея заключается в том, чтобы найти числа х и у , такие, что

х = у (по модулю N), 0<х,у < N, х фу, х + у ф N. (18)

Метод Ферма накладывает более строгое условие х -у" = N, но в действительности соответствия (18) достаточно для того, чтобы разложить число Л на множители. Из (18) следует, что число Л есть делитель числа х -у = (х - у){х + у), но число N не делит пи х - у, пи х + у; следовательно, gcd(A, х - у) и gcd{N, х + у) являются делителями числа Л, которые могут быть найдены при помощи эффективных алгоритмов, рассмотренных в разделе 4.5.2.

Один из способов нахождения решения уравнения (18) - найти такие значения X, при которых х = а (по модулю N) для малых значений а. В дальнейшем будет показано, что зачастую, чтобы получить решения (18), достаточно просто объединить решения приведенного выше уравнения. Далее, если = a + kNd" для некоторых knd при малом значении а, дробь x/d является хорошим приближением к л/kN; и обратно, если x/d - очень хорошее приближение к л/kN, то jx - kNd\ будет мало. Сказанное наводит на мысль о необходимости рассмотреть разложение

в цепную дробь числа y/kN, поскольку, как видно из соотношения 4.5.3-(12) и упр. 4.5.3-42, цепные дроби дают хорошие рациональные приближения.

Для квадратичных иррациональностей цепные дроби обладают многими приятными свойствами, как было доказано в упр. 4.5.3-12. В приводимом ниже алгоритме эти свойства используются для получения решений уравнения

х = {-1ГрТр1 ... р" (по модулю N). (19)

Здесь используется фиксированное множество простых чисел pi = 2, р2 =3, ... вплоть до Рт- Из ЭТОГО множества выбираются только такие простые числа р, для которых либо р = 2, либо (A;iV)fP~/ modp < 1, поскольку другие простые числа никогда не будут множителями чисел, порождаемых этим алгоритмом (упр. 14). Если (a;i,eoi,eii,...,emi), (a;r,eor,eir, • ,e„r) -решения (19), такие, что в векторной сумме

(eoi,eii,.. .,e„i) -t- • • • + (eor, eir,..., e„r) = (2eo, 2ei,..., 2e„) (20)

каждый компонент четный, то

X = (xi... X,) mod iV, t/= ((-l)Si---Pm)modiV (21)

дает решение уравнения (18) за исключением случая, когда х = ±у. Условие (20) равнозначно утверждению, что рассматриваемые векторы линейно зависимы по модулю 2, поэтому, если найдено по меньшей мере т + 2 решений (19), должно сушествовать хотя бы одно решение, соответствуюшее (20).

Алгоритм Е {Разложение на простые множители при помоищ цепных дробей). По данным положительному целому числу N и положительному целому числу к, такому, что число kN не является точным квадратом; этот алгоритм предпринимает попытку найти решения уравнения (19) для данной последовательности простых чисел pi, ..., Рт, исследуя сходимость цепной дроби для y/kN. (Другой алгоритм, используюший для поиска множителей числа N выходные данные (алгоритма Е. - Прим. перев.), является предметом рассмотрения в упр. 12.)

Е1. [Начальная установка.] Присвоить D +- kN, R <- [\/DJ , R <-2R,U <-U +- R, V 1, V D - R, P <- R, P <- 1, A 0, S 0. (Следуя основной процедуре упр. 4.5.3-12, алгоритм находит разложение в цепную дробь числа у/Ш. Переменные U, U, V, V, Р, Р, Аи S представляют R + Un, R + Un-i, Vn, Vn-i, Pn mod N, Pn~imodN, An и nmod2 соответственно. Всегда будет выполняться неравенство О < V < U < R, поэтому самая высокая точность потребуется только для нахождения чисел Р и Р.)

Е2. [Продвинуть и, V, S.] Присвоить Т V, V <- A{U - U) + V, F 4- Г, А 4-[U/V\, U <-и,и R -{U mod V),S+-1-S.

ЕЗ. [Разложить на множители V.] (В соответствии с результатами упр. 4.5.3-12(с) здесь имеем Р - kNQ" = {-l)V.) Присвоить (eo,ei,... ,6) +- (5,0,... ,0), Т <-V. Теперь нужно выполнить следуюшее. Для 1 < j < т, если Т modpj = О, присвоить Т 4- T/pj и ej <- Cj + 1 и повторять этот процесс до тех пор, пока не получится Т mod pj ф 0.

Таблица 1

пример выполнения алгоритма е

Е4. [Решение?] Если Г = 1, вывести значения (Р, ео, ei,..., е), которые составляют решение уравнения (19). (Если получено достаточное число решений, то на этом шаге алгоритм может быть завершен.)

Е5. [Продвинуть Р, Р.] Если V ф 1, присвоить Т +- Р, Р +- (АР + P)modN, Р <- Т и возвратиться к шагу Е2. В противном случае процесс разложения в цепную дробь начинает повторять цикл сначала, за возможным исключением S, и поэтому выполнение алгоритма на этом завершается. (Обычно данный цикл настолько продолжителен, что завершение не происходит.)

В качестве примера применения алгоритма Е к сравнительно малым числам рассмотрим случай, когда N = 197209, А; = 1, m = 3, pi = 2, рг = 3, рз = 5. Начальная часть вычислений представлена в табл. 1.

Продолжение вычислений приводит к получению за первые 100 итераций 25 выходных данных; другими словами, алгоритм находит решения очень быстро, но некоторые из них тривиальны. Например, если продолжить вычисления еще на 14 шагов, можно получить 197197 = 2* • 3 • 5° выходных данных, которые не представляют интереса, поскольку 197197 = -12. Для завершения процесса разложения на простые множители достаточно первых двух решений, полученных выше. Так как получено

(159 316-133 218)2 = (2 -3 -5)2 (по модулю 197209),

соотношение (18) вьшолняется при х = (159 316- 133 218) mod 197209 = 126308, у - 540. В соответствии с алгоритмом Евклида gcd(126308 - 540, 197209) = 199, и получаем изящное разложение

197209= 199-991.

Чтобы понять причины, по которым алгоритм Е столь успешно выполняет разложение больших чисел на простые множители, рассмотрим эвристический анализ времени выполнения алгоритма Е, следуя неопубликованной идее, высказанной