Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Приложение B
Основная алгоритмическая теория чисел Для криптографических конструкций, приведенных в этой книге, чтобы быть эффективными (т.е., действовать в течение времени, являющимся полиномами длин их входов), необходимо чтобы эти конструкции использовали эффектив- ные (т.е. полиномиально-временные) алгоритмы для выполнения основных теоретико-числовых операций. Хотя в некоторых случаях существуют «три- виальные» алгоритмы, которые будут работать, все же целесообразно внима- тельно рассмотреть их эффективность, поскольку для криптографических при- ложений нередко используются целые числа длиной тысячи битов. В других случаях получение какого-либо полиномиально-временного алгоритма требует немного сообразительности, а анализ их эффективности может опираться на нетривиальные теоретико-групповые результаты. В приложении B.1 мы опишем основные алгоритмы для целочисленной арифметики. Здесь мы рассмотрим знакомые алгоритмы для сложения, вычи- тания и т.д., а также алгоритм Эвклида для вычисления наибольших общих де- лителей. Мы также обсудим расширенный алгоритм Эвклида, предполагая, что читатель ознакомился с материалом в разделе 8.1.1. В приложении B.2 мы покажем различные алгоритмы для арифметических опе- раций с абсолютными значениями чисел. В дополнение к краткому обсуждению основных операций по модулю (т.е. модульной редукции, сложения, умножения и инверсии), мы опишем умножение Монтгомери, которое может существенно упро- стить (и ускорить) реализацию операций модульной арифметики. Затем мы обсудим алгоритмы для проблем, которые менее распространены за пределами области крип- тографии: возведение в степень по модулю N (а также в произвольных группах) и выбор равномерного элемента из ZN or ZN* (или в произвольной группе). Этот раз- дел предполагает знакомство с основами теории групп, рассмотренных в разделе 8.1. Указанный выше материал, неявно используется во второй половине книги, несмотря на то, что абсолютной необходимости читать этот материал, чтобы следовать книге, нет. (В частности, читатель, готовый принять результаты этого приложения без доказательства, может просто прочитать краткое изложение этих результатов в теоремах, изложенных ниже). Приложение B.3, в котором обсужда- ется поиск генераторов в циклических группах (когда факторизация группового порядка известна) и предполагает результаты раздела 8.3.1, содержит материал, 320 который вряд ли вообще используется; он включен для полноты и ссылок. Поскольку наша цель состоит в том, чтобы установить, что определенные про- блемы могут быть решены в течение полиномиального времени, мы сделали выбор в пользу простоты, а не эффективности алгоритмов и их описаний (до тех пор, пока алгоритмы работают в течение полиномиального времени). По этой причине мы вообще не интересуемся точным временем работы алгоритмов, мы представляем, что после установления они действительно работают в течение полиномиального времени. Читатель, который серьезно заинтересован в реализации этих алгоритмов, предупрежден, что необходимо искать другие источники для более эффективных альтернатив, а также различные методы для ускорения необходимых вычислений. Результаты этого приложения обобщены теоремами, которые приведены далее. Мы везде предполагаем, что любое целое a, представленное в качестве входных данных, записывается с использованием именно «a» битов; т.е. бит высокого порядка равный 1. В приложении B.1 мы покажем: жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|