В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 11. Простые числа Теперь необходимо познакомиться с понятием группы (group) — еще одним математическим термином, но на сей раз совсем простым. Группа — это мно- жество чисел, для которых определена одна операция, например сложение или умножение 2 . Сумма двух элементов группы должна равняться третьему элементу этой же группы. В группе, для которой определена операция умно- жения, не может находиться число 0. (Во-первых, умножать на 0 не очень-то интересно, а во-вторых, делить на 0 нельзя.) Тем не менее числа 1 , . . . , p − 1 вместе с операцией умножения по модулю p образуют группу. Эта группа называется мультипликативной группой по модулю p (multiplicative group modulo p) и обозначается по-разному; мы будем использовать обозначение Z ∗ p . Конечное поле состоит из двух групп: аддитивной (группы сложения) и мультипликативной. Таким образом, конечное поле Z p состоит из адди- тивной группы, определенной с помощью операции сложения по модулю p , и мультипликативной группы Z ∗ p . Группа может включать в себя подгруппу (subgroup) . Подгруппа содер- жит несколько элементов группы. Если применить операцию группы к двум элементам подгруппы, мы должны снова получить элемент подгруппы. На первый взгляд это звучит довольно сложно, поэтому рассмотрим небольшой пример. Числа по модулю 8 вместе с операцией сложения (по модулю 8) обра- зуют группу. Числа { 0 , 2 , 4 , 6 } образуют подгруппу. Сложив два любых числа этой подгруппы по модулю 8, мы снова получим элемент этой же подгруп- пы. Аналогичное утверждение справедливо и для мультипликативных групп. Мультипликативная группа по модулю 7 состоит из чисел 1 , . . . , 6 и операции умножения по модулю 7. Множество { 1 , 6 } образует подгруппу, как, впрочем, и множество { 1 , 2 , 4 } . Попробуйте перемножить два любых элемента одной и той же подгруппы по модулю 7, и вы сами убедитесь в том, что получите элемент этой же подгруппы. Подгруппы применяются для ускорения некоторых криптографических операций. Они также часто используются злоумышленниками для нападения на системы. Вот почему понятие подгруппы так важно для нас. До сих пор речь шла только о сложении, вычитании и умножении по модулю p . Чтобы полностью определить мультипликативную группу, нужно ввести операцию, обратную умножению, т.е. деление. Оказывается, что мы можем определить и операцию деления по модулю p . Самое простое опреде- ление этой операции выглядит следующим образом: a/b (mod p ) — это такое число c , что c · b = a (mod p ) . Делить на 0 нельзя, но оказывается, что выра- жение a/b (mod p ) определено для всех чисел при b 6 = 0 . 2 В действительности к группе выдвигается еще несколько требований, но все группы, о которых идет речь в этой книге, им соответствуют. 11.3. Арифметика по модулю простого числа 217 Как же вычислить частное двух чисел по модулю p на практике? Объяс- нение того, как это делается, займет несколько страниц. А для начала вновь вернемся на 2000 лет назад — к Евклиду и его алгоритму поиска наибольшего общего делителя. 11.3.4 Алгоритм поиска НОД Еще раз вернемся к курсу математики старших классов: наибольшим об- щим делителем (greatest common divisor — GCD) , или НОД , двух чисел a и b называют наибольшее число k , такое, что k | a и k | b . Другими словами, НОД ( a, b ) — это самое большое число, которое делит и a и b . Алгоритм вычисления НОД двух чисел, который мы используем сегодня, был разработан еще Евклидом. Более подробное описание этого алгоритма содержится в книге Дональда Кнута [54]. функция GCD вход: a Положительное число. b Положительное число. выход: k Наибольший общий делитель a и b . assert a ≥ 0 ∧ b ≥ 0 while a 6 = 0 do ( a, b ) ← ( b mod a, a ) od return b Почему этот алгоритм приводит к нужному результату? Вначале пока- жем, что операция присвоения, используемая в цикле, не изменяет множе- ство общих делителей чисел a и b . Действительно, ( b mod a ) — это всего лишь b − sa для некоторого целого числа s . Любое число k , которое делит a и b , бу- дет также делить a и ( b mod a ) . (Между прочим, обратное утверждение тоже верно.) А когда a = 0 , b будет общим делителем чисел a и b , причем наиболь- шим делителем. Можете сами убедиться в том, что цикл рано или поздно придет к завершению, потому что значения a и b все время уменьшаются, пока одно из них не достигнет нуля. В качестве примера подсчитаем НОД чисел 21 и 30. Начнем с пары ( a, b ) = (21 , 30) . На первой итерации мы вычисляем (30 mod 21) = 9 , а значит, получа- ем ( a, b ) = (9 , 21) . На второй итерации вычисляем (21 mod 9) = 3 и получаем ( a, b ) = (3 , 9) . И наконец, на последней итерации вычисляем (9 mod 3) = 0 и получаем ( a, b ) = (0 , 3) . Алгоритм возвращает число 3, которое действи- тельно является наибольшим общим делителем чисел 21 и 30. У НОД есть еще один “родственник”: наименьшее общее кратное (least common multiple — LCM) , или НОК . Наименьшее общее кратное чисел a и b — |