Арифметика вычетов

Вы все учили математику вычетов в школе. Иногда ее называли "арифметикой часов". Если Милдред сказ а-ла, что она будет дома к 10:00, и опоздала на 13 часов, то когда она придет домой, и на сколько лет отец лишит ее водительских прав? Это арифметика по модулю 12. Двадцать три по модулю 12 равно 11.

(10 + 13) mod 12 = 23 mod 12 = 11 mod 12

Другим способом записать это является утверждение об эквивалентности 23 и И по модулю 12:

10 + 13 = 11 (mod 12)

В основном, а = Ь (mod и), если а = Ъ + кп для некоторого целого к. Если а неотрицательно и Ъ находится между 0 и и, можно рассматривать Ъ как остаток при делении а на п. Иногда, Ъ называется вычетома по моду­лю и. Иногда а называется конгруэнтнымЪ по модулю и (знак тройного равенства, =, обозначает конгруэнт­ность). Одно и то же можно сказать разными способами.

Множество чисел от 0 до и-1 образует то, что называется полным множеством вычетовпо модулю и. Это означает, что для любого целого а, его остаток по модулю и является некоторым числом от 0 до й-1.

Операция a mod и обозначает остаток от а, являющийся некоторым целым числом от 0 до й-1. Эта операция называется приведением по модулю.Например, 5 mod 3 = 2.

Это определение mod может отличаться от принятого в некоторых языках программирования. Например, оператор получения остатка в языке PASCAL иногда возвращает отрицательное число. Он возвращает число между -(и-1) и и-1. В языке С оператор % возвращает остаток от деления первого выражения на второе, оно может быть отрицательным числом, если любой из операндов отрицателен. Для всех алгоритмов в этой книге проверяйте, что вы добавляете и к результату операции получения остатка, если она возвращает отрицательное число.

Арифметика остатков очень похожа на обычную арифметику: она коммутативна, ассоциативна и дистриб у-тивна. Кроме того, приведение каждого промежуточного результата по модулю п дает тот же результат, как и выполнение всего вычисления с последующим приведением конечного результата по модулю п.

{а + Ъ) mod n = ((a mod n) + (b mod и)) mod n

(а - Ъ) mod n = ((a mod n) - (b mod и)) mod n

(а * Ъ) mod n = ((a mod n) * (b mod и)) mod n

(а * ф+с)) mod п == (((a*b) mod и) + ((а*с) mod и)) mod и

Вычисление mod n часто используется в криптографии, так как вычисление дискретных логарифмов и ква д-ратных корней mod n может быть нелегкой проблемой. Арифметика вычетов, к тому же, легче реализуется на компьютерах, поскольку она ограничивает диапазон промежуточных значений и результата. Для ^-битовых вы­четов п, промежуточные результаты любого сложения, вычитание или умножения будут не длиннее, чем 2 к бит. Поэтому в арифметике вычетов мы можем выполнить возведение в степень без огромных промежуточных р е-зультатов. Вычисление степени некоторого числа по модулю другого числа,

а^хтойп,

представляет собой просто последовательность умножений и делений, но существуют приемы, ускоряющие это действие. Один из таких приемов стремится минимизировать количество умножений по модулю, другой -оптимизировать отдельные умножения по модулю. Так как операции дистрибутивны, быстрее выполнить возв е-дение в степень как поток последовательных умножений, каждый раз получая вычеты. Сейчас вы не чувствуете разницы, но она будет заметна при умножении 200-битовых чисел.

Например, если вы хотите вычислить с? mod n, не выполняйте наивно семь умножений и одно приведение по модулю:

{а * а * а * а * а * а * а * a) mod n

Вместо этого выполните три меньших умножения и три меньших приведения по м одулю:

{{a² mod nf mod nf mod n

Точно также,

a¹⁶ mod n =(((a² mod nf mod nf mod nf mod n

Вычисление cf, где х не является степенью 2, ненамного труднее. Двоичная запись представляет х в виде суммы степеней 2: 25 - это бинарное 11001, поэтому 25 = 24 + 23 + 20. Поэтому

a²⁵ mod п = (а*а²⁴) mod п = (a* a**aⁱ⁶) mod n =

= (а*(( а²) ²) ²*((( а²) ²) ²) ²) mod п = (**((( а*а²) ²) ²) ²) mod n

С продуманным сохранением промежуточных результатов вам понадобится только шесть умножений:

(((((((a² mod nf af mod nf mod nf mod nf mod nf *a) mod n

Такой прием называется цепочкой сложений[863], или методом двоичных квадратов и умножения. Он ис­пользует простую и очевидную цепочку сложений, в основе которой лежит двоичное представление числа. На языке С это выглядит следующим образом:

unsigned long qe2(unsigned long x, unsigned long y, unsigned long n) { unsigned long s, t, u; int i;

s=l; t=x; u=y; while (u) {

if(u&l) s=(s*t)%n;

u»l;

t=(t*t)%n; }

return(s) }

А вот другой, рекурсивный, алгоритм:

unsigned long fast_exp(unsigned long x, unsigned long y, unsigned long N) { unsigned long tmp;

if(y==l) return(x % N); if (1^л(х&1)) {

tmp= fast_exp(x,y/2,N);

return ((tmp*tmp)%N); else {

tmp = fast_exp(x,(y-1)/2,N);

tmp = (tmp*tmp)%N;

tmp = (tmp*x)%N;

return (tmp); ) )

Этот метод уменьшает количество операций, в среднем, до 1.5* к операций, где к - длина числа х в битах. Найти способ вычисления с наименьшим количеством операций - трудная проблема (было доказано, что поел е-довательность должна содержать не меньше к-\ операций), но нетрудно снизить число операций до 1.1** или даже лучше при больших к.

Эффективным способом много раз выполнять приведение по модулю для одного п является метод Монтго­мери[1111]. Другой метод называется алгоритмом Баррета[87]. Эффективность описанного алгоритма и этих двух методов рассматривается в [210]: алгоритм, рассмотренный мною, является наилучшим для едини ч-ного приведения по модулю, алгоритм Баррета - наилучшим для малых аргументов, а метод Монтгомери - на и-лучшим для обычного возведения в степень по модулю. (Метод Монтгомери также использует преимущество малых показателей степени, используя прием, называющийся смешанной арифметикой.)

Операция, обратная возведению в степень по модулю и, вычисляет дискретный логарифм. Ядальше вкратце рассмотрю эту операцию.