В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 11. Простые числа по модулю используются слишком часто, а математики довольно ленивы, су- ществует еще несколько общепринятых способов обозначения. Зачастую все выражение записывается без каких-либо символов модуля, и только в са- мом конце выражения добавляется оператор (mod p ) , чтобы напомнить, что все действия в этом выражении выполняются по модулю p . Более того, ес- ли смысл выражения понятен из контекста, оператор (mod p ) могут вообще опустить, и тогда вам придется постоянно помнить о том, что все вычисления следует выполнять по модулю p . Вообще-то заключать операцию взятия по модулю в скобки необязатель- но. Вполне допустимо записать ее как a mod b . Однако те, кто не привык к использованию оператора mod, могут поначалу путать его с обычным тек- стом. Чтобы избежать путаницы, мы будем заключать выражение ( a mod b ) в скобки. Обратите внимание: число, взятое по модулю p , всегда должно находиться в диапазоне 0 , . . . , p − 1 , даже если исходное целое число было отрицатель- ным. Некоторые языки программирования допускают применение операций по модулю к отрицательным числам (что очень раздражает математиков). Например, если мы возьмем –1 по модулю p , то получим p − 1 . Общее прави- ло формулируется таким образом: чтобы подсчитать ( a mod p ) , необходимо найти числа q и r , такие, что a = qp + r и 0 ≤ r < p . Результатом выражения ( a mod p ) будет r . Если a = − 1 , то q = − 1 и r = p − 1 . 11.3.1 Сложение и вычитание Складывать по модулю p очень легко. Просто сложите два числа и вы- чтите из полученного результата p , если он окажется б´ольшим или равным p . Поскольку оба слагаемых находятся в диапазоне 0 , . . . , p − 1 , их сумма не может превышать 2 p − 2 , поэтому, чтобы получить результат в нужном диапазоне, достаточно вычесть p не более одного раза. Вычитание выполняется аналогично сложению. Вычтите из одного чис- ла другое и, если полученный результат окажется отрицательным, добавьте к нему p . Эти правила применимы только к числам, уже взятым по модулю p . Если же они находятся за пределами диапазона 0 , . . . , p − 1 , вам придется выпол- нять полноценное взятие их суммы по модулю p . Чтобы привыкнуть к вычислениям по модулю, нужно некоторое время. Вначале вас будут смущать выражения наподобие 5 + 3 = 1(mod7) . Вы хо- рошо знаете, что 5 плюс 3 равняется никак не 1, а 8. В то же время, работая по модулю 7, мы имеем, что 8 mod 7 = 1 , а значит, 5 + 3 = 1(mod7) . Довольно часто, сами того не понимая, мы используем арифметические операции по модулю и в реальной жизни. Подсчитывая время суток, мы скла- 11.3. Арифметика по модулю простого числа 215 дываем часы по модулю 12 (или 24). В расписании автобусов может быть написано, что автобус отправляется в 55 минут такого-то часа, а его время в пути составляет 15 минут. Чтобы узнать, когда автобус приезжает в место назначения, мы складываем 55 + 15 = 10(mod60) и определяем, что автобус приезжает в 10 минут следующего часа. Мы пока ограничимся вычислени- ями по модулю простого числа, однако вы можете выполнять операции по модулю любого числа, которое вам понравится. 11.3.2 Умножение Выполнять умножение, как правило, немного труднее, чем сложение. Что- бы вычислить ( ab mod p ) , мы вначале подсчитываем произведение ab как обычное целое число и затем берем полученный результат по модулю p . Если оба числа находятся в диапазоне 0 , . . . , p − 1 , их произведение может достигать числа ( p − 1) 2 = p 2 − 2 p + 1 . В этом случае вам придется выполнить полно- ценное деление с остатком, чтобы найти пару ( q, r ) , такую, что ab = qp + r и 0 ≤ r < p . Отбросьте q ; искомым результатом является r . Для большей наглядности рассмотрим пример. Пусть p = 5 . Результатом выражения 3 · 4(mod p ) будет 2. Действительно, 3 · 4 = 12 и (12 mod 5) = 2 . Таким образом, 3 · 4 = 2(mod5) . 11.3.3 Группы и конечные поля Математики называют множество чисел по модулю простого числа p (0 , 1 , . . . , p − 1) конечным полем (finite field) и часто именуют его “полем mod p ” или же просто “ mod p ”. Ниже приведено несколько полезных замечаний ка- сательно вычислений в поле mod p . • Если к элементу поля mod p прибавить любое кратное числа p или вы- честь из него любое кратное числа p , исходный элемент не изменится. • Все результаты арифметических операций над полем mod p будут на- ходиться в диапазоне 0 , 1 , . . . , p − 1 . • Все вычисления можно проводить в обыкновенных целых числах и при- менять операцию взятия по модулю только в последний момент. Таким образом, к элементам поля mod p применимы все обычные алгебраиче- ские законы относительно сложения и умножения целых чисел (такие, как a ( b + c ) = ab + ac ) . В литературе применяются разные символы для обозначения конечного поля целых чисел по модулю p . Мы будем обозначать его как Z p . В других источниках можно встретить обозначения GF( p ) или даже Z /p Z . |