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

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

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

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

10 + 13 ? 11 (mod 12)

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

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

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

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

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

(a + b) mod n == ((a mod n) + (b mod n)) mod n

(a - b) mod n == ((a mod n) - (b mod n)) mod n

(a * b) mod n == ((a mod n) * (b mod n)) mod n

(a * (b+c)) mod n == (((a*b) mod n) + ((a*c) mod n)) mod n

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

a^x mod n,

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

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

(a * a * a * a * a * a * a * a) mod n

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

((a² mod n)² mod n)² mod n

Точно также,

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

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

a²⁵ mod n = (a*a²⁴) mod n = (a* a⁸*a¹⁶) mod n =

= (a*(( a²) ²) ²*((( a²) ²) ²) ²) mod n = (a*((( a*a²) ²) ²) ²) mod n

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

(((((((a² mod n)* a)² mod n)² mod n)² mod n)² mod n)² *a) mod n

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

unsigned long qe2(unsigned long x, unsigned long y, unsigned long n) {

unsigned long s, t, u;

int i;

s=1; t=x; u=y;

while (u) {

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

u>>1;

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 (l^(x&l)) {

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*k операций, где k - длина числа x в битах. Найти способ вычисления с наименьшим количеством операций - трудная проблема (было доказано, что последовательность должна содержать не меньше k-1 операций), но нетрудно снизить число операций до 1.1*k или даже лучше при больших k.

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

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