Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 16
Текст из файла (страница 16)
17. 19, 31., 61, 89. 107., 127, 521, 607, 1 279, 2 203, 2 281, 3 217, 4 253, 4 423, 9 689, 9 941, 11 213, 19 937, 21 701, 23 209, 44 497, 86 243, 110 503, 132 049, 216 091, 756 839, 859 433. 1 257 787, 1 398 269, 2 976 221. (26) Волыпая часть из значений в нижней строке получена Дэвидом Словинским (ЭатЫ 81ов!пзЫ) и используется для тестирования новых суперкомпьютеров (см, Х Несгеа!!опа! Май.
11 (1979), 258-261]; числа 756 839, 859433 и 1 257 787 он получил вместе с Полем Гейджем (Раи! Сайе) в 90-х годах. Тем не менее две наибольшие степени, 1398269 и 2976221, были получены Жоэлем Арменгодом (3ое! Агшепбаи<1) и Гордоном Спенсом (Согбен Брепсе) на персональных компьютерах; для решения задачи онн испачьзовали программу, разработанную в 1996 году Георгом Вельтманом (Сеогйе Жо!мпап), руководителем проекта Сгеа! 1пгегпес Мегвеппе Рппн Беата (С1МРЯ), Заметим, что простое число 8191 = 2'з — 1 в списке (26) отсутствует; Мерсенн утверждал, что 2е 'э' — 1 — простое число, и многие высказывали предположение, что любое простое число Мерсенна может быть использовано в качестве показателя степени.
К проекту С1МР8 присоединились тысячи людей, и Скотт Куровский (ЯсоФФ Киготгз)и) с целью более систематизированного использования показателей степени разработал программное обеспечение для 1пгегпе! под названием РгцпеХек Уже к февралю 1998 года, за год с небольшим после внедрения этого продукта в 1пгегпес, активность, связанная с поисками простых чисел Мерсенна, постоянно возрастала. Таким образом., следует ожидать существенного прогресса в поиске этих исторических чисел.
После 1997 года найдены такие простые числа 2" — 1. р Автор Дата 3021377 Роланд Кларксон (Но!аш! С!агкзоп) 27 января 1998 пща 6972593 Найан Хьяратвала (Хауап На)та!па!а) 1 июня 1999 года Процесс поиска больших простых чисел до снх пор не систематизирован, потому что людям свойственно стремление устанавливать мировые рекорды, которые трудно побить, вместо того чтобы тратить время на поиск меньших значений показателей степеней. Напрямер, в 1983 голу было доказано, что 2'ззегэ — 1 — простое число, в 1984 году, что 2ыеев' — 1 — также простое число, а число 2мезез — 1 — нет.
Поэтому до сих пор может существовать одно или несколько неизвестных чисел Мерсенна, меньших 2" эге зы — 1. (Под руководством Вольтмана к 26 мая 1997 года бьши проверены все показатели степени до 1000000, и его добровольцами были последовательно заполнены все ранее незаполненные позиции.) Поскольку число 2зэшгм — 1 содержит около 900000 десятичных разрядов, ясно, что для доказательства того факта, что числа подобного вида простые, был применен какой-то специальный метод. (Действительно, предварительная проверка 12 апреля 1996 года числа 2' '-'~тхет — 1 отняла менее 2984о с машинного времени (это примерно 8.3 ч) на компьютере Сгау Т94. Предварительная проверка числа 2~эгв гн — 1, выполненная в августе 1997 года на компьютере Репс!иш РС 100 МНх, заняла 15 суток.) Впервые эффективный способ проверки, является лп число Мерсенна 2" — 1 простым, был предложен Э.
Люка [Ашег. Х Май. 1 (1878), 184 — 239, Положив теперь и = р, где р — нечетное простое число, и воспользовавшись тем фактом, что (~) кратно р, кроме случая, когда 1» = О или и = р, приходим к выводу, что уг эз 3(г 07», $р»л 4 (по модулю р). (Зб) При р г- 3 по теореме Ферма имеем Зг ~ эз 1; следовательно, (З~" О/з — 1) х (З~г О'г + 1)»л 0 и З~г 07» ээ Ы. Если Ур ы -1, то Ур+1 - -4Ур — Ур 1 м 4Ур + Ър — Ур+, »л -П ~,, отсюда У».,1 шеар м О. Если Ур эз +1, то Ур г 4Уг — Уз+1 = 4Ур — Ър — Ур 1 эз -(ур „значит, 6 1 шар = О.
Таким образом доказано, что для каждого простого р существует целое число г(р), такое, что (Зб) Уг+ оо шос) р = О, Цр)) < 1. Далее, если д." — пронзво н,ное положительное целое число и если т = гп(Х)— такое наименьшее положительное целое чисчо. что У„,~вО п1об д' = О, то У„тодХ = О тогда и только т ла.
когда и кратно пг(Ю). (37) (Это число»п(Х) называется рангом появления в последовательности числа 7» .) Для доказательства (37) учтем, что последовательность К„, У„,+м У„,+з,... конгруэнтна (по модулю У) последователыюсти аП», аУ~, аУ», ..., где число а = У +1 пюб Ю взаимно просто с Ю, так как Зсб(У„, У„+,) = 1. После всех этих приготовлений докажем теорему 1.. В силу соотношения (27) по ицлукции имеем Ь„= 1'з шод(2» — 1). (38) Далее, кэ тождества 2У„+1 = 4У„+ 1' следует, что Зсо(с'„,$'„) < 2, поскольку всякий общий делитель чисел У„н Ъ'„должен делить Г„и 2П чм в то время как 6'„Л.
У вм Поэтому У„н 1'„не имеют общих нечетных множителей, и, если А» з = О, должно выполняться ба-1 = Уяя-грэя-з лт О (по модулю 2» — 1), Уг,-г ф 0 (по молущю 2» — 1). Затем, если гп = »п(2» — 1) — ранг появления числа 2» — 1, то оно должно быть делителем числа 2» ', ио не числа 2» "; таким образом, т = 2» 1. Докажем теперь, учитывая сказанное выше, что число и = 2» — 1 должно быть простым. Предполбжим, что разложение числа и на простые множители имеет вид р~'... р'„".
Все простые числа р» больше 3, так что число и нечетно и конгруэнтно (-1)»-1 = -2 (по модулю 3). Из (33), (Зб) и (37) следует, что Ц ы 0 (~о модулю 2» — 1), где г =)сш(р~~' '(р1+»~),...,р' '(р„+г„)), и каждое гу равно Ы. Отсюда получаем, что 1 кратно т = 2» '. Пусть пе = Пу=зУ~" '(ру+гз)'тогдане < Ц; ар»» '(р;+-'р,) =(э)"н. Крометого,поскольку рз +»1 — четное число, то 1 < пе/2' ', ибо всякий раз„когда берется наименьшее общее кратное двух четных чисел, множитель 2 теряется. Объединяя эти результаты, получаем гл < г: 2(г)'и < 4(~)"гп < Згп; отсюда, т < 2 и 1 = »и ьли г = 2»п, т. е.
г равно степени 2. Поэтому с, = 1, с„= 1 и, если и — не простое число, должно быть и = 2» — 1 = (2" + 1)(2' — 1), где 2» + 1 н 2' — 1 — простые числа. Последнее разложение прн нечетном д невозможно, поэтому и — простое. Обратно, предположим, что и = 2е — 1 — простое число. Необходимо показать, что 1т -е ат 0 (по модулю и). Для этого достаточно доказать, что гш-~ ьз -2 (по мсдулю и), поскольку (гш-~ = (1ш-е)т — 2. Но Ъ~ -~ = ((1/2+ ъ/б)/2)"+ + ((Л- Л)/2) ш2--~ ("") 2""-'"„6'" ш21 --Мт~-("") 3.
Так как и — нечетное простое число, биномиальный коэффициент ( 25 ) (25) + (25 -1) делится на и за исключением случая, когда 2)с = О и 25 = и + 1, Следовательно, 21" ю/т)т,- гн 1+ 31"+и/з (по модулю и). Здесь 2 гя (21е+цгт)т, поэтому согласно теореме Ферма 21 -г1/т = (21е+~Ут)( -ц р21, В итоге в силу одного простого случая закона взаимности квадратичных вычетов (упр. 23) 31" Пут эх -1, поскольку и лия)3 = 1 и и шоб 4 = 3. Это означает, что ьз -2 и, следовательно, должно быть $Гт,-з = О, что и требуется. $ В 1460 году анонимный автор, работы которого в настоящее время хранятся в итальянских библиотеках, открыл, что числа 2'т — 1 и 2'е — 1 являются простыми [см.
Е. Р!сцЩ Н1ясог1а Маей. 16 (1989), 123-136). С тех пор наибольшими из известных простых чисел почти всегда оказываются числа Мерсенна. Но положение может измениться, поскольку находить простые числа Ъ(ерсенна становится все труднее, н поэтому в упр. 27 представлен эффективный способ проверки чисел другого вида.
УПРАЖНЕНИЯ 1. [10) Если последовательность пробных делителей в алгоритме А 5е, А, Им ... содержат число, не являющееся простым, то почему оно никогда не появится на выходе7 2. [15) Можно ли исключить из алгоритма А шаг А2, если известно, что исходное число 1У для алгоритма А не меньше 37 $. [МРО) Покажите, что существует число Р со следующим свойством: если 1 000 < и < 1 000 000, то число я будет простым тогда и только тогда, когда йсб(п, Р) = 1. 4.
[Мйр[ Используя обозначения упр. 3.1-7 и раздела 1.2.11.3, докажите, что среднее значение наименьших и, таких, что Х„= Хпю „находится в яитервапе между 1.5Ц(гл) — 0.5 и 1:5254)(ш) — 0.5. 5. [21) При помощи метода Ферма (алгоритм 11) нейдите вручную множители числа 11 1П по модулам 3, 5, 7, 8 н 11. О. [М24) Докажите, что если р — нечетное простое число и 17 не кратно числу р, то количество целых чисел х, принадлежащих интервалу 0 < я < р, для которых существует решение р уравнения х" — М ш р~ (по модулю р), равно (р ш 1)/2, 7. [25] Проанализируйте задачи программирования метода решета — алгоритм 1Э вЂ” дли двоичного компьютера в случае, когда табличные значения для модулей ни заполняют не точно целое число слов памяти. 6. [23] (Решето Зрашопбсна, 3 в, до н. э.) Следующая процедура позволяет найти все нечетные простые числа, меньшие данного целого числа Х, поскольку она, удаляет все непростые числа.
Выполнение процедуры начинаегся с того, что для всех нечетных целых чисел от 1 до дг последовательно вычеркиваются числа рэ, рь(рь + 2), рь(рь + 4), ..., кратные к-му простому числу рь при й = 2, 3, 4, ..., пока не будет найдено такое простое число рю для которого р~ь > )т'. Покажите, как превратить описанную процедуру в алгоритм, пригодный для прямой реализации в компьютере, беэ использования операций умножения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
