Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 15
Текст из файла (страница 15)
Если предположить, что закуплено 10 млрд компьютеров и все они задействованы в решении этой проблемы, пройдет более 31 гола, прежде чем одни из них разложит число У на простые множятели. Но пока правительство будет закупать твк много специализированных компьютеров, люди начнут применять 300-разрядные числа Ю. Поскольку метод кодирования х н хэ щи Х известен, он обладает еще и дополнительными достоинствами, помимо того факта, что расшифровать код можно только при помощи ВЯА-блока. Такие системы "общедоступных ключей" были впервые рассмотрены В. Диффи (%'.
П!йе) и 31. Э, Хеллмаиом (М. Е. Не!)пшп) и журнале 1ЕЕЕ 2гапэ. 1Т-22 (1926), 644-654. Как пример того, что можно сделать, когда метод кодирования широко известен, предположим, что Алиса желает связаться с Бобом па электронной почте и при этом они оба хотят, чтобы их письма былп подписаны так, чтобы получатели были уверены, что никто не подделывает сообщение. Пусть Ел(М) — кодирующая функция для сообщений М, направляемых Алисе, а Вл(М) — декодирующая функция НЯА-блока, установленного у Алисы, Пусть твк- же Ев(М), Пв(М) — соответственно кодирующая и декодирующая функции ВБА- блока, принадлежащего Бобу. Тогда Алиса может отослать подписанное сообщение.
поставив свою подпись и дату, а затем переслать Бобу сообщение Ев(ЛЗл(М)), использовав для вычисления Пл(М) свой компьютер. Когда сообщение получает Боб, его ВБА-блок преобразует это сообщение в сообщение Пл(М): Бобу известно Ел, так что он может вычислить ЛХ = Ел (Л14(ЛХ)). Это должно убедить его, что сообщение поступило именно от Алисы; никто другой не мог отослать сообщение с кодом Юл (ЛХ).
(Ну хорошо, теперь Бобу известен и код ЛЗл (М), поэтому оп, посылая сообщение Ех(Рл(М)) Ксавьеру, может представлять Алису, Чтобы защититься от таких попьпок подделки, в содержимом кода М должно быть четко указано, что оно предназначено только для Боба.) Естественно задать вопрос, каким образом Алиса и Боб узнают коднрующие функции Ел и Ев друг друга? Простого хранения этих функций в общедоступном файле явно недостаточно, поскольку некто Чарли может проникнуть в этот файл, подставив вычисленный им код Х.
Затем Чарли получит возможность тайно перехватывать и декодировать чужие сообщения до того, как Алиса или Боб чтонибудь заподозрят. Выход из этой ситуации заключается в том, чтобы хранить такие произведения Юл и Хв в специальном общедоступном каталоге, который имеет собственный ВЯА-блок и широко известное произведение Хо. Когда Алиса пожелает узнать, как связаться с Бобом, она запросит в этом каталоге произведение для Боба; компьютер, управляющий каталогом, отправит ей подписанное сообщение, выдав значение Хв.
Такое сообщение должно быть легитимным, поскольку подделать его никто не сможет. Интересную альтернативу ВЯА-схеме предложил Майкл Рабин (М)сЬае1 ВвЪ1п). В работе, опубликованной в М1Т БаЪ. (ог Сошр. Бс!., герогс ТВ-212 (1979), он описал способ кодирования функцией хэ шо4 Х вместо функции хз шоб У, В этом случае механизм декодирования, который можно было бы назвать ЗЯВТ-блоком, возвращает четыре различных сообщения; суть в том, что четьгре различных сообщения содержат один н тот же квадрат по модулю Х, а именно — х, -х, УхшобЮ н (-ух) шод Х, где у = (рт ' — д" ~) пик1У. Если условиться на будущее, что х — четное число нли что х < -'Х„то двусмысленность коснется двух сообщений, из которых предпсшожительно только одно имеет смысл.
Эта двусмысленность может быть легко устранена, как показано в упр, 35. Схема Рабина 'обладает важным свойством — найти квадратные корни по модулю Х, вероятно, так же трудно, как найти разложение на простые множители числа Ю = рд. Если число х выбрать случайно, шансы на то, что прп вычисленнп квадратного корня из хл щи ЛГ будет найдено значение р, такое, что выполняются условия хзщрз и х~~р, причем ясб(х — р, Ю) = р илн д, равны 50150. Однако эта система имеет существенный изъян, который, похоже, отсутствует в ВЯА-схеме (упр. ЗЗ).
Каждый, кто обращается к Яс)ВТ-блоку, может легко определить простые множители числа Ю. Это не только допускает возможность жульничества со стороны нечестных служащих нлн угрозы вымогательства, но также позволяет выдать секрет чисел р и о. После этого нечестивцы могут утверждать, что их подпись на каком-то переданном документе была подделана. Таким образом, ясно, что цель безопасной связи заключается в том, чтобы учесть тонкости проблем, совсем не похожих на те проблемы, с которыми приходится обычно сталкиваться при разработке и анализе алгоритмов. Испюрпческал справка.
В 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.
(Это утвернгдение появилось в связи с рассуждениями Мерсенна о совершенных числах в предисловии к его Соййаса РЬув!со-МагЬетабса. Любопытно, что он также сделал следующее примечание: "Какими бы известными на сегодня методами мы ни пользовались, для того чтобы определить, будет ли заданное 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 ие яеляегпся простым [см, его Весйегсйез зцг!а ТЬ4опе дев Ь7отЬгеэ (Раг(в, 1924), 21]; в его вычисления, возможно, вкрались ошибки, но вывод оказался верным. Таблица 2 ПОЛЕЗНЫЕ ПРОСТЫЕ ЧИСЛА Десать наибольших иростых чисел, мсньаизх, чвзз Ф, суть К- 01, ..., 14"- 010. Ф 216 Взе 233 216 216 230 гз! 233 гзз 234 гзз 236 231 236 гве 230 гвз 233 гзз гзе 236 гзе 231 236 240 241 243 243 244 246 246 241 246 236 2вв 2 264 106 1О" Ив 1О' 1010 1О" изв 1016 01 19 1$ 1 5 1 з 9 з 15 3 39 5 39 бт з Зб 1 б 9 41 31 5 25 45 7 вт 21 П 57 17 бб 21 пб 59 55 9З 25 59 17 9 11 63 зз 2З П бз 49 17 9 П 19 5 19 17 21 17 49 гт 79 89 33 41 19 17 25 77 49 17 З1 87 19 167 З1 17 67 П7 69 5Т 127 65 99 ют 165 вз 21 27 29 71 57 5З Зв ЗЗ аз 51 Зв 1З 17 27 17 21 27 27 зз 61 45 П1 95 43 83 61 65 49 ПЗ 61 23 45 107 67 195 $$ зз П7 П9 81 6З 147 89 225 173 259 95 39 29 41 107 71 57 41 пз 55 57 31 2З З1 27 55 зз 37 63 85 вт Пб П9 63 101 69 99 79 131 69 65 69 131 91 203 63 53 175 129 93 тт 279 93 427 179 ЗО1 179 41 57 59 Пт П9 93 63 149 61 87 49 зз 45 69 61 57 61 75 91 101 1З$ 125 73 1ОЗ 85 1от 105 143 79 Пт из ИЗ 135 213 ТЗ 65 255 143 121 167 297 147 617 257 зтб 189 47 бз 69 2ОЗ 149 129 101 из 75 89 61 зб 5Т 69 69 87 69 77 пб 107 18т 143 7$ ют 99 1ЗЗ гвб 165 121 137 141 1В5 165 235 75 143 267 149 1ЗЗ 197 ЗЗ9 иб 607 279 звт 257 69 69 из 239 167 149 из 191 61 99 бз 41 67 129 Юб 1ОЗ 1ЗЗ Во 141 П1 199 165 9З 135 иб 153 301 18$ 141 159 199 191 219 293 91 161 291 287 1З9 237 435 189 649 369 391 279 ЗЗ 71 161 243 183 167 1зт 329 Пб ПЗ 85 65 69 143 П1 пз 14Т 9$ 1$9 П7 219 1ВЗ 99 из 151 185 зоз 207 247 173 201 227 2З1 299 1П 16$ 309 згт 159 гвт 541 2ЗЗ 667 Звб 409 Згв 93 93 173 249 21З 171 143 357 121 пт 91 75 85 1$3 121 П7 157 П7 16$ 12$ гз1 213 121 161 159 209 321 227 ЖЕ 189 351 2З1 241 389 133 21$ 319 359 из зоб 619 243 861 З99 407 Збз П7 99 179 261 219 179 1$З 3$9 аьз 135 из 99 9З 87 185 129 123 И9 167 183 135 гзб гтз 133 гз 1т1 267 Збб 281 325 2ЗЗ 375 2$7 301 437 139 227 369 зтт 229 зп 649 2$7 втг 45З 471 363 137 П1 213 гбт 2З1 231 233 369 В настоящее время числа вида 2г-1 называются числами Мерсениа и известно, что простые числа Мерсенна вычислены для следующего ряда значений йл 2, 3, 5, 7, 13.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
