AOP_Tom2 (1021737), страница 124
Текст из файла (страница 124)
35. Схема Рабина 'обладает важным свойством — найти квадратные корни по модулю Х, вероятно, так же трудно, как найти разложение на простые множители числа !у = рй. Если число х выбрать случайно, шансы на то, что при вычислении квадратного корня из х~ шоп !т' будет найдено значение р, такое, что выполняются условия х =р и хорху, причем ясд(х — ун Ю) = р или д, равны 50/50. Однако эта система имеет существенный изъян, который, похоже, отсутствует в ВБА-схеме (упр.
33). Каждый, кто обращается к бц11Т-блоку, может легко определить простые множители числа Х. Это не только допускает возможность жульничества со стороны нечестных служащих или угрозы вымогательства, но также позволяет выдать секрет чисел р и д. После этого нечестивцы могут утверждать, что их подпись на каком-то переданном документе была подделана.
Таким образом, ясно, что цель безопасной связи заключается в том, чтобы учесть тонкости проблем, совсем не похожих на те проблемы, с которыми приходится обычно сталкиваться при разработке и анализе алгоритмов. Исшорцнеская справка. В 1988 году появилось сообщение, что Клиффорд Кокс (С))його Сос1св) рассмотрел возможность кодирования сообщения посредством преобразования хм шод ру еще в 1973 году„но его работа засекречена. Самые большие нзвестные простые числа. В различных разделах этой книги было рассмотрено несколько вычислительных методов, использующих в процессе работы большие простые числа.
Описанные в данном разделе методы позволяют сравнительно легко находить простые числа, имеющие, скажем, не более 25 разрядов. В табл. 2 приведены 10 нанболыпих простых чисел, меньших, чем длина машинного става типового компьютера. (Другие полезные простые числа приводятся в упр, 3.2,1.2 — 22 и 4.6.4 — 57.) В действительности известны значительно ббльшне простые числа специального вида, а иногда бывает важно найти простые числа максимально возможной величины. Поэтому давайте завершим настоящий раздел исследованием интересного способа, которым были найдены наиболыпие из известных простых чисел.
Такие простые числа имеют вид 2" — 1 для различных частных значений п, и поэтому они особенно подходят для некоторых приложений на двоичных компьютерах. Число вида 2" — 1 не может быть простым, если не является простым число и, поскольку 2"' — 1 делится на 2' — 1. В 1644 году Марен Мерсенн (Мапл Мегэепце) удивил своих современников, заявив, что числа 2э — 1 являются простыми при р = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 и не являются таковыми ни при каких других р, меньших 257. (Это утверждение появилось в связи с рассуждениями Мерсенна о совершенных числах в предисловии к его Соййа~а РЬуэ1со-МасЛешабса. Любопытно, что он также сделал следующее примечание: "Какими бы известными на сегодня методами мы ни пользовались, для того чтобы определить, будет ли заданное 15- илн 20-значное число простым, не хватит целой жизни". Мерсенн, который в предыдущие годы часто переписывался с Ферма, Декартом и другими учеными по сходным вопросам, не привел никаких доказательств своих утверждений и в течение последующих 200 лет никто не знал, был ли он прав.
В 1772 году Эйлер после многолетних безуспешных попыток наконец доказал, что 2эз — 1 — простое число. Почти через 100 лет Э. Люка (Е. 1цсвв) установил, что 2щт — 1 — тоже простое число, а судьба числа 2э~ — 1 осталась под вопросом. Следовательно, Мерсенн был не совсем точен. Затем в 1883 году И. М. Первушин доказал, что 2э' — 1 — простое число [см. Историко-мат.исследования 6 (1953), 559], и это послужило поводом для подозрений, что Мерсенн допустил описку, записав 67 вместо 61.
В конце концов были обнаружены н другие ошибки в утвермсдениях Мерсенна; Р. Е. Пауэрс (В. Е. Рочегв) [АММ 18 (1911), 195] показал, что простым является число 2ээ -1, как уже предполагалн до него некоторые авторы; три года спустя он доказал, что число 2'ат-1 также является простым. В 1922 году М. Крайчик (М. КгайсЬЙ) обнаружил, что число 2ээ~ — 1 не леллетсл простым [см.
его Яесйегсйее эцг 1а ТЬеог1е с)еэ ЖотЬгеэ (Раг)э, 1924), 21]; в его вычисления, возможно, вкрались ошибки, но вывод оказался верным. В настоящее время числа вида 2г — 1 называются числами 7йергеяна н известно, что простые числа Мерсецна вычислены для следующего ряда значений р: 2, 3, 5, 7, 13, 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) Большая часть из значений в нижней строке получена Дэвидом Словинским (Паьйс! 8!он1пз)ц) и используется для тестирования новых суперкомпьютеров [см. З. ЙесгеаГюпа! МаГЬ. 11 (1979), 258- 261]; числа 756839,859 433 и 1 257 787 он получил вместе с Полем Гейджем (Рац! Саде) в 90-х годах. Тем не менее две наибольшие степени, 1398269 и 2976221, были получены Жоэлем Арменгодом (Лое! Агшепйацб) и Гордоном Спенсом (Согдоп Брепсе) на персональных компьютерах; для решения задачи они использовали программу, разработанную в 1996 году Георгом Вольтманом (Сеогйе %о1сшап), руководителем проекта Сгеа1 1псегпес Мегзеппе РНше БеагсЬ (С1МРБ).
Заметим, что простое число 8191 = 2'з — 1 в списке (26) отсутствует; Мерсенн утверждал, что 2 '~~ — 1 - простое число, и многие высказывали предположение, что любое простое число Мерсенна может быть использовано в качестве показателя степени. К проекту С1МР8 присоединилясь тысячи людей, и Скотт Куровский (Всогг Кпгоюз)о) с целью более систематизированного использования показателей степени разработал программное обеспечение для 1псегпес под названием Рг1гпеле1. Уже к февралю 1998 года, за год с небольшим после внедрения этого продукта в 1псегпес, активность.
связанная с поисками простых чисел Мерсенна, постоянно возрастала. Таким образом, следует ожидать существенного прогресса в поиске этих исторических чисел. После 1997 года найдены такие простые числа 2г — 1, р Автор Дата 3021377 Роланд Кларксон (Во!апг( С!аг!своп) 27 января 1998 года 6972593 Найан Хьяратвала (Кауап На!га1тга!а) 1 июня 1999 года Процесс поиска больших простых чисел до сих пор не систематизирован, потому что людям свойственно стремление устанавливать мировые рекорды, которые трудно побить, вместо того чтобы тратить время на поиск меньших значений показателей степеней. Например, в 1983 году было доказано, что 2'зэеэ" — 1 в простое число, в 1984 году, что 2мвеэг — 1 †так простое число,а число 2"еэез — 1 †н. Поэтому.
до сих пор может существовать одно или несколько неизвестных чисел Мерсенна, меньших 2з зевам — 1. (Под руководством Вольтмана к 26 мая 1997 года были проверены все показатели степени до ! ОООООО, и его добровольцами были последовательно заполнены все ранее незаполненные позиции.) Поскольку число 2звызз' — 1 содержит около 900000 десятичных разрядов, ясно, что для доказательства того факта, что числа подобного вида простые, был применен какой-то специальный метод.
(Действительно, предварительная проверка 12 апреля 1996 года числа 2' зачтет — 1 отняла менее 29845 с машинного времени (это примерно 8.3 ч) на компьютере Сгау Т94. Предварительная проверка числа 2 эгв ею — 1, выполненная в августе 1997 года на компьютере Репсшш РС 100 МНг, заняла 15 суток.) Впервые эффективный способ проверки, является ли число Мерсенна 2г — 1 простым, бьш предложен Э. Люка [Атег.,7. МаВь 1 (1878), 184 — 239, 289 — 321, особенно с. 316) и усовершенствован Д. Г. Лемером [Аппа1э оГ МазЬ. 31 (1930), 419-448, особенно с.
443). Этот способ проверки является частным случаем метода, применяемого в настоящее время для проверки принадлежности числа и к простым числам, когда известны множители числа п+ 1, и состоит в следующем. Теорема Ь. Пусть 9 — нечетное простое число и последоватсг»ьность (Ь„) задается правилом Ьв = 4 Ьи«! = (Ь~ — 2) !под (2» — 1). (27) Тогда число 2» — 1 будет простым тогда и только тогда„когда Л» з = О.
Например, 21 — 1 — простое число, поскольку Ьг —— (4' — 2) шо»(7 = О. Этот способ проверки особенно подходит для реализации на двоичных компьютерах изза простоты вычислений по модулю (2» — 1) (см. раздел 4.3.2). В упр. 4.3.2 — 14 изложен способ, позволяющий сэкономить время выполнения операций в случае очень больших чисел д.
Доказательство. Докажем теорему Ь, используя лишь самые простые принципы теории чисел, путем исследования некоторых свойств рекуррентных последовательностей, представляющих и самостоятельный интерес. Рассмотрим последовательности (Ьи) и (1г„), определяемые правилами Ьг„+! —— 4ӄ— Пи 1, Ъ'и. 1 — — 41ги — Ь"и !. П,=О, 10 У! = 1, 1:1 — — 4, (28) Докажем сейчас один вспомогательный результат, когда р — простое число н е > 1.
Если Ь'„= 0 (по модулю р'), то Ьг„г: — 0 (по модулю р'+'). (33) Этот результат следует из более общих соображений, изложенных в упр. 3.2.2-11, но для соотношений (28) можно привести и непосредственное доказательство. Предположим, что Уи = Ьр', Пи.«! = а. Согласно уравнению (32) и (28) имеем Ьзи = Ьр'(2а — 4Ьр')— : 2аби (по модулю р" «1), а Пзи, = 1Я«1 — Ь'з «в аз. Аналогично Пзи = Пзи«»Пи ЬзиП вЂ” 1 = За~Ь'„н Пз .«1 = Ьз .нП 1 — Пз П = аз.
В общем случае Ь«ьи = lса~ 'Ь»и и Ььи,.! = а (по модулю р'+'). Следовательно, взяв Ь = р, получим (33). Из формул (30) и (31), раскрывая (2 х з/3)и по биномиальной теореме, можно получить остальные выражения для Ьи и Ъ'„: ( " ) 2 -зь-!31 1г ~~, (" ) 2 -гь»~3~ (34) По индукции легко доказать справедливость следующих соотношений: )и — П -1-1 1'и-1! П = ((2 + з/3 )" — (2 — з/3 )" ) ( 1/Г2; 1'„=(2+ /3) +(2- /3)*'; Кн-«и ~~иПии-1 Ьт — 1Пи. (29) (30) (31) (32) Положив теперь и = р, где р — нечетное простое число, и воспользовавшись тем фактом, что Я) кратно р, кроме случая, когда )» = О или /с = р, приходим к выводу, что Уг = 31е '>~~, Ър эв 4 (по модулю р).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
