Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2), страница 13

Эксперименты Вуидерлиха показали, что если значения Х близки к 104е при т ж 150, то алгоритм работает хорошо только с учетом этого уточнения, Так как на выполнение шага ЕЗ приходится ббльшая часть времени выполнения алгоритма, Моррисон, Бриллхарт и Шруппель предложили несколько способов прекращения выполнения этого шага, если результат становится правдоподобным: (а) когда значение Т изменяется таким образом, что его можно представить с однократной точностью, выполнение этого шага продолжается только в том случае, когда (Т/Р,) > Р! и Зт ' шоб Т ~ 1; (Ь) если Т оказываетсЯ все еще > Рзь после того, как выделены все множители <,~,р; (с) вьщелены только все множители, ббльшие р;,, для групп, скажем, нз 100 или около того последовательных значений $"; процесс разложения на простые множители может быть продолжен позже, ио только для значений 1' из каждой группы, для которой получен наименьший оста- ток Т.

(Прежде чем выделять множители, ббльшие рэ, полезно вычислить г' шоб Р, Рэ~Рэ~Р, Рэ~, где все У достаточно малы длЯ того, чтобы модУли Р18Рэ'Р,'Р4'Р,' можно было представлять с однократной точностью, но достаточно велики, чтобы выполнялись равенства $' щи рл~~ ы О. Поэтому один остаток с однократной точностью будет характеризовать значение 1" по модулю пяти малых простых чисел.) Па поводу оценки длины цикла выходных данных алгоритма Е обратитесь к работе Н. С. Ъ7101ашэ, Маей. Сотр. 36 (1981), 593-601.

эТеоретнчесизя верхняя граница. С точки зрения вычислительной сложности алгоритма желательно знать, существует ли метод разложения иа простые множители, ожидаемое время выполнения которого может быть ограничено оценкой 0(№(ло), где е(У) -+ 0 при Ф -ь оо. Выше было показано, что поведение алгоритма Е, вероятно, удовлетворяет такой оценке, однако желательно было бы найти строгое доказательство этого факта, так как цепные дроби не достаточно хорошо упорядочены. Первое доказательство того, что существует такой алгоритм разложения на простые множители, нашел в 1978 году Джон Диксон (лойп Рйхоп). Ои показал, что в действительности достаточно рассматривать упрощенный вариант алгоритма Е, из которого убирается аппарат цепных дробей, но основная идея соотношений (18) остается.

Метод Диксона [Май. Сошр. 36 (1981), 255-260] состоит в следующем. Предположим, что для числа У существует по меньшей мере два различных простых множителя и это число Х не делится на первые гп простых чисел ры рт, ..., р . Выберем случайное целое число Х из интервала О ( Х ( д' и положим Ъ' = Х шойй'. Если Ъ' = О, то число 8сб(Х,Х) является надлежащим множителем числа йГ. В противном случае, как и на шаге ЕЗ, выделяем все малые простые множители числа 1'. Другими словами, выражаем число Р в виде а» е Т (24) где Т не делится ни иа одно из первых гп простых чисел.

Если Т = 1, то выполнение алгоритма продолжается, как на шаге Е4„и выводятся данные (Х, ем..., е,„), которые представляют собой решение уравнения (19) при ее = О. Этот процесс продолжается с новыми случайными значениями величины Х до тех пор, пока пе наберется достаточно много выходных данных для того, чтобы по методу упр. 12 обнаружить множитель для числа ч'. При исследовании этого алгоритма нужно найти границы для (а) вероятности того, что случайное значение Х приводит к выводу результата, и (Ь) вероятности того, что для нахождения множителя потребуется большое количество выходных данных.

Пусть Р(тп, К) — вероятность (а), т. е. вероятность того, что Т = 1, если величина Х выбирается случайной. После опробования М значений величины Х получим в среднем МР(т,57) выходных значений, и число выходных значений имеет бииомиальное распределение, для которого среднеквадратичное отклонение меньше, чем квадратный корень из среднего значения. Вероятность (Ь) легко найти, воспользовавшись результатом упр.

13: при нахождении одного множителя алгоритму потребуется более гп + й выходных значений с вероятностью ( 2 э. В упр, 30 доказывается, что Р(т,Ж) > т'/(г!К) в случае, когда г = 2(!обХ/(2 1обр„,)(, поэтому время выполнения алгоритма можно оценить почти так же, как в (22), но при этом величина 2~/Х должна быть заменена величиной Х. На этот раз выбираем ть,чььГ~ гО, где (е! < 1 и г — четное число. Теперь значение т выбираем так, чтобы г = 1п й!/1пр ~- О(1/!об !об Аг); это означает, что 1пр = — -!п1пХ+0(1), 1пй/!п)ПЮ д 2 2 1пги = 1пя(р,„) =1пр,„— 1п!пр„, +О(1/1обр,„) !пй!1п1пХ д+! 2 — — 1п 1п Л' + О (! о8 !об !об г7), 2 гп" — *Р~- тгэ! ) л-О( ~~~~~лэ.

Выберем М таким, что Мгп'/(г!М) > 4ш. Следовательно, ожидаемое количество выходных значений МР(т, Ю) будет не меньше 4т. Время выполнения алгорит- ма — порядка Мт!обЮ плюс 0(тэ) шагов, что следует из результатов упр. 12; отсюда получаем, что 0(гпз) оказывается меньше Мгп 1обХ, что равно ~~)~~ ~ ~) ~ О~Омьу"'9~|~ж) '~(и~~к))!. Вероятность того, что с помощью данного метода не удастся получить множитель, ничтожно мала, так как вероятность того, что вычислено меньше, чем 2т выходных значений (упр.

31), не превышает е "'~э, в то время как вероятность того, что из числа первых 2т выходных значений не будет найдено ни одного множителя, не превышает 2 "' и гп » !пХ Доказана следующая несколько усиленная теоре- ма Диксона. Теорема Р. С ществует алгоритм, время выполнения которого равно 0(№бт~ ), где е(Л) = с 1п !пав/!пав в с — произвольная константа,. ббльтая, чем ~/8, и который находит нетривиальный множитель числа Х с вероятностью 1 — 0(1/Х) в случае, когда чтя числа Х существует по меиьпшй мере два простых делителя.

$ Другие подходы. Джон М.. Поллард (Зопп М. Ро!!агб) предложил другой способ разложения иа простые множители !Ртов СашбгЫбе РЫ. оос. 76 (1974), 521-528), в котором лается практический способ нахождения простых множителей р числа А! для случая, когда число р-1 не имеет больших простых множителей, Этот алгоритм (см. упр. 19) был, вероятно, первой попыткой решения поставленной задачи после того, как выяснилось, что алгоритмы А и В для больших чисел Х выполняются слишком долго. В обзорной работе, написанной Р. К. Ги (Н. К.

Спу) в соавторстве с Дж. Х. Конвеем (3. Н. Сопжау) и опубликованной в Сопйтеээиэ Хпшегап!!пш 16 (1976)„49-89, проведен анализ состояния проблемы на то время и перспектив разработки новых методов ее решения. Ги утверждал: "Я буку удивлен, если кто-либо в этом веке разложит на простые множители числа длиной 1Оэе, не оговаривая специальных случаев"; ему действительно пришлось много раз удивляться в течение следующих 20-ти лет. Значительные успехи в разработке способов разложения на простые множители были достигнуты в 80-е годы, начиная с мсшода квадратавчного прессования Карла Померанса (СаН Рошегапсе), разработанного им в 1981 году (см.

Ъесгиге Вогез !п Ссэпр. Яс1 209 (1985), 169-182). Затем Хендрик Ленстра (НеЫг!Ь (епегга) разработал мешод эллипшичссхих кривых !Аппа)э ог МагЬ. 126 (1987), 649-673). Он эвристически предположил, что для нахождения простого множителя р необходимо выполнить около ехр( (2+ в)(1пр)(!п1пр) ) операций умножения. Эта величина— не что иное, как аснмптотический квадратный корень из оценки времени выполнения алгоритма Е, когда р ж ~~У, и она становится даже лучше, если число Аг имеет относительно малые простые множители. Прекрасное описание этого метода дано Джозефом Х, Силверманом (ЛоэерЬ Н. Вйтегшап) и Джоном Тейтом (ЛоЬп Таге) в Наг!опа! Ро!пгв оп ЕВ!рбс Сигтев (Хетг 'г'огй: Ярг!пйег, 1992), СЬаргег 4.

В 1988 году к решению этой задачи вернулся Джон Поллард. Оп предложил новый подход, который стал позже известен как решегло числового полл. С рядом работ, посвященных этому методу., который является в настоящее время чемпионом по разложению на простые множители чрезвычайно больших чисел, можно ознакомиться в Бес!иге Хогеэ ш Магй. 1554 (1993). При использовании этого метода прогнозируемый порядок времени выполнения равен ехр((64/9+ в)'~з(!и!1Г)'~з()п!пА)э~в) (25) при Х -+ ао. Согласно анализу, выполненному А. К. Ленстрой (А. К. Ьепэгга), порогом, после которого хорошо иаг троенный метод решета числового поля начинает превосходить хорошо настроенный метод квадратичного просеивания., являстся висло А' 10г1з Подробности этих методов выходят за рамки данной книги. но представление об их эффективности можно получить, обратив внимание иа некоторые уже известные случаи неудачных попыток разложения на простые множители чисел Ферма вида 2э + 1.

Например, разложение 2"з + 1 = 2424833. 7455602825647884208337395736200454918783366342657 рэв было получено при помощи метода решета числового поля после вычислений в течение четырех месяцев, что заняло все свободное время почти 700 рабочих станций (1 епэгга, Мапавве, Ро!!агд, МаВь Согпр. 61 (1993), 319-349; 64 (1995), 1357); здесь рвв обозначает 99-разрядное простое число.