и наибольший простой множитель не превышает (а;")*/"*, т. е. а;"* F(i/(1 -t)). Следовательно, xF{t)dt - {хdt/t)[xF[t/{l - t))) и уравнение (6) получается посредством интегрирования последнего уравнения. Этому эвристическому доводу может быть придана строгость. В. Рамасвами (V. Ramaswami) [Bull. Amer. Mati. Soc. 55 (1949), 1122-1127] показал, что в случае фиксированных а при х со интересующая нас вероятность асимптотически равна F{a) + 0(l/loga;); анализом этой проблемы занимались и многие другие авторы [см. обзор Карла К. Нортона (Karl К. Norton), Memoirs Amer. Math. Soc. 106 (1971), 9-27]. В случае, если < а < 1, формула (6) упрощается:

Таким образом, например, вероятность того, что для случайного целого числа < х существует простой множитель > л/х, равна 1 - F() = 1п2, что составляет около 69%. Во всех этих случаях выполнение алгоритма А сопряжено с определенными трудностями.

Обсудим теперь вопрос о том, насколько быстро алгоритм А выдаст результат в случае, когда множитель ограничен шестиразрядным числом. Заметим, что для больших чисел N, если нам не повезет, общее время выполнения процедуры разложения на множители с использованием пробных делителей очень быстро превысит практические возможности гшгоритма.

Ниже в этом разделе будет показано, что существуют достаточно хорошие способы, позволяющие определить, является ли относительно большое п простым числом, не проверяя все пробные делители до л/п. Поэтому алгоритм А будет выполняться быстрее, если между шагами А2 и A3 включить проверку принадлежности числа к простым числам. Для алгоритма, усовершенствованного таким образом, время выполнения можно в первом приближении считать пропорциональным pt-i, т. е. второму по величине простому множителю числа iVвместо max(pt i, %/pt )• Используя аргументы, аналогичные аргументам Дикмана (см. упр. 18), можно показать, что с приближенной вероятностью G(/3) второй по величине простой множитель случайного целого числа < х будет < х, где

Очевидно, что для /? > эта функция G(/?) = 1 (см. рис. 12). Численное решение уравнений (6) и (7) дает следующие "процентные отношения значений" этих функций.

F(q),G(/3)= .01 .05 .10 .20 .35 .50 .65 .80 .90 .95 .99 q= .2697 .3348 .3785 .4430 .5220 .6065 .7047 .8187 .9048 .9512 .9900 /3= .0056 .0273 .0531 .1003 .1611 .2117 .2582 .3104 .3590 .3967 .4517

Таким образом, примерно в половине случаев второй по величине простой множитель будет < х и т. д.

Можно проанализировать также величину t - общего числа простых множителей. Обычно 1 < < Ig iV, но эти нижние и верхние границы достигаются редко. Можно доказать, что если N выбирается как случайное число в интервале между 1

Второй по величине 0.6

X" x х- х- X х° х° X х-" Х-" X Рис. 12. Функция распределения вероятностей для двух наибольших простых множителей случайного целого числа < х.

и X, то вероятность того, что * < In In г 4- с In In а; при х -> оо, стремится к

для любых фиксированных с. Другими словами, распределение величины t является, по существу, нормальным со средним значением и дисперсией, равными In In а:; примерно для 99.73% всех больших чисел < х вьшолняется \t - Inlna;] < Ъ\/ In In х. Далее, известно, что среднее значение для t - Inlna; при 1 < iV < а; достигает величины

7+ (1п(1-1/р) + 1/(р-1))=7+е

