AOP_Tom2 (1021737), страница 121
Текст из файла (страница 121)
По данным положительному целому числу >у и положительному целому числу е, такому, что число Й>У не является точным квадратом; этот алгоритм предпринимает попытку найти решения уравнения (19) для данной последовательности простых чисел р>, ..., р, исследуя сходимость цепной дроби для >Й>>>.
(Другой алгоритм, использующий для поиска множителей числа >У выходные данные (алгоритма Е. —- Прим. перев.), является предметом рассмотрения в упр. 12.) Е1. [Начальная установка.] Присвоить П +- лХ, Л (- [»Ъ], Л' ~- 2Л, П ~- Г < — Л', Е < — 1, 1г' < — 1з — Лз, Р е- Л, Р' +- 1, А е — О, Я < — О.
(Следуя основной процедуре упр. 4.5.3-12> алгоритм находит разложение в цепную дробь числа >/к>>'. Переменные П, 6", Ъ', Ъ"', Р, Р', А и Л представляют Л+ П„, Л + П„>, Ъ'„, Ъ'„„р„п>ой>У, р„> шо>(Х, А„и пшо>12 соответственно. Всегда будет выполняться неравенство 0 < 1> < П < Л', поэтому самая высокая точность потребуется только для нахождении чисел Р и Р'.) Е2.
[Продвинуть П, Ъ; Я.] Присвоить Т < — $; Ъ' ~ — А(à — П) + 1г', Ъ' ь — Т, А ~— [Г/Ъ'], Г с — П, П +- Л' — (П шо>1 Ъ'), Я е — 1 — Я. ЕЗ. [Разложить на множители И.] (В соответствии с результатами упр. 4.5.3-12(с) здесь имеем Р> — lс>>>Я> = ( — 1)ЯГ) Присвоить (ео, е>,..., е,„) е — (Я,О,...,О), Т < — Г Теперь нужно выполнить следующее. Для 1 < > < и>, если Т шо>1 р = О, присвоить Т < — Т/р и е> ~ — е + 1 и повторять этот процесс до тех пор, пока не полу'чится Т п>о>( р- ф О. Таблица 1 ПРИМЕР ВЫПОЛНЕНИЯ АЛГОРИТМА Е Ж = 197209, Ь = 1, оз = 3, рз = 3, рз = 3, рз = 5 Выход 1о9 316 ев +2" 3 5' 133 218з са +2о 34 5! 37250 ээ -2з Зз 5о Е4.
(Решение?] Если Т = 1, вывести значения (Р,ео,ез,...,е ), которые составляют решение уравнения (19). (Если получено достаточное число решений, то на этом шаге алгоритм может быть завершен.) Еб. (Продвинуть Р, Р'.', Если T ф 1, присвоить Т < — Р, Р < — (АР + Р') шобХ, Р' з- Т и возвратиться к шагу Е2. В противном случае процесс разложения в цепную дробь начинает повторять цикл сначала, за возможным исключением Я, и поэтому выполнение алгоритма на этом завершается. (Обычно данный цикл настолько продолжителен, что завершение не происходит.) 5 В качестве примера применения алгоритма Е к сравнительно малым числам рассмотрим случай, когда Х = 197209, й = 1, пз = 3, р, = 2, рз — — 3, рз — — 5.
Начальная часть вычислений представлена в табл. 1. Продолжение вычислений приводит к получению за первые 100 итераций 25 выходных данных; другими словами, алгоритм находит решения очень быстро, но некоторые из них тривиальны. Например, если продолжить вычисления еще на 14 шагов, можно получить 1971973 = 24 Зз .
5о выходных данных, которые не представляют интереса, поскольку 197197 в— е — 12. Для завершения процесса разложения на простые множители достаточно первых двух решений, полученных выше. Так как получено (159316 133218)' = (23 Зз 5')3 (по м~ду~ю 197209). соотношение (18) выполняется при х = (159316 133218)шо6197209 = 126308, у = 540. В соответствии с алгоритмом Евклида 8сз1(126308 — 540, 197209) = 199, и получаем изящное разложение 197209 = 199 991. Чтобы понять причины, по которым алгоритм Е столь успешно выполняет разложение больших чисел на простые множители, рассмотрим эвристический анализ времени выполнения алгоритма Е, следуя неопубликованной идее, высказанной После Е1: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: У Р А Р 888 1 0 444 876 73 12 444 882 145 6 5 329 857 37 23 32 418 751 720 1 159 316 852 143 5 191 734 681 215 3 131 941 863 656 1 193 139 883 ЗЗ 26 127 871 821 136 6 165 232 877 405 2 133 218 875 24 Зб 37 250 490 477 1 93 75о 6 Т 0 1 73 О 29 1 37 0 1 1 143 0 43 1 41 0 11 1 17 0 1 1 1 0 53 автору в 1975 году Р, Шруппелем (Н.
8с)тгоерре1). Положим для определенности, что й = 1. Число выходных данных, необходимых для получения разложения числа )бу на простые множители, пропорционально пт — числу выделенных в процессе вычислений малых простых чисел. Каждый раз на выполнение шага ЕЗ затрачивается порядка пт!обХ единиц времени, так что общее время выполнения в первом приближении пропорционально величине тз 1ок)б'(/Р, где Р— вероятность получения очередного результата на каждой итерации. Предположим, что в течение всего времени выполнения алгоритма величина Г равномерно распределена и интервале от 0 до 24/)грт, тогда вероятность Р равна значению (24/)тбт) ', умноженному на количество целых чисел < 24/)б', для которых все простые множители принадлежат множеству (р),...,р ).
В упр. 29 приведена нижняя граница для Р, из которой можно заключить, что наибольшее время выполнения алгоритма имеет порядок 2УУ юг1обЛУ ) 1о82 /У гдег= ~ пту'/г. '~ !ой е у р рб * )Л _#_БТуу,* р у =О) )б ), у . „Б47)) УУ вЂ” У, фу у )22) упрощается и принимает вид .,р)руТУ УУ)ИБУ,Р) Р))У,ТУУ)'У')У,ТУ,ТУУ)-'У')У б) б~ бб))). Следовательно, при надлежащих предположениях ожидаембте время выполнения р б р.
№У У, )УУ) УЛТР')У УУ стремится к 0 при )"ТУ -4 оа. Когда число )т) находится в интервале, чаще всего используемом на практнкеу нужно быть осторожным и не принимать всерьез такую асимптотическую оценку. Например, если Х = 10зе, получим Х)у'УР = (18Х)" при о 4.75, но то же самое соотношение справедливо и для а рв 8.42, когда'Х = 10зее, Функция №)~1 имеет порядок роста, который представляет собой некоторого рода пересечение )ТУ))Ь и (18Х), но все три равенства практически одинаковы для чисел тур, не являющихся недопустимо большими. Многочисленные вычислительные зксперименты, выполненные М.
Ч. Вундерлихом (М. С. ртрппт(ег11с1)), показали, что хорошо настроенный вариант алгоритма Е значительно лучше выполняет разложение, чем предусматривается втой оценкой [см. Ьессиге )рогез тп Май. 751 (1979), 328-3421: несмотря на »УУ=УР" ° -*.УуУ У УУ)У б) .бр,,р р р.. множители тысяч чисел в интервале 10'б < ттт < 104в он получил выражение для времени выполнения, равное приблизительно ут)е'Б.
Попытка выполнить разложение числа Х с помощью алгоритма Е начинается. по существу, с замены Х на БХ, что выглядит довольно любопытно (если не откровенно глупо). "Простите, как вы смотрите на то, что перед попыткой разложения числа я умножу его на 37Р Тем не менее идея выглядит привлекательной, поскольку некоторые значения й делают числа 1)' потенциально делимыми на меньшие простые числа, и позтому на шаге ЕЗ полное разложение зтих чисел на простые множители может быть выполнено проще.
С другой стороны, большое значение числа й сделает числа Ъ' больше, и тогда их полное разложение на простые множители будет затруднено. Нужно сбалансировать зти тенденции путем соответствующего подбора числа Е Рассмотрим, например, делимость чисел 1' на числа, равные степеням о.
На шаге ЕЗ получаем Рз — кХД2 = ( — 1)з1г, так что, если 5 делит и, имеем Р2 = 1Л'Я2 (по модулю 5). В данном соответствии число Ч' не может быть кратным 5, поэтому оно взаимно просто с Р н можно записать (Р/ф2 = ЙХ (по модулю 5). Если предположить, что Р и Я вЂ” случайные взаимно простые числа, такие, что 24 возможные пары чисел (Р пюй 5,Я спой 5) ф (0,0) равновероятны, вероятность того, что 5 делит 1', равна, таким образом, — ' а О, 0 или —" в зависимости от того, 24' 24' ' ' 24 какие значения принимает число АХ гной 5: О, 1, 2, 3 или 4. Аналогично вероятность того что 25 делит 1', равна О, 4е, О, 0 эе соответственно, если только кХ не вое : еоа крапю 25. В общем аэучае для данного нечетного простого числа р, для которого (ЙХ)1е 0~2 шойр = 1, получаем, что у' кратно р' с вероятностью 2/(р' '(р+ 1)): среднее число р делителей числа 1' приближается к 2р/(р2 — 1).
из этого анализа, выполненного Р. Шруппелем (Н. БсЬгоерре!), следует, что лучший выбор числа 14— это значение, которое обеспечивает максимум функции 1 /(р„'кМ) 1обрэ. — — 1обlс, (23) где / определена в упр. 28, поскольку, по существу, это ожидаемое значение величины 1п(э/24Э/Т) при переходе к 2иагу Е4. Если числа й и т хорошо подобраны, выполнение разложения по алгоритму Е дает еще лучшие результаты. Выбор подходящего числа пт может быть выполнен экспериментально, так как проведенный выше анализ аснмптотического поведения носит незавершенный характер и нельзя быть уверенным в точности полученной информации. Поэтому внесение в алгоритм многочисленных уточнений, связанных с таким выбором пэ, может привести к непредсказуемым последствиям.
Например, сравнив выполнение шага ЕЗ с выполнением алгоритма А, можно получить следующее важное усовершенствование. Суть его в том, что процесс разложения на простые множители можно остановить после нахождения Тшойр ~ 0 н (Т/рэ) < р, поскольку в этом случае Т будет либо равно 1, либо простым числом. Если Т вЂ” простое число, большее р„, (в таком случае оно будет не больше р„„+р — 1), то, учитывая, что получено полное разложение на простые множители, можно вывести в качестве результата (Р, ее,..., е, Т). На второй фазе алгоритма будут использованы только те выходные данные, для которых все простые числа Т встретятся не менее двух раз.
Эта модификация приводит к образованию намного большего списка простых чисел без дополнительных затрат времени. Эксперименты Вундерлнха показали, что если значения Аг близки к 104е при гп 150, то алгоритм работает хорошо только с учетом этого уточнения. Так как на выполнение шага ЕЗ приходится большая часть времени выполнения алгоритма, Моррисон, Бриллхарт и Шруппель предложили несколько способов прекращения выполнения этого шага, если результат становится правдоподобным: (а) когда значение Т изменяется таким образом, что его можно представить с однократной точностью, выполнение этого шага продолжается только в том случае, когда (Т/ру) > рэ и 3 ' шой Т ф 1; (Ь) если Т оказывается все еще > рз„после того, как выделены все множители < —,' р,„; (с) выделены только все множители, большие р;„для групп, скажем, из 100 или около того последовательных значений Г; процесс разложения на простые множители может быть продолжен позже, но только для значений у из каждой группы, для которой получен наименьший оста- ток Т.
(Прежде чем выделять множители, большие рэ, полезно вычислить 1' шоб Р,'Рэ'Рз'Р~~'Р~Ь', где все / достаточно малы длн того, чтобы модУли Р,'Рз'Рз'Р~'Рэ' можно было представлять с однократной точностью, но достаточно велики, чтобы выполнялись равенства Ъ' шоб рб = О. Поэтому один остаток с однократной точ- Л э-! постыл будет характеризовать значение Ъ' по модулю пяти малых простых чисел.) По поводу оценки длины цикла выходных данных алгоритма Е обратитесь к работе Н. С. ЪЙ111ашэ, Ма1Л. Сошр. 36 (1981), 593 — 601. ~Теоретическаи верхняя граница.
С точки зрения вычислительной сложности алгоритма желательно знать, существует ли метод разложения на простые множители, ожидаемое время выполнении которого может быть ограничено оценкой 0(№(~~), где е(Ж) -+ 0 при Х -+ со. Выше было показано, что поведение алгоритма Е, вероятно, удовлетворяет такой оценке, однако желательно было бы найти строгое доказательство этого факта, так как цепные дроби не достаточно хорошо упорядочены. Первое доказательство того, что существует такой алгоритм разложения на простые множители, нашел в 1978 году Джон Диксон (ЯоЬп П1хоп). Он показал, что в действительности достаточно рассматривать упрощенный вариант алгоритма Е, из которого убирается аппарат цепных дробей, но основная идея соотношений (18) остается.
Метод Диксона [МагЛ. Сошр. 36 (1981), 255 — 260) состоит в следующем. Предположим, что для числа Х существует по меньшей мере два различных простых множителя и это число Г не делится на первые тп простых чисел рм рз, ..., р . Выберем случайное целое число Х из интервала 0 < Х < Х и положим У = Хэ шо6 Х. Если Г = О, то чишю ксб(Х, Х) являетси надлежащим множителем числа Х. В противном случае, как и на шаге ЕЗ, выделяем все малые простые множители числа Ъ'. Другими словами, выражаем число $' в виде (24) 1г=р', ...р-т, где Т не делится ни на одно из первых т простых чисел. Если Т = 1, то выполнение алгоритма продолжается, как на шаге Е4, и выводятся данные (Х, ем, е ), которые представляют собой решение уравнения (19) при ее —— О. Этот процесс продолжаетея с новыми случайными значениями величины Х до тех пор, пока не наберется достаточно много выходных данных для того, чтобы по методу упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
