автору в 1975 году Р. Шруппелем (R. Schroeppel). Положим для определенности, что А; = 1. Число выходных данных, необходимых для получения разложения числа Л на простые множители, пропорционально т - числу выделенных в процессе вычислений малых простых чисел. Каждый раз на выполнение шага ЕЗ затрачивается порядка mlogiV единиц времени, так что обшее время выполнения в первом приближении пропорционально величине mlogN/P, где Р - вероятность получения очередного результата на каждой итерации. Предположим, что в течение всего времени выполнения алгоритма величина V равномерно распределена в интервале от О до 2у/М. Тогда вероятность Р равна значению {2у/М)~, умноженному на количество целых чисел < 2\/~N, для которых все простые множители принадлежат множеству {pi,...,Pfn}- В упр. 29 приведена нижняя граница для Р, из которой можно заключить, что наибольшее время выполнения алгоритма имеет порядок

2y/Nm logN

где г =

log2\/iV

(22)

mVr! [ log„

Если положить Inm равным приблизительно \/lniVln IniV, то предположив, что Рт = 0(т log т), получим г и In N/ In In N - 1, вследствие чего формула (22) упрошается и принимает вид

exp(2V(lniV)(lnlniV) + 0((logiV)i/2(loglogiV)-i/2(logloglogiV))).

Следовательно, при надлежащих предположениях ожидаемое время выполнения алгоритма Е не должно превышать величины N\ где e{N) ss 21пInN/lnN стремится к О при N оо.

Когда число N находится в интервале, чаще всего используемом на практике, нужно быть осторожным и не принимать всерьез такую асимптотическую оценку. Например, если N = 10°, получим iV/" = (IgA)" при а и 4.75, но то же самое соотношение справедливо и для а ss 8.42, когда N = 10°°. Функция iV- имеет порядок роста, который представляет собой некоторого рода пересечение N/" и (IgiV)", но все три равенства практически одинаковы для чисел Л, не являющихся недопустимо большими. Многочисленные вычислительные эксперименты, выполненные М. Ч. Вундерлихом (М. С. Wunderlich), показали, что хорошо настроенный вариант алгоритма Е значительно лучше выполняет разложение, чем предусматривается этой оценкой [см. Lecture Notes in Math. 751 (1979), 328-342]; несмотря на то что для N = 10° имеет место 21п \nN/lnN ss .41, при разложении на простые множители тысяч чисел в интервале 10 < N < 10"* он получил выражение для времени выполнения, равное приблизительно iV°.

Попытка выполнить разложение числа N с помощью алгоритма Е начинается, по существу, с замены N на kN, что выглядит довольно любопытно (если не откровенно глупо). "Простите, как вы смотрите на то, что перед попыткой разложения числа я умножу его на 3?" Тем не менее идея выглядит привлекательной, поскольку некоторые значения к делают числа V потенциально делимыми на меньшие простые числа, и поэтому на шаге ЕЗ полное разложение этих чисел на простые множители может быть выполнено проще. С другой стороны, большое значение чиста к сделает числа V больше, и тогда их полное разложение на простые множители будет затруднено. Нужно сбалансировать эти тенденции путем соответствующего подбора числа к. Рассмотрим, например, делимость чисел V на числа, равные степеням 5.

На шаге ЕЗ получаем - kNQ - (-l)F, так что, если 5 делит v, имеем = kNQ" (по модулю 5). В данном соответствии число Q не может быть кратным 5, поэтому оно взаимно просто с Р и можно записать (P/Q) = kN (по модулю 5). Если предположить, что Р и Q - случайные взаимно простые числа, такие, что 24 возможные пары чисел (Р mod 5, С? mod 5) ф (0,0) равновероятны, вероятность того, что 5 делит V, равна, таким образом, , , О, О или в зависимости от того, какие значения принимает число kN mod 5: О, 1, 2, 3 или 4. Аналогично вероятность того, что 25 делит V, равна О, О, О, соответственно, если только kN не кратно 25. В общем случае для данного нечетного простого числа р, для которого {kN)~/ modp = 1, получаем, что V кратно р с вероятностью 2/{р~{р+ 1)); среднее число р делителей числа V приближается к 2р/(р2 - 1). Из этого анализа, выполненного Р. Шруппелем (R. Schroeppel), следует, что лучший выбор числа к - это значение, которое обеспечивает максимум функции

53/(p,-,fciV)logp,--logfc, (23)

где / определена в упр. 28, поскольку, по существу, это ожидаемое значение величины ln(\/iV/r) при переходе к шагу Е4.

Если числа кит хорошо подобраны, выполнение разложения по алгоритму Е дает еще лучшие результаты. Выбор подходящего числа m может быть выполнен экспериментально, так как проведенный выше анализ асимптотического поведения носит незавершенный характер и нельзя быть уверенным в точности полученной информации. Поэтому внесение в алгоритм многочисленных уточнений, связанных с таким выбором т, может привести к непредсказуемым последствиям. Например, сравнив выполнение шага ЕЗ с выполнением алгоритма А, можно получить следующее важное усовершенствование. Суть его в том, что процесс разложения на простые множители можно остановить после нахождения Т mod pj ф О и \TIpj\ < Pj, поскольку в этом случае Г будет либо равно 1, либо простым числом. Если Т - простое число, большее рт (в таком случае оно будет не больше Рт +Рт - 1), ТО, учитывая, ЧТО получено полное разложение на простые множители, можно вывести в качестве результата (Р, ео,..., е, Г). На второй фазе алгоритма будут использованы только те выходные данные, для которых все простые числа Т встретятся не менее двух раз. Эта модификация приводит к образованию намного большего списка простых чисел без дополнительных затрат времени. Эксперименты Вундерлиха показали, что если значения N близки к 10*° при m и 150, то алгоритм работает хорошо только с учетом этого уточнения.

Так как на выполнение шага ЕЗ приходится большая часть времени выполнения алгоритма, Моррисон, Бриллхарт и Шруппель предложили несколько способов прекращения выполнения этого шага, если результат становится правдоподобным: (а) когда значение Т изменяется таким образом, что его можно представить с однократной точностью, выполнение этого шага продолжается только в том случае, когда [T/pj\ > Pj и 3~1 mod Т ф 1; (Ь) если Т оказывается все еще > р после того, как выделены все множители < jPm, (с) выделены только все множители, большие р5, для групп, скажем, из 100 или около того последовательных значений V; процесс разложения на простые множители может быть продолжен позже, но только для значений V из каждой группы, для которой получен наименьший оста-

ток т. (Прежде чем выделять множители, большие ps, полезно вычислить У mod р(Р2Рзр(*р1 , где все / достаточно малы для того, чтобы модули р(Р2Рзр(р1 можно было представлять с однократной точностью, но достаточно велики, чтобы вьшолнялись равенства V modp/" = 0. Поэтому один остаток с однократной точностью будет характеризовать значение V по модулю пяти малых простых чисел.)

По поводу оценки длины цикла выходных данных алгоритма Е обратитесь к работе Н. С. Williams, Math. Сотр. 36 (1981), 593-601.

*Теоретическая верхняя граница. С точки зрения вычислительной сложности алгоритма желательно знать, сушествует ли метод разложения на простые множители, ожидаемое время выполнения которого может быть ограничено оценкой 0(7V()), где e{N) О при iV оо.

Выше было показано, что поведение алгоритма Е, вероятно, удовлетворяет такой оценке, однако желательно было бы найти строгое доказательство этого факта,. так как цепные дроби не достаточно хорошо упорядочены. Первое доказательство того, что существует такой алгоритм разложения на простые множители, нашел в 1978 году Джон Диксон (John Dixon). Он показал, что в действительности достаточно рассматривать упрощенный вариант алгоритма Е, из которого убирается аппарат цепных дробей, но основная идея соотношений (18) остается.

Метод Диксона [Math. Сотр. 36 (1981), 255-260] состоит в следующем. Предположим, что для числа N существует по меньшей мере два различных простых множителя и это число N не делится на первые m простых чисел pi, р2, Рт- Выберем случайное целое число X из интервала О < X < iV и положим У = mod N. Если У = О, то число gcd(X, iV) является надлежащим множителем числа N. В противном случае, как и на шаге ЕЗ, выделяем все малые простые множители числа У. Другими словами, выражаем число У в виде

У=рГ...Р"Т, (24)

где Т не делится ни на одно из первых m простых чисел. Если Г = 1, то выполнение алгоритма продолжается, как на шаге Е4, и выводятся данные (X,ei,... ,6), которые представляют собой решение уравнения (19) при ео = 0. Этот процесс продолжается с новыми случайными значениями величины X до тех пор, пока не наберется достаточно много выходных данных для того, чтобы по методу упр. 12 обнаружить множитель для числа N.

При исследовании этого алгоритма нужно найти границы для (а) вероятности того, что случайное значение X приводит к выводу результата, и (Ь) вероятности того, что для нахождения множителя потребуется большое количество выходных данных. Пусть P{m,N) - вероятность (а), т. е. вероятность того, что Т = 1, если величина X выбирается случайной. После опробования М значений величины X получим в среднем MP{m,N) выходных значений, и число выходных значений имеет биномиальное распределение, для которого среднеквадратичное отклонение меньше, чем квадратный корень из среднего значения. Вероятность (Ь) легко найти, воспользовавшись результатом упр. 13: при нахождении одного множителя алгоритму потребуется более т + к выходных значений с вероятностью < 2~*.

В упр. 30 доказывается, что

P{m,N) > m7(r!iV)