В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 11 Простые числа В следующих двух главах книги речь идет о криптографических системах с открытым ключом. К сожалению, изучение этого материала требует опре- деленного знания математики. Не секрет, что порой хочется пропустить по- дробные объяснения и ограничиться лишь уравнениями и формулами, но мы хорошо осознаем, что этого делать не следует. Чтобы использовать какой-ни- будь инструмент, вы должны понимать его свойства. Это очень легко, когда речь идет о чем-нибудь наподобие функции хэширования. У нас есть “идеаль- ная” модель функции хэширования, и мы требуем, чтобы реальная функция хэширования вела себя точно так же, как эта модель. Для систем с открытым ключом все гораздо сложнее. У нас нет идеальной модели криптографиче- ской системы с открытым ключом. На практике вам придется иметь дело с математическими свойствами подобных систем и, чтобы чувствовать себя уверенно, необходимо понимать эти свойства. Короткого пути здесь нет; вы должны понимать математику. Это не так сложно, как кажется; единствен- ное, что от вас требуется, — это знание школьной программы математики на уровне старших классов (а точнее, математики, которую изучали авторы этой книги, когда были в старших классах). Эта глава посвящена простым числам. Простые числа играют в матема- тике очень важную роль, но нас они интересуют только потому, что боль- шинство существующих криптосистем с открытым ключом основаны на при- менении простых чисел. 11.1 Делимость и простые числа Число a является делителем числа b (это записывается как a | b и читается “ a делит b ”), если b делится на a без остатка. Например, число 7 является делителем числа 35, поэтому можно записать, что 7 | 35 . Число называется 208 11.1. Делимость и простые числа 209 простым (prime) , если у него есть только два делителя: единица и само это число. Например, число 13 является простым, так как у него есть только два делителя: 1 и 13. Перечислить первые несколько простых чисел несложно — это 2, 3, 5, 7, 11, 13 и т.д. Любое число, большее единицы, которое не яв- ляется простым, называется составным (composite) . Число 1 не является ни простым, ни составным. В следующих главах книги используется терминология и обозначения, принятые в математике. Это намного облегчит чтение другой литературы по данному вопросу. Вначале математические обозначения могут показать- ся вам сложными и запутанными, но не стоит беспокоиться — этот раздел математики действительно очень прост. Ниже приведена простая лемма о делимости. Лемма 1. Если a | b и b | c , тогда a | c . Доказательство. Если a | b , тогда существует целое число s , такое, что as = b . (Действительно, если b делится на a , тогда оно должно быть крат- ным a .) Если b | c , тогда существует целое число t , такое, что bt = c . Но из этого следует, что c = bt = ( as ) t = a ( st ) , а значит, a является делителем c . (Чтобы понять ход последнего рассуждения, просто убедитесь в том, что каждый из знаков равенства использован корректно. Логическое умозаклю- чение состоит в том, что первый элемент c должен быть равен последнему элементу a ( st ) .) ¤ Лемма является констатацией факта. Доказательство объясняет, почему эта лемма верна. Маленький квадратик справа обозначает конец доказатель- ства. Математики вообще любят использовать всевозможные символы 1 . Это очень простая лемма, и доказательство должно быть понятно всем, кто пом- нит, что означает запись a | b . Простые числа исследовались математиками еще тысячи лет назад. Даже сегодня, если требуется определить все простые числа до миллиона, мы ис- пользуем алгоритм, разработанный более 2000 лет назад Эратосфеном, дру- гом Архимеда. (Эратосфен также был первым человеком, измерившим точ- ный диаметр Земли. Спустя 1700 лет Колумб будто бы использовал намного меньшую — и неверную — оценку диаметра земного шара, когда собирался достичь Индии западным путем.) Евклид, еще один великий древнегреческий математик, привел гениальное доказательство того, что количество простых чисел бесконечно. Это доказательство настолько замечательно, что мы ре- шили включить его в нашу книгу. Оно поможет быстро вернуть ваши мысли в лоно математики. 1 Использование символов имеет свои преимущества и недостатки. Мы будем применять их только тогда, когда посчитаем, что это нужно для данной книги. |