Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 9
Текст из файла (страница 9)
Х14. (Проверить хз — Аг.] Присвоить у < — (~/х~ — Я) или (~Й~ -Ф). Если у~ = хз — Аг, то (х — у) — искомый множитель. Завершить выполнение алгоритма; в противном случае возвратиться к шагу ВЗ. 3 Ускорить выполнение этой процедуры можно различными способами. Например, выше было отмечено, что для случая Аг шог! 3 = 2 значение х должно быть кратным 3; можно положить, что х = Зх', и использовать другое сито, соответствующее х', повысив скорость выполнения операций в три раза. Если Ю шод 9 = 1, 4 илн 7, то х должно быть сравнимо с х1, х2 или х4 (но модулю 9); так что можно, пропустив числа через два сита (одно для х', а другое — для х", где х = 9х' + а и х = 9хи — а), повысить скорость и 4-' раза.
Если Т1гпюд4 =- 3, то хшос!4 известно и скорость повысится еще в 4 раза; в другом случае, когда Ж шод 4 = 1, х должно быть нечетным, что повысит скорость в два раза. Еще одни способ удвоения скорости (ценой расширения объема применяемой памяти) заключается в объединении пары модулей путем использования т, ь тг вместо ть для 1 < Й < Зг. 1 Еще более важный способ повышения скорости выполнения алгоритма П сос~тоит в использовании булевых операций, которые реализованы в болыпинстве двоичных компъютеров. Будем считать, что М1Х представляет собой двоичный компьютер с длиной слова 30 бнт.
Таблицы л(г„Ц можно хранить в памяти так, чтобы на кажлую позицию приходился один бит; таким образом, в одном слове можно хранить 30 значений. Операцию АМР, которая заменяет Й-й бнт накопителя нулем, если й-й бит заданного слова в памяти есть нуль для 1 < А < 30, можно использовать для одновременной обработки 30 значений х! Для удобства можно сделать несколько копий таблиц Я(1, Я с тем, чтобы элементы таблицы лля т; занимали !сп1(гл;, 30) бит. Тогда таблицы просеивания для каждого модуля заполнят некоторое целое число слов. При таких предположениях выполнение основного цикла алгоритма П 30 раз эквивалентно такой последовательности команд.
гП <-А',. гА +- Я'(1, г1Ц. гП +- гП вЂ” 1. ЯТ1 Кх 1МСХ ЗО ЛАЯ 02 По существу, количество пиклов, необходимых для выполнения 30 итераций, равно 2 + Зг; в случае, если г = 11, это означает, что на выполнение одной итерации 02 1.01 К1 1.РА 31,1 РКС1 1 31ММ э+2 1МС1 М1 ЗТ1 К1 1.Р1 К2 АМ0 32,1 РЕС1 1 31ММ э+2 1МС1 М2 ЯТ1 К2 1.01 КЗ Если гП < О, то присвоить гП +- гП + 1слг(ты ЗО) А', +-гП.
гП +- А). гА ~- гА Л У(2, гП). гП +- гП вЂ” 1. Если гП < О, то присвоить гП < — гП + !сю(тм ЗО). А) + гП +- Аэ, (От тз до т, так же, как те ) А'„+- гП. х 1- х+ЗО. Повторить, если все просеяно. $ затрачивается три цикла, как и в алгоритме С, но в алгоритме С, кроме того, выполняется еще 9 = -'(е — и) итераций. Если бы элементы в таблице для пз, занимали не целое число слов, то на каждой итерации необходимо было бы выполнять сдвиг элементов таблицы, чтобы биты были расположены должным образом. Это привело бы к добавлению в основной цикл множества дополнительных команд и, вероятно, сделало бы выполнение программы слишком медленным для всех значений е/и > 100 по сравнению с алгоритмом С (упр.
7). Процедуры просеивания можно применять к множеству других задач, не обязательно связанных с выполнением арифметических действий. Обзор этих методов выполнен Марвином хЬ Вундерлихом (Магг!и С. %цпбег!!сп) и приведен в Х4СМ 14 (1967), 10-19. В 19 веке для разложения чисел на простые множители Ф. У. Лоуренс (Р. Ж, Ьажгепсе) предложил конструкцию специальных просеивающих машин (ф)ага Х оуРиге апг! Аррйеб Май, 28 (1896), 285 — ЗП), а в 1919 году Э.
О. Карнсан (В. О. Сапээап) дополнил такое устройство еще 14-ю модулями. (С интересной историей того, как были заново открыты и сохранены для потомства давно забытые сита Карнсана, можно ознакомиться в работе БЬайг, %!)!!атэ, Мота!и, Май. 1пгеП!8епсег 17,3 (1995), 41-47,] Много различных просеивающих машин было разработано и использовалось в течение 1926-1989 годов Д. Г. Лемером и его сотрудниками, которые начали с велосипедных цепей, а позже использовали фотоэлектронные элементы и другие технологии (см., например, АММ 40 (1933), 401-406).
Электронное решето Лемера, использующее линию задержки, которое было запущено в эксплуатацию в 1965 году, обрабатывает один миллион чисел в секунду. К 1995 году стало возможным сконструировать машину, которая просеивает 6144 млн чисел в секунду, выполняя 256 итераций на шагах В2 и ВЗ за почти 5.2 нс. (См. 1лйее, Рат!егзоп, %!!!!ашз, )зЗепи АгсИеХ гоог ЯЗэйппде (4) 13 (1995), 113-139.) Д. Г.
Лемер и Эмма Лемер (В. Н. апд Епнпа Ьейпег) описали в Май, Сотр. 28 (1974), 625-635, другой способ разложения на простые множители с использованием решета. Проверка принадлежности чисел к простым. Из всех рассмотренных до сих пор алгоритмов ни один не может эффективно определить, является ли большое число и простым. К счастью, существуют другие способы решения этой задачи. Эффективные способы были разработаны Э. Люка (Й.
Ьпоы) и др., в частности Д. Г. Лемером !см. Вп!!. Атег. Май. Яос. ЗЗ (1927), 327 — 340). Согласно теореме Ферма (теорема 1.2.4Р) хг шпор = 1, когда р — простое число и х не кратно р. При этом имеются эффективные методы вычисления х" ' п1од п, требующие только 0()ойп) операций умножении по модулю и. (Они будут исследоваться в разделе 4.6.3.) Поэтому зачастую можно определить, что и не является простым, убедившись, что данное условие не выполняется.
Например, однажды Ферма установил, что числа 2' + 1, 2~+ 1, 2" + 1, Зэ + 1 и 2га+1 являются простымн. В письме Мерсеяну (Мегэеппе), написанному в 1640 году, Ферма предположил, что 2з + 1 — всегда простое число, и сообщил, что он не в состоянии определить, является лн простым число 4 294967297 = 2зт+1. Ни Ферма, нн Мерсенн так и не решили этой задачи, хотя могли сделать это следующим образом: можно. вычислить число Зз шоб (2зз + 1), выполнив 32 операции возведения в квадрат по модулю 2з~ + 1, и получить результат, равный 3029026160; поэтому (по теореме, открытой Ферма в том же 1640 году!) 2зз + 1 — не простое число.
Данный аргумент не дает никакого представления о том, чему равны множители, но является ответом на поставленный Ферма вопрос. Теорема Ферма представляет собой мощное средство анализа, которое дает возможность определить„что данное число не является простым. Если число и не простое, то всегда можно найти такое значение х < и, что х" ' шоб и Э! 1. Опыт показывает, что такое значение почти всегда находится очень быстро.
Существует несколько редких значений числа и, для которых х" ' шоб и часто равно единице, но тогда п имеет множитель, меньший /и (упр. 9). Этот метод может быть расширен для доказательства того, что большое число и действительно леляешся простым, если использовать следующую идею. Если имеется число х, для которого порядок х по модулю и равен и — 1, то и — простое чпсло. (Порядок числа х по модулю и — это наименьшее положительно целое число л, такое, что х~ шоб и = 1; см. раздел 3.2.1.2.) Из этого условия следует, что числа я' шобп, ..., х" ' шог)п различны и взаимно просты с п, а следовательно„это должны быть числа 1, 2, ..., и — 1, расположенные в некотором порядке.
Таким образом, и не имеет ни одного собственного делителя. Если и — простое число, то такое число х (называемое первообразнььм корнем числа и) всегда существует (см. упр. 3.2.1.2-16). В действительности таких первообразных корней довольно много. Существует фп — 1) таких чисел, и зто достаточно большое число, так как и/у(п — 1) = 0(1ок1ояп). Чтобы определить, будет ли порядок х равен и — 1, совсем необязательно вычислять х~ шоб и для всех й < п — 1.
Порядок х будет равен и — 1 тогда и только тогда, когда выполняются условия !) х" ' шобп = 1; й) х!" П/г пкк1п ф 1 для всех простых чисел р, которые делят п — 1. Следовательно, х' шоб и = 1 тогда и только тогда, когда е кратно порядку числа х по модулю и. Поэтому, если оба условия выполняются и если х есть порядок х по модулю п, Й является делителем и — 1, но не является делителем числа (и — 1)/р ни для одного простого множителя р числа п — 1.
Значит, остается единственная возможность — й = и — 1. Этим завершается доказательство того, что условий (!) н (й) достаточно, чтобы установить, является ли число и простым. В упр. 10 показано, что для каждого из простых р можно использовать различные значения х, а п все еще будет оставаться простым числом. Можно ограничиться этими соображениями относительно простых чисел для х, поскольку порядок произведения ие по модулю и делит наименьшее общее кратное порядков и и и согласно результатам упр. 3.2.1.2-15.
Соблюдение условий (1) и (И) можно эФФективно проверить при помощи быстрых методов вычисления степеней чисел, которые рассматриваются в разделе 4.6.3. Но необходимо знать простые множители числа и — 1, поэтому возникает интересная ситуация, когда разложение на простые множители числа и зависит от разложения на простые множители числа и — 1. Пример.
Разложение на простые множители достаточно большого числа полюгает уяснить идеи, рассмотренные до сих пор. Попробуем найти простые множители 65-разрядного числа 2зы + 1. Проявив некоторую сообразительность, процесс разложения на простые множители можно начать, приняв во внимание интересное свойство исходного числа 2зы + , (2зот 2ы + ц(2зот + 2зз + 1). это частный случай разложения 4хз + 1 = (2яз + 2я + 1)(2яз — 2я + 1), о котором Эйлер сообщал Гольдбаху (Оа16ЬвсЬ) в 1742 году [Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
