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

Влшаеишп1) (Вой. Ашег. Май. 5ос. 66 (1949), 1122-1127) показал, что в случае фиксированных а при х -э м интересующая нас вероятность асимптотнчески равна Г(а) + 0(1/!охх); анализом этой проблемы занимались и многие другие авторы [см. обзор Карла К, Нортона (Кег1 К. Хог1оп), Метонв Атег. Май. Яос. 106 (1971), 9-27]. В случае, если -' < а < 1, формула (6) упрощается: т <й Г' й Е(а) = 1 — / Е~ — ) — = 1 — / — = 1+ (па.

ч Таким образом, например, вероятность того, что для случайного целого числа < х существует простой множитель > ~/х„равна 1 — РЯ) = 1и 2, что составляет око- ло 69%. Во всех этих случаях выполнение алгоритма А сопряжено с определеннымн трудностями, у теперь вопрос в случае, когда множитель ограничен шестиразрядным числом. Заметим, что для больших чисел Л, если нам не повезет, общее время выполнения процедуры разло- жения на множители с использованием пробных дезителей очень быстро превысит практические возможности алгоритма. Ниже в этом разделе будет показано, что существуют достаточно хорошие спосо- бы, позволяющие определить, является ли относительно большое и простым числом, не проверяя все пробные делители до ~/о. Поэтому алгоритм А будет выполняться быстрее, если между шагамн А2 и АЗ включить проверку принадлежности числа к простым числам, Для алгоритма, усовершенствованного таким образом, время вы- полнения можно в первом приближении считать пропорциональным р, ы т.

е. вше- ромр по величине простому множителю числа Х вместо шах(рс-ы ь/~ ). Используя аргументы, аналогичные аргументам Дикмана (см. упр. 18), можно показать, что с приближенной вероятностью С(6) второй по величине простой множитель случай- ного целого числа < х будет < х", где а(е / (а( ' ) р( ' )) ~ р„аргут е) Очевидно, что для ~У > -' эта функция С(б) = 1 (см, рис. 12). Численное реше- ние уравнений (6) и (7) дает следующие "процентные отношения значений" этих функций. Е(а),С(б) = .01 .05 .10 .20 .35 .50 .65 .80 ,90 .95 .99 а = .2697 .3348 .3785 .4430 .5220 .6065 .7047 .8187 .9048 .9512 .9900 ~У = .0056 .0273 .0531 .1003 .1611 .2117 .2582 .3104 .3590 .3967 .4517 Таким образом, примерно в половине случаев второй по величине простой множитель будет < х-"'" и т.

д. Можно проанализировать также величину г — общего числа простых мнохситпелей. Обычно 1 < г < )я%, но эти нижние и верхние границы достигаются редко. Можно доказать, что если Х выбирается как случайное число в интервале межлу 1 о.з Второй по ее о.е ол 0.2 о.о ' хо тз хт х 3 х л хс х е хт х е ж е хл Рис. 12.

Функция распределения вероятностей для двух наибольших простых множителей случайного целого числа < х. и х, то вероятность того, что г < !п Ьл х+ с Дв !их ири х -е со, стремится к — е "7пн (8) для любых фиксированных с. Другими словами, распределение величины г является, по существу, нормальным со средним значением и дисперсией, равными !и 1их; примерно для 99.73% всех больших чисел < х выполняется ]1 — !и !их] < ЗЯп!их. Далее, известно, что среднее значение для ! — 1п1их при 1 < )7 < х достигает величины 7+ ~Х~ (1и(1 — 1/р) + 1/(р — 1)) = 7+ ~Х' ~р(п) !и ь(гл) р простое о>2 = 1.03465 38818 97437 91161 97942 98464 63825 46703+.

(9) (См. С. Н. Нагду, Е. М. етг!8Ьг, Ап 1иггос(исг!ои го гЬе ТЬеогу о! ЖитЬегя, 51Ь ес!!г!ои (Ох!огс(, 1979), 222,11; см. также Р. Егббз, М, Кас, Ашег. Х. МаСЬ. 26 (1940), 738-742.] Размер простых множителей имеет примечательную связь с перестановками. Среднее число битов в )с-и наибольшем простом множителе случайного и-битового чнсла при и -т оо асимптотически стремится к средней длине )с-го наибольшею цикла перестановок случайного п-злемента, (См.

П. Е. КпцсЬ апб Ь. ТгаЬЪ Рахово, ТЬеогебса! Сошр. Яс7 3 (1976), 321-348; А. М, Вершик, Бог!е! МаГЬ. РоЫал(у 34 (1987), 57-61.] Отсюда следует, что алгоритм Л сначала находит несколько малых множителей, а затем начинает долгий поиск остальных ббльших множителей. Прекрасное описание распределения вероятностей простых множителей для случайных целых чисел приведено в статье Патрика Биллингглея (Рапйс1л В!!!!ийз!еу), опубликованной в журнале АММ 80 (1973), 1099-1115 (см.

также его статью в Аппа)з и! РгоЬаМ!1Гу 2 (1974), 749 — 791). Разложение на простые множители с использованием псевдослучайных циклов. В начале главы 3 указывалось, что выбранный генератор случайных чисел дает числа, которые оказываются не совсем случайными. Этот тезис, работавший в той главе против нас, здесь оборачивается благом и ведет к поразительно аффективному методу разложения на простые множители, открытому Дж. М.

