нечестивцы могут утверждать, что их подпись на каком-то переданном документе была подделана. Таким образом, ясно, что цель безопасной связи заключается в том, чтобы учесть тонкости проблем, совсем не похожих на те проблемы, с которыми приходится обычно сталкиваться при разработке и анализе алгоритмов.

Историческая справка. В 1988 году появилось сообщение, что Клиффорд Кокс (Clifford Cocks) рассмотрел возможность кодирования сообщения посредством преобразования modpq еще в 1973 году, но его работа засекречена.

Самые большие известные простые числа. В различных разделах этой книги было рассмотрено несколько вычислительных методов, использующих в процессе работы большие простые числа. Описанные в данном разделе методы позволяют сравнительно легко находить простые числа, имеющие, скажем, не более 25 разрядов. В табл. 2 приведены 10 наибольших простых чисел, меньших, чем длина машинного слова типового компьютера. (Другие полезные простые числа приводятся в упр. 3.2.1.2-22 и 4.6.4-57.)

В действительности известны значительно большие простые числа специального вида, а иногда бывает важно найти простые числа максимально возможной величины. Поэтому давайте завершим настоящий раздел исследованием интересного способа, которым были найдены наибольшие из известных простых чисел. Такие простые числа имеют вид 2" - 1 для различных частных значений п, и поэтому они особенно подходят для некоторых приложений на двоичных компьютерах.

Число вида 2" - 1 не может быть простым, если не является простым число п, поскольку 2"" - 1 делится на 2" - 1. В 1644 году Марен Мерсенн (Marin Mersenne) удивил своих современников, заявив, что числа 2-1 являются простыми при р = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 и не являются таковыми ни при каких других р, меньших 257. (Это утверждение появилось в связи с рассуждениями Мерсенна о совершенных числах в предисловии к его Cogitata Physico-Mathematica. Любопытно, что он также сделал следующее примечание: "Какими бы известными на сегодня методами мы ни пользовались, для того чтобы определить, будет ли заданное 15- или 20-значное число простым, не хватит целой жизни". Мерсенн, который в предыдущие годы часто переписывался с Ферма, Декартом и другими учеными по сходным вопросам, не привел никаких доказательств своих утверждений и в течение последующих 200 лет никто не знал, был ли он прав. В 1772 году Эйлер после многолетних безуспешных попыток наконец доказал, что 2 - 1 - простое число. Почти через 100 лет Э. Люка (Ё. Lucas) установил, что 227-i - тоже простое число, а судьба числа 2® - 1 осталась под вопросом. Следовательно, Мерсенн был не совсем точен. Затем в 1883 году И. М. Первушин доказал, что 2® - 1 - простое число [см. Ясторико-мат.исследования 6 (1953), 559], и это послужило поводом для подозрений, что Мерсенн допустил описку, записав 67 вместо 61. В конце концов были обнаружены и другие ошибки в утверждениях Мерсенна; Р. Е. Пауэре (R. Е. Powers) [АММ 18 (1911), 195] показал, что простым является число 2*-l, как уже предполагали до него некоторые авторы; три года спустя он доказал, что число 2°-1 также является простым. В 1922 году М. Крайчик (М. Kraitchik) обнаружил, что число 2 -1 ме является простым [см. его Recherches sur la Theorie des Nombres (Paris, 1924), 21]; в его вычисления, возможно, вкрались ошибки, но вывод оказался верным.

Таблица 2

ПОЛЕЗНЫЕ ПРОСТЫЕ ЧИСЛА

в настоящее время числа вида 2 - 1 называются числами Мерсенна и известно, что простые числа Мерсенна вычислены для следзющего ряда значений р:

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)

Большая часть из значений в нижней строке получена Дэвидом Словинским (David Slowinski) и используется для тестирования новых суперкомпьютеров [см. J. Recreational Math. 11 (1979), 258-261]; числа 756 839,859433 и 1257 787 он получил вместе с Полем Гейджем (Paul Gage) в 90-х годах. Тем не менее две наибольшие степени, 1398 269 и 2 976221, были получены Жоэлем Арменгодом (Joel Armengaud) и Гордоном Спенсом (Gordon Spence) на персональных компьютерах; для решения задачи они использовали программу, разработанную в 1996 году Георгом Вольтма-ном (George Woltman), руководителем проекта Great Internet Mersenne Prime Search (GIMPS). Заметим, что простое число 8191 = 2 - 1 в списке (26) отсутствует; Мерсенн утверждал, что 2 - 1 - простое число, и многие высказывали предположение, что любое простое число Мерсенна может быть использовано в качестве показателя степени.

К проекту GIMPS присоединились тысячи людей, и Скотт Куровский (Scott Kurowski) с целью более систематизированного использования показателей степени разработал программное обеспечение для Internet под названием PrimeNet. Уже к февралю 1998 года, за год с небольшим после внедрения этого продукта в Internet, активность, связанная с поисками простых чисел Мерсенна, постоянно возрастала.

Таким образом, следует ожидать существенного прогресса в поиске этих исторических чисел.

После 1997 года найдены такие простые числа 2** - 1.

р Автор Дата

3021377 Роланд Кларксон (Roland Clarkson) 27 января 1998 года 6972593 Найан Хьяратвала (Nayan Hajratwala) 1 июня 1999 года

Процесс поиска больших простых чисел до сих пор не систематизирован, потому что людям свойственно стремление устанавливать мировые рекорды, которые трудно побить, вместо того чтобы тратить время на поиск меньших значений показателей степеней. Например, в 1983 году было доказано, что 22 049 - простое число, в 1984 году, что 2"° - 1 - также простое число, а число 2°° - 1-нет. Поэтому до сих пор может существовать одно или несколько неизвестных чисел Мерсенна, меньших 22 9®22i j {Под руководством Вольтмана к 26 мая 1997 года были проверены все показатели степени до 1000 000, и его добровольцами были последовательно заполнены все ранее незаполненные позиции.)

Поскольку число 22®22l содержит около 900000 десятичных разрядов, ясно, что для доказательства того факта, что числа подобного вида простые, был применен какой-то специальный метод. (Действительно, предварительная проверка 12 апреля 1996 года числа 2 - 1 отняла менее 29845 с машинного времени (это примерно 8.3 ч) на компьютере Cray Т94. Предварительная проверка числа 22 976 221 - выполненная в августе 1997 года на компьютере Pentium PC 100 MHz, заняла 15 суток.) Впервые эффективный способ проверки, является ли число Мерсенна 2-1 простым, был предложен Э. Люка [Amer. J. Math. 1 (1878), 184-239,