AOP_Tom2 (1021737), страница 116
Текст из файла (страница 116)
Е(а), С(6) = .01 .05 .10 .20 .35 .50 .65 .80 .90 .95 .99 а = .2697 .3348 .3785 .4430 .5220 .6065 7047 .8187 .9048 .9512 .9900 6 = .0056 .0273 .0531 .1003 .1611 .2117 .2582 .3104 .3590 .3967 .4517 Таким образом, примерно в половине случаев второй по величине простой множитель будет < х тмт и т. д. Можно проанализировать также величину ! — общего числа простых множителей. Обычно 1 < ! < 18 М, но эти нижние и верхние границы достигаются редко. Можно доказать, что если А! выбирается как случайное число в интервале межлу 1 1.0 ол Второй во в 0.6 0.4 0.2 0.0 о .е е е е е .е .е .е .о Рис.
12. Функция распределения вероятностей для двух наибольших простых множителей случайного целого числа < х. и х, то вероятность того, что 1 < !и 1п х + ссlГп !их при х -4 оо, стремится к — е "/ии е/2т /- (8) для любых фиксированных с.
Другими словами, распределение величины г является, по существу, нормальным со средним значением и дисперсией, равными 1п1пх; примерно для 99.73% всех больших чисел < х выполняется ~1 — !и 1и х) < ЗДп!их. Далее, известно, что среднее значение для 1 — !п1пх при 1 < Х < х достигает величины 7+ Е (!п(1 — 1/р) + 1/(р 1)) = 7+ Е !о(п) !и Дп) р простое в>т = 1.03465 38818 97437 9116197942 9846463825 46703+. (9) (См. О. Н, Нате(у, Е. М. Ъг!8Ьг, Ап 1пггог!исбоп 10 гЛе ТЬеогу о/ХитЬегв, 51Ь еб!1!оп (Ох$огб, 1979), 322.11; см. также Р. Егббз, М. Кас, Ашег.
Х МагЛ. 26 (1940), 738-742.) Размер простых множителей имеет примечательную связь с перестановками. Среднее число битов в Л-и наибольшем простои множителе случайного и-битового числа при и -4 оо асимптотически стремится к средней длине Л-го наибольшего цикла перестановок случайного и-элемента. [См. Р. Е. Кпи1Ь апе! 1,. ТгаЬЬ Раге!о, ТЬеогег!са! Сотр.
Ясй 3 (1976), 321 — 348; А. М. Вершик, Бои'е1 Ма!Ь. Рой!ае!у 34 (1987), 57-6Ц Отсюда следует, что алгоритм А сначала находит несколько малых множителей, а затем начинает долгий поиск остальных ббльших множителей. Прекрасное описание распределения вероятностей простых множителей для случайных целых чисел приведено в статье Патрика Биллингслея (Рагйс!г В!!!!п8з!еу), опубликованной в журнале АММ 80 (1973), 1099-1115 (см, также его статью в АппаЬ оГРгоЬаЬ!!Ву 2 (1974), 749 — 791). Разложение на простые множители с использованием псевдослучайных циклов.
В начале главы 3 указывалось, что выбранный генератор случайных чисел дает числа, которые оказываются не совсем случайными. Этот тезис, работавший в той главе против нас, здесь оборачивается благом н ведет к поразительно эффективному методу разложения на простые множители, открытому Дж. М. Поллардом (3. М. Ро!)аге!) (В1Т 15 (1975), 331 — 334).
Число шагов вычислений в методе Полларда имеет порядок ~Гр, м поэтому при больших Х он значительно быстрее алгоритма А. Как следует из уравнения (7) и рис. 12, время выполнения алгоритма, реализующего метод Полларда, обычно меньше, чем К~1~. Пусть /(х) — нилином с целочисленными коэффициентами. Рассмотрим две последовательности хо = уо — — А; х„,+1 — — /(х„) шод Х, у„,~1 — — /(у,„) шодр, (10) где р — любой простой множитель числа Х. Тогда у = х шобр при т > 1. Из упр. 3.1-7 видно, что для некоторого т>1 выполняется равенство у = уц где 4(т) — наибольшая степень 2, не превышающая т. Таким образом, разность х„, — хц„,1 1 будет кратна р.
Далее, если /(у) шодр ведет себя как случайное отображение множества (О, 1, ..., р -1) на самое себя, то, как показано в упр. 3.1 — 12, среднее значение наименьших из таких т будет порядка ~/р. Фактически это среднее значение для случайных выборок меньше 1.625 Я(р), как показано в упр. 4 ниже; функция Я(р) в и/пр/2 была определена в разделе 1.2,11,3. Если различные простые делители числа Х соответствуют различным значениям т (что для больших Х почти всегда верно), их можно найти, вычисляя аса(х„— хц 1 м Х) для т = 1, 2, 3, ... до тех пор, пока остаток от деления на множитель не станет простым.
Поллард назвал этот метод ро-методом, так как периодическая последовательность аида уо, ум ... напоминает греческую букву р. Из главы 3 известно, что линейный полинам /(х) = ах+с не обеспечивает достаточной случайности последовательростн. Следующим простейшим видом палииома является квадратичный полинам /(х) = хз + 1. Нам неизвестно., обеспечивает ли данная функция случайность, но недостаток знаний по этому вопросу склоняет нас, скорее всего, в пользу гипотезы о том, что функция обеспечивает достаточную случайность, а эмпирическая проверка показала, что она ведет себя так, как и предполагалось. В действительности же функция /, вероятно, даже дает немного больше, чем случайность, так как хз + 1 содержит только -'(р + 1) различных значений по модулю р (см. Агпеу, Вепдег, Расйбс Х Магй. 103 (1982), 269 — 294).
В связи со сказанным уместна следующая процедура. Алгоритм В (Разложение на простые множители при помощи ро-метода). Этот алгоритм с высокой вероятностью вычисляет простые множители данного целого числа Х > 2, хотя не исключен и отрицательный результат (т. е. множитель найден не будет. —. Прим.
перев.). В1. (Начальная установка.] Присвоить х < — 5, х' +- 2, 1' < — 1, 1 < — 1, и < — Х. (Во время выполнения этого алгоритма число и не является множителем числа Х, а пеРеменные х и х' пРедставлиют величины х шод и и хдп0 ~ пюа и в выражении (10), где также /(х) = хз + 1, А = 2, 1 = 4(т) и lс = 21 — т.) В2. (Проверить, будет ли число простым.] Если и — простое число (рассматривается ниже), вывести и в качестве результата; на этом выполнение алгоритма завершается. ВЗ. [Множитель найден7) Присвоить д +- боб(х' — х, и). Если д = 1, то перейти к шагу В4; в противном случае вывести д.
Теперь, если д = и, алгоритм завершается (его выполнение прерывается, ибо нам известно, что и не является простым числом). В противном случае присвоить и ь- и/д, х 4 — х люби, х' 4 — х' шайи и возвратиться к шагу В2. 13аметим, что д может и не быть простым числом— это подлежит проверке. В каждом случае, когда д — не простое число, его простые множители не могут быть определены при помощи этого алгоритма.) В4. 1Продвинуться.] Присвоить /с ~- 5 — 1. Если й = О, то присвоить х' 4 — х, 1 ь- 21, 5 4 — Б Присвоить х 4- (хз + 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 000000. При р < 10 максимум т(р) равен т(874 771) = 7685.
Максимум функции т(р)/ /р достигается при р = 290047 и т(р) = 6251. На основании этих результатов почти все 12-разрядные числа можно разложять на простые множители быстрее чем за 2 ООО итераций алгоритма В (сравните с 75 000 операций деления, требуемых для выполнения алгоритма А).
Время на каждой итерации алгоритма В, в основном, затрачивается на выполнение умножения и деления с многократной точностью на шаге В4 и на вычисление наибольшего общего делителя на шаге ВЗ. Выполнение этих операций может быть ускорена за счет применения методики "умножения Монтгомери" (см. упр. 4.3.1-41). Более того, в случае, когда операция нахождения наибольшего общего делителя выполняется медленно, Поллард предложил ускорить процесс путем накапливания произведения по модулю и, скажем, десяти последовательных значений (х' — х) перед тем, как искать наибольший общий делитель. Таким образом, 90% операций нахождения наибольшего общего делителя заменяется одним умножением по модулю Х ценой некоторога увеличения вероятности того, что решение при этом не будет найдено.
Поллард также предложил начинать вычисления на шаге В1 с т = д, а не с т = 1, где д равно одной десятой от количества итераций, которые планируется реализовать. В тех редких случаях, когда для больших Х результат не был найден, можно применить функцию /1х) = х~ + с при некотором с 74 0 или 1. следует избегать также значения с = -2, поскольку рекуррентное уравнение х „, = х„, — 2 имеет 2 решение в виде х,„= тз + т ' . Похоже, чта другие значения параметра с не приводят к возникновению простых связей по модулю р и все они должны быть удовлетворительными при подходящих начальных значениях. Ричард Брент применил эту модификацию алгоритма В для нахождения простого множителя 1238926361552897 числа 2зав + 1. [См. Май.
Сошр. 36 (1981), 627 — 630; 38 (1982), 253-255.] Метод Ферма. Другой подход к решению проблемы разложения чисел на простыв множители, который в 1643 году предложил Пьер де Ферма (Р1егге г1е Реппа1), более подходит для поиска больших множителей, нежели малых. [Описание метода, данное самим Ферма и переведенное на английский язык, можно найти в книге Л. Е. Диксона (Ь.
Е. 01саэоп) НЫгогу оГ сйе Тйеогу оГХшпбегэ 1 (Сагпе81е 1пэц о1 Ъавп1пйсоп, 1919), 357.) Допустим, что Х = ие, где и < е. Для практических целей можно положить, что Х вЂ” нечетное число. Это означает, что и и е тоже нечетны. Можно также положить, что х = (и+ е)/2, у = (е — и)/2, (12) Х=х~ — у, 0<у<х<Х. (13) Суть метода Ферма заключается в том, что ишу тся такие значения х и у, которые удовлетворяют уравнению (13). В следующем алгоритме показано, как таким путем можно разложить число на простые множители, не выполняя операций деления. Алгоритм С (Рпзлоэтсение на просшме множители при помощи операций слолсения и вычитания).
По данному нечетному числу Х этот алгоритм определяет наибольший множитель числа Х, меньший или равный етХ. С1. [Начальная установка.) Присвоить х +- 2[~/Х! + 1, у е — 1, т е- [его)з — Х. (Во время выполнения этого алгоритма величины х, у, т отвечают соответственно величинам 2х+ 1, 2у+ 1, хэ — ут — Х в уравнении (13). Должно соблюдаться условие [т[ < х и у < х.) С2. [Выпалнено7[ Если т = О, то выполнение алгоритма завершается.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
