AOP_Tom2 (1021737), страница 118
Текст из файла (страница 118)
7). Процедуры просеивания можно применять к множеству других задач, не обязательно связанных с выполнением арифметических действий. Обзор этих методов выполнен Марвином Ч. Вундерлихом (Магтш С. Жиппег!!сЛ) и приведен в ЗАСМ 14 (1967), 10-19. В 19 веке для разложения чисел на простые множители Ф. У.
Лоуренс (Г. %. Ьавтепсе) предложил конструкцию специальных просеивающих машин Яиагк Х о1 Риге аш! Арр!!ед Май. 28 (1896), 285 31Ц, а в 1919 году Э. О. Карисан (Е. О. СаНээап) дополнил такое устройство еще 14-ю модулями. (С интересной историей того, как были заново открыты и сохранены для потомства давно забытые сита Карисана, можно ознакомиться в работе БЛа!!!1, Ю!!!ашв, ,Мага!и, Май. 1псе!!!Келсег 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, другой способ разложения на простые множители с использованием решета. Проверка принадлежности чисел к простым. Из всех рассмотренных да сих пор алгоритмов ни один не может эффективно определить, является лн большое число и простым. К счастью, существуют другие способы ревпения этой задачи. Эффективные способы были разработаны Э. Люка (Е.
Еисаэ) и др., в частности Д. Г. Лемером [см. Ви!! Аэпег. Май. Яос. 33 (1927), 327 — 340). Согласно теореме Ферма (теорема 1.2,4Р) хг ~ шайр= 1, когда р — простое число и х не кратно р. При этом имеются эффективные методы вычисления х" э шаг! п, требующие толька 0(!ойп) операций умножения по модулю и. (Они будут исследоваться в разделе 4.6.3.) Поэтому зачастую можно определить, что и не является простым, убедившись, что данное условие не выполняется. Например, однажды Ферма установил, что числа 2' + 1, 2з + 1, 2 + 1, 2 + 1 и 2'в+1 являются простыми.
В письме Мерсенну (Мегэеппе), написанному в 1640 году, Ферма предположил„что 2э + 1 — всегда простое число, и сообщил, что он не в состоянии определить, является ли простым число 4 294 967 297 = 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о61ойп). Чтобы определить, будет ли порядок х равен п — 1. совсем необнзательно вычислять х шос1 и для всех к < и — 1. Порядок х будет равен п — 1 тогда и только тогда, когда выполняются условия !) х" шос1 и = 1: й) хщ 11е шай и ~ 1 для всех простых чисел р, которые делят и — 1.
Следовательно, х" шой п = 1 тогда и только тогда, когда я кратно порядку числа х по модулю п. Поэтому, если оба условия выполняются и если /с есть порядок х по модулю п, Й является делителем п — 1, но не является делителем числа (и — 1)/р ни для одного простого множителя р числа и — 1. Значит, остается единственная возможность — к = и — 1.
Этим завершается доказательство того, что условий (1) и (й) достаточно, чтобы установить. является лн число и простым. В упр. 10 показано, что для каждого из простых р можно использовать различные значения х, а п все еще будет оставаться простым числом. Можно ограничиться этими соображениями относительно простых чисел для х, поскольку порядок произведения ие по модулю и делит наименьшее общее кратное порядков и н е согласно результатам упр. 3.2.1.2 — 15. Соблюдение условий (г) н (й) можно эфФективно проверить при помаши быстрых методов вычисления степеней чисел, которые рассматриваются в разделе 4.6.3. Но необходимо знать прсктые множители числа и — 1, поэтому возникает интересная ситуация, когда разложение на простые множители числа п зависит от разложения ва простые множители числа и — 1.
Пример. Разложение на простые множители достаточно большого числа помогает уяснить идеи, рассмотренные до сих пор. Попробуем найти простые множители 65-РазРЯдного числа 2аы + 1. ПРоЯвив некотоРУю саобРазательностгч пРоцесс Разложения на простые множители можно начать, приняв во внимание интересное свойство исходного числа 2г~4+ 1 рвот 2ы + 1)рвот+ 2ы + ц. (15) это частный случай разложения 4хх + 1 = (2хэ + 2х + 1)(2хз — 2х + 1), о котором Эйлер сообщал Гольдбаху (Со!6ЪасЬ) в 1742 году 1Р.
Н. Рпзз, Соггезропс~апсе МасЗь е1 Рбуя19ие 1 (1843), 145). 'Задача заключается в исследовании каждого из ЗЗ-разрядных множителей в соотношении (15). Компьютерная программа легко обнаруживает, что 2'ет — 2ьч + 1 = 5. 857 пэ, где 116) пэ = 37866809061660057264219253397 есть 29-разрядное число, не имеющее ни одного простого множителя, меньшего 1 000. Вычисления с многократной точностью, выполняемые при помощи алгоритма 4.6.ЗА, показывают, что 3"' ' шобле = 1, пс — 1 = 2 2 19. 107.
353. пы п~ — — 13 191270754108 226049 301. Здесь 3"' ' шос1п~ ф 1, поэтому и, — не простое число. Продолжая выполнение алгоритма А или В, можно получить следующие множители: п~ — — 91813 п„пз —— 143675413657196977. Теперь 3"' ' шоб пз — — 1, поэтому можно попытаться доказать, что пз — простое число. Приняв во внимание, что множители ( 1000, получаем пг — 1=2 2 2 2 3 3 547 пз, где пз = 1824032775457.
Так как 3"' ' шобиз ф 1, приходим к заключению, что пз — -составное число, а при помощи алгоритма А находим, что пз — — 1103 пз, где пэ = 1 653 701519. Число пк ведет себя, как простое (т. е. 3"" ' шоб пэ — — 1), поэтому пз — 1 = 2 7 19 23.137 1973 Итак, выполнено первое полное разложение на простые множители.
Теперь мы готовы вернуться к предыдущей подзадаче, а именно †доказательству того,что пх так что есть основание предполагать, что пэ — простое число. Конечно, не может быть и речи о том, чтобы для проверки, является лв пс простым числом, проанализировать 10 миллионов миллионов или около того возможных делителей, но рассмотренный выше метод вполне пригоден для такой проверки. Следующая задача — разложение на простые множители числа пе — 1. Преодолев некоторые трудности, компьютер сообщит, что есть простое число.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