Поллардом (3, М. Ро!!агл!) !В1Т 1$ (1975), 331-334]. Число шагов вычислений в методе Полларда имеет порядок ~/р~ м поэтому при больших К он значительно быстрее алгоритма А. Как следует нз уравнения (7) и рис. 12, время выполнения алгоритма, реализующего метод Полларда, обычно меньше, чем АГ'~4. Пусть 7(х) — полинам с целочисленными коэффициентами.

Рассмотрим две последовательности хе = уе = А; х,„+1 = ~(х,„)шаба, 9„,+1 = Ду„,) шобр, (10) где р — любой простой множитель числа А'. Тогда р =х шеар при т>1. Из упр. 3.1-7 видно, что для некоторого т > 1 выполняется равенство 9„= рц,> и где Г(гп) — наибольшая степень 2„не превышающая ш. Таким образом, разность х,„- хц„,1 1 будет кратна р. Далее, если 7(9) шобр ведет себя квк случайное отображение множества (О, 1, ..., р- Ц на самое себя, то, как показано в упр.

3.1-12, среднее значение наименьших из таких гп будет порядка ь~р. Фактически это среднее значение для случайных выборок меньше 1.626 ф р), как показано в упр. 4 ниже; функция й(р) ж фтр/2 была определена в разделе 1,2.11.3. Если различные простые делители числа Х соответствуют различным значениям га (что для болыпнх М почти всегда верно), их можно найти, вычисляя йсб(хм — хц 1 ы Ю) для т = 1, 2, 3, ... до тех пор, пока остаток от деления на множитель не станет простым. Поллард назвал этот метод ро-методом, так как периодическая последовательность вида уе, ум ... напоминает греческую букву р. Из главы 3 известно, что линейный полинам 7 (х) = ах+с не обеспечивает достаточной случайности последовательности. Следующим простейшим видом полинома является квадратичный полинам 7(х) = хз + 1, Нам иеизаесзпно, обеспечивает ли данная функция случайность, но недостаток знаний по этому вопросу склоняет нас, скорее всего, в пользу гипотезы о том, что функция обеспечивает достаточную случайность, а эмпирическая проверка показала, что она ведет себя так, как и предполагалось.

В действительности же функция у, вероятно, даже дает немного болыце„чем случайность, так как хз + 1 содержит только 1(р+ 1) различных значений по модулю р (см. Агпеу, Вепдег, Рас(бс Х Маей. 103 (1982), 269-294), В связи со сказанным уместна следующая процедура. Алгоритм В (Разложение иа просшме множвшело при помощоро-мегпода). Этот алгоритм с высокой вероятностью вычисляет простые множители данного целого числа К > 2, хотя не исключен и отрицательный результат (т. е, множитель найден не будет, — Прям. перев.).

В1. [Начальная установка.] Присвоить х +- 6, х' +- 2, к < — 1, 1 +- 1, и < — М, (Во время выполнения этого алгоритма число и не является множителем чнс- лад', а переменные х и х' представляют величины х шобп и хц„,~ 1 гаодп в выражении (10), где также 7(х) = хз + 1, А = 2, 1 = 6(т) и й = 21 — т.) В2. [Проверить, будет ли число простым.) Если и — простое число (рассматривается ниже), вывести и в качестве результата; на этом выполнение алгоритма завершается. ВЗ. [Множитель найден?) Присвоить д 4 — Зсмк(х' — х, и). Если д = 1, то перейти к шагу В4; в противном случае вывести д.

Теперь, если д = и, алгоритм завершается (его выполнение прерывается, ибо нам известно, что и не является простым числом). В противном случае присвоить и +- и/д, х <- х шоб п, х' < — х' щи и и возвратиться к шагу В2. (Заметим, что д может и не быть простым числом— это подлежит проверке. В каждом случае, когда д — не простое число, его простые множители не могут быть определены при помощи этого алгоритма,) В4. [Продвинуться.[ Присвоить х с — )с — 1. Если А = О, то присвоить х' +- х, 1+- 2(, и е- А Присвоить х +- (хз + 1) шоб и и возвратиться к шагу ВЗ. 1 В качестве примера алгоритма В попробуем снова разложить на простые множители число Х = 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 Экспериментальным путем установлено, что среднее значенке гп(р) примерно равно 2~ур и никогда не превышает 12тур, когда р < 1 000 000. При р с 104 максимум т(р) равен т(874 771) = 7685, Максимум функции гп(р)/~/р достигается при р = 290 047 и т(р) = 6251. На основании этих результатов почти все 12-разрядные числа можно разложить на простые множители быстрее чем за 2 000 итераций алгоритма В (сравните с 75 000 операций деления„требуемых для выполнения алгоритма А). Время на каждой итерации алгоритма В, в основном, затрачивается на выполнение умножения и деления с многократной точностью на шаге В4 и на вычисление наибольшего общего делителя на шаге ВЗ.

Выполнение этих операций может быть ускорено за счет применения методики "умножения Монтгомери' (см. упр. 4.3.1-41) . Более того, в случае, когда операция нахождения наибольшего общего делителя выполняется медленно, Поллард предложил ускорить процесс путем накапливания произведения по модулю и, скажем, десяти последовательных значений (х' — х) перед тем, как искать наибольший общий делитель. Таким образом, 90% операций нахождения наибалыпего общего делителя заменяется одним умножением по модулю Ж ценой некоторого увеличения вероятности того, что решение при этом не будет найдено, Поллард также предложил начинать вычисления на пшге В1 с т = д, а не с ш = 1, где 0 равно одной десятой от количества итераций, которые планируется реализовать, В тех редких случаях, когда для болыпих Аг результат не был найден, можно применить функцию )'(х) = х~ + с при некотором с 74 0 или 1.