AOP_Tom2 (1021737), страница 117
Текст из файла (страница 117)
Имеем Х = ((х — у)/2) ((х + у — 2)/2), а (х — у)/2 — -наибольший множитель для Х, меньший или равный ~/Х. СЗ. [Шаг по х.[ Присвоить т +- т + х и х ~- х + 2. С4. [Шаг по у.[ Присвоить т < — т - у и у ( — у Ч 2. Сб. [Проверить т.) Если т > О, то возвратиться к шагу С4, иначе возвратиться к шагу С2. Возможно, читатель сочтет небезынтересным поиск вручную простых множителей числа 377 при помощи этого алгоритма, Число шагов, необходимых для нахождения множителей и и е числа Х = ие, по существу, пропорционально (х + у — 2)/2 — [~IХ) = е — [ /Х) это, конечно, может оказаться очень большой величиной, хотя каждый швг на большинстве компьютеров может выполняться очень быстро.
Р. Ш. Леман (К. Б. Ее12шап) (21Хасб. Сотр. 28 (1974), 637 — 646) усовершенствовал алгоритм таким образом, что в худшем случае для его выполнения требуется только 0(Х'~~) операций. Называть алгоритм С методом Ферма не совсем правильно, поскольку Ферма использовал несколько более обтекаемый подход. В компьютерах основной цикл алгоритма С выполняется довольно быстро, но для вычислений вручную он мало пригоден. На самом деле Ферма не сохранял текущие значения 9; он рассматривал величину х — Л' и, исходя иэ наименее значимых разрядов, делал вывод о том, 2 является ли эта величина полным квадратом.
(Последние два разряда полного квадрата должны быть 00, е1, е4, 25, об или е9, где е — четная, а о — нечетная цифра.) По этой причине он избегал операций, которые выполнялись на шагах С4 и С5, заменяя их при помощи специальных приемов операцией определения числа, не являющегося полным квадратом. Предложенный Ферма способ просмотра правых крайних разрядов можно, конечно, обобщить, используя другие модули.
Предположим для ясности, что Л' = 8616460 799 (историческое значение этого числа описывается ниже), и рассмотрим следующую таблицу. и (х2 — х) пюй тп равно 1, 2, 2 1, 2, О, О, 2 5, б, 2, О, О, 2, 6 1, 2, 5, 2, 1, 2, 5, 2 , то х' шой т равно 0,1,1 О, 1, 4, 4, 1 О, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1 Если х шойгп равно О, 1, 2 О, 1, 2, 3, 4, 5, 6 О, 1, 2, 3, 4, 5, б, 7 О, 1, 2, 3, 4, 5, 6, 7„ 8, 9, 10 3 5 7 8 11 Если величина х2 — 2У есть полный квадрат 92, то она должна иметь остаток по модулю т, соответствующий этому факту. Например, если Л' = 8616460799 и х шой 3 ~ О, то (х2 — Л') пюй 3 = 2, т, е. величина х2 — Л' не может быть полным квадратом.
Поэтому х должно быть кратным 3 дли всех значений 2У = х' — 92. Из таблицы видно, что х й3=0; хшой5 =0,2 или 3; хшой7 =2,3,4или5; х гной 8 = 0 либо 4 (отсюда х пюй 4 = 0); х шой 11 — 1, 2, 4, 7, 9 или 10. (14) Это значительно сокращает процесс поиска х. Пусть, например, х должно быть кратно 12. Тогда должно быть х ) (чгХ1 = 92825 и наименьшим числом, кратным 12, является число 92832. Это значение дает в остатке (2,5,3) по модулю (5, 7, 11) соответственно, поэтому оно не удовлетворяет уравнению (14) по отношению к модулю 11.
Увеличив х на 12, можно заменить остаток по модулю 5 на 2, по модулю 7 на 5 и по модулю 11 на 1. Поэтому легко увидеть, что первое значение величины х > 92 825, удовлетворяющее всем условинм в уравнении (14), есть х = 92 880. Теперь 928802 — Х = 10233601, и, вычислив вручную квадратный корень, получаем, что 10233601 = 31992 действительно является полным квадратом. Таким образом получено искомое решение х = 92880, 9 = 3 199, а разложение на простые множители имеет вид 8616460799 = (х — у)(х+ у) = 89681 96079. Это значение Х интересно тем, что английским экономистом и логиком У. С. Дживонсом (чч'. Б. Лечопз) в хорошо известной книге оно было введено следующим образом: "По данным двум числам можно найти их произведение простым и надежным способом, но совсем другое дело, когда дчя большого числа необходимо найти его множители.
Можно ли сказать, какие два числа были перемножены, чтобы получилось число 8 616 460 7997 Я думаю, что вряд ли кто-либо, кроме меня, знает это". [7ое РНпс1р1ее оГ Вс1епсе (Масло!1ап, 1874), СЬарсег 7.] Однако, как следует из вышесказанного, Ферма смог разложить это число на простые множители на обратной стороне конверта меньше чем за десять минут! Основная мысль Дживонса о сложности разложения чисел на простые множители по сравнению с их перемножением справедлива, но только в случае, когда мы имеем дело с произведением чисел, не настолько близких друг к другу. Вместо модулей, рассматриваемых в уравнении (14), можно использовать любые степени различных простьгх чисел.
Например, если взять 25 вместо 5, то возможные значения величины х шо625 будут равняться О, 5, 7, 10, 15, 18 и 20. Это дает больше информации, чем (14). В общем случае можно получить больше информации, выполняя операции по модулю р~, чем по модулю р, при нечетных р, если х — Л: — 0 (по модулю р) имеет решение х. Рассмотренный модулярный метод называется методом решета (сита) (сбече ргосеапге), так как можно представить, что все целые числа проходят через "решето", пропускаюшее только те значения, для которых х шое1 3 = О; затем эти числа просеиваются через другое сито, которое пропускает только числа, для которых хшо65 = О, 2 или 3, и т.
д. Каждое сито в отдельности отсеивает примерно половину оставшихся значений (см. упр. 6), Когда же просеивание ведется при помаши попарно взаимно простых модулей, то на основании китайской теоремы об остатках (теорема 4.3.2С) каждое сито работает независимо от остальных. Поэтому, если выполнять просеивание относительно, скажем, 30 различных простых чисел, то для того, чтобы определить, будет ли величина хз — Х полным квадратом для у~, достаточно из каждых 2зо величин проверить только одну. Алгоритм Р (Разложение на простые множители методом решета). По данным нечетным числам Ж этот алгоритм определяет наибольший множитель числа Х, меньший или равный ч/М.
В процедуре используются попарно взаимно простые модули гпы тш ..., т„, которые также взаимно просты с Х. Предположим, что доступны т таблиц проееиеанил о[1,А, 0 < у < т„1 < 1 < г, где о'[г, я = [ут — Х = у' (по модулю т,) имеет решение у]. Р1. [Начальная установка.] Присвоить х < — [~/А7] и /с, < — ( — х) шодт; при 1<1<с.
(Во время выполнения этого алгоритма индексные переменные ел, кш ..., х, будут установлены таким образом, что 1г, = ( — х) шод т,.) Р2. [Просеять.] Если 8[1, 1,] = 1 при 1 < ю' < г, то перейти к шагу Р4. Р3. [Найти х.] Присвоить х +- х + 1 и к; < — (х; — 1) шодт; при 1 < 1 < г. Возвратиться к шагу Р2. Р4. [Проверить хз — Ас.] Присвоить у с — [~/хз — )с'] или [л/хз — сУ].
Если уз = х — Ас, то [х — у) — искомый множитель. Завершить выполнение алгоритма; г в противном случае возвратиться к шагу РЗ. 1 Ускорить выполнение этой процедуры можно различными способами. Например, выше было отмечено, что для случая )с' шос) 3 = 2 значение х должно быть кратным 3; можно положить, что х = Зх', и использовать другое сито, соответствующее х', повысив скорость выполнения операций в три раза.
Если сс' шос) 9 = 1, 4 или 7, то х должно быть сравнимо с х1, х2 или х4 [по модулю 9); так что можно, пропустив числа через два сита [одно для х', а другое — для х", где х = 9х' + а и х = 9х" — а), повысить скорость в 4;,' раза. Если Асшос)4 = 3, то хщос)4 известно и скорость повысится еще в 4 раза; в другом случае, когда Ас тес) 4 = 1, х должно быть нечетным, что повысит скорость в два раза. Еще один способ удвоения скорости [ценой расширения объема применяемой памяти) заключается в объединении пары модулейпутем использованияспс ь пса вместопсь для 1 < Й < -г. 1 Еще более важный способ повышения скорости выполнения алгоритма Р сосстоит в использовании булевых операций, которые реализованы в большинстве двоичных компьютеров.
Будем считать, что И1Х представляет собой двоичный компьютер с длиной слова 30 бит. Таблицы Я[с,)сс] можно хранить в памяти так, чтобы на каждую позицию приходился один бит; таким образом, в одном слове можно хранить 30 значений. Операцию АИО, которая заменяет А-й бит накопителя нулем, если Й-й бит заданного слова в памяти есть нуль для 1 < сс < 30, можно использовать для одновременной обработки 30 значений х) Для удобства можно сделать несколько копий таблиц Я[с, с] с тем, чтобы элементы таблицы для т, занимали 1сш[пс„30) бит. Тогда таблицы просеивания для каждого модуля заполнит некоторое целое число слов. При таких предположениях выполнение основного цикла алгоритма Р 30 раз эквивалентно такой последовательности команд.
гП +- А[. гА +- Я'[1, гП]. гП +- гП вЂ” 1. ЗТ1 Кг 1ИСХ 30 ЛАЗ 02 По существу, количество циклов, необходимых для выполнения 30 итераций, равно 2 + Зг; в случае, если г = 11, это означает, что на выполнение одной итерации 02 101 К1 1.0А З1,1 0ЕС1 1 31ИИ э+2 1ИС1 М1 ЗТ1 К1 1.01 К2 АИ0 З2,1 0ЕС1 1 Л1ИИ э+2 1ИС1 М2 ЗТ1 К2 001 КЗ Если гП < О, то присвоить гП +- гП + 1спл(шп ЗО) А', +- гП.
гП с — /с2. гА +- гА Л Я'[2, г1Ц. гП +- гП вЂ” 1. Если г?1 < О, то присвоить гП +- гП + 1ст(псс, ЗО). Ас + — |П, гП +- /сс. (От псз до пс, так же, как псэ.) А', +- гП. х + — х+ ЗО. Повторить, если все просеяно. $ затрачивается три цикла, как и в алгоритме С, но в алгоритме С, кроме того, выполняется еще у = —.(е — и) итераций. Если бы элементы в таблице для т; занимали не целое чишю слов, то на каждой итерации необходимо было бы выполнять сдвиг элементов таблицы, чтобы биты были расположены должным образом. Это привело бы к добавлению в основной цикл множества дополнительных команд и, вероятно, сделало бы выполнение программы слишком медленным для всех значений е/и > 100 по сравнению с алгоритмом С (упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