(,£>(п) In С(П)

р простое п>2

= 1.03465 38818 97437 9116197942 98464 63825 46703-f-.

[См. G. Н. Hardy, Е. М. Wright, An Introduction to the Theory of Numbers, 5th edition (Oxford, 1979), §22.11; см. также P. Erd6s, M. Kac, Amer. J. Math. 26 (1940), 738-742.]

Размер простых множителей имеет примечательную связь с перестановками. Среднее число битов в к-м наибольшем простом множителе случайного п-битового числа -при п ->• 00 асимптотически стремится к средней длине к-го наибольшего цикла перестановок случайного п-элемента. [См. D. Е. Knuth and L. Trabb Pardo, Theoretica; Сотр. Sci. 3 (1976), 321-348; A. M. Вершик, Soviet Math. Doklady 34 (1987), 57-61.] Отсюда следует, что алгоритм А сначала находит несколько малых множителей, а затем начинает долгий поиск остальных ббльших множителей.

Прекрасное описание распределения вероятностей простых множителей для случайных целых чисел приведено в статье Патрика Биллингслея (Patrick BilUngsley), опубликованной в журнапе АММ 80 (1973), 1099-1115 (см. также его статью в Annals of Probability 2 (1974), 749-791).

Разложение на простые множители с использованием псевдослучайных циклов. В начале главы 3 указывалось, что выбранный генератор случайных чисел дает числа, которые оказываются не совсем случайными. Этот тезис, работавший в той главе против нас, здесь оборачивается благом и ведет к поразительно эффективному методу разложения на простые множители, открытому Дж. М. Поллардом (J. М. Pollard) [BIT 15 (1975), 331-334].

Число шагов вычислений в методе Полларда имеет порядок y/pt-i, поэтому при больших N он значительно быстрее алгоритма А. Как следует из уравнения (7) и рис. 12, время выполнения алгоритма, реализующего метод Полларда, обычно меньше, чем N/.

Пусть /(х)-полином с целочисленными коэффициентами. Рассмотрим две последовательности

хо=Уо = Л; Хт+1 = f{xm) mod N, Ут+i =/(Ут) modp, (10)

где р-любой простой множитель числа TV. Тогда

ym=Xmmodp при m > 1. (И)

Из упр. 3.1-7 видно, что для некоторого т>1 вьшолняется равенство Ут = Уе{т}-1> где £{т) - наибольшая степень 2, не превышающая т. Таким образом, разность Хщ - хцт)-1 будет кратна р. Далее, если /(у) modp ведет себя как случайное отображение множества {О, 1, ... ,р-1} на самое себя, то, как показано в упр. 3.1-12, среднее значение наименьших из таких т будет порядка у/р. Фактически это среднее значение для случайных выборок меньше 1.625 Q(p), как показано в упр. 4 ниже; функция Q{p) » ул-р/2 была определена в разделе 1.2.11.3.

Если различные простые делители числа N соответствуют различным значениям т (что для больших TV почти всегда верно), их можно найти, вычисляя gcd(xm - хе(т)-1, TV) для m = 1, 2, 3, ... до тех пор, пока остаток от деления на множитель не станет простым. Поллард назвал этот метод ро-методом, так как периодическая последовательность вида уо, ух, ... напоминает греческую букву р.

Из главы 3 известно, что линейный полином f{x) = ах+с не обеспечивает достаточной случайности последовательности. Следующим простейшим видом полинома является квадратичный полином }{х) = х + 1. Нам неизвестно, обеспечивает ли данная функция случайность, но недостаток знаний по этому вопросу склоняет нас, скорее всего, в пользу гипотезы о том, что функция обеспечивает достаточную случайность, а эмпирическая проверка показала, что она ведет себя так, как и предполагалось. В действительности же функция /, вероятно, даже дает немного больше, чем случайность, так как х + 1 содержит только (р Ч- 1) различных значений по модулю р (см. Агпеу, Bender, Pacific J. Math. 103 (1982), 269-294). В связи со сказанным уместна следующая процедура.

Алгоритм В {Разложение на простые множители при помощи ро-метода). Этот алгоритм с высокой вероятностью вычисляет простые множители данного целого числа TV > 2, хотя не исключен и отрицательный результат (т. е. множитель найден не будет. - Прим. перев.).

81. [Начальная установка.] Присвоить х <- 5, х <- 2, к <- 1, I 1, п <- N. (Во время выполнения этого алгоритма число п не является множителем числа TV, а переменные х и х представляют величины Хт mod п и хцт)-1 mod п в выражении (10), где также f{x) = х + 1, А = 2, I = £{т) и к = 21 - т.)

82. [Проверить, будет ли число простым.] Если п - простое число (рассматривается ниже), вывести п в качестве результата; на этом выполнение алгоритма завершается.