Арифметика остатков очень похожа на обычную арифметику: она коммутативна, ассоциативна и дистриб у-тивна. Кроме того, приведение каждого промежуточного результата по модулю 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 может быть нелегкой проблемой. Арифметика вычетов, к тому же, легче реализуется на компьютерах, поскольку она ограничивает диапазон промежуточных значений и результата. Для к-битовых вычетов n, промежуточные результаты любого сложения, вычитание или умножения будут не длиннее, чем 2 к бит. Поэтому в арифметике вычетов мы можем выполнить возведение в степень без огромных промежуточных р е-зультатов. Вычисление степени некоторого числа по м одулю другого числа,

ax mod n,

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

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

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

Вместо этого выполните три меньших умножения и три меньших приведения по м одулю: ((a2 mod n)2 mod n)2 mod n Точно также,

a16 mod n =(((a2 mod n)2 mod n)2 mod n)2 mod n

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

a25 mod n = (a*a24) mod n = (a* a8*a16) mod n =

= (a*(( a2) 2) 2*((( a2) 2) 2) 2) mod n = (a*((( a*a2) 2) 2) 2) 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 (lA(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]: алгоритм, рассмотренный мною, является наилучшим для едини ч-ного приведения по модулю, алгоритм Баррета - наилучшим для малых аргументов, а метод Монтгомери - на и-лучшим для обычного возведения в степень по модулю. (Метод Монтгомери также использует преимущество малых показателей степени, используя прием, называющийся смешанной арифметикой.)

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

Простые числа

Простым называется целое число, большее единицы, единственными множителями которого является 1 и оно само: оно не делится ни на одно другое число. Два - это простое число. Простыми являются и 73, 2521, 2365347734339 и 2756839-1. Существует бесконечно много простых чисел. Криптография, особенно криптография с открытыми ключами, часто использует большие простые числа (512 бит и даже бол ьше).

Евангелос Кранакис (Evangelos Kranakis) написал отличную книгу по теории чисел, простым числам и их применению в криптографии [896]. Паула Рибенбойм (Paula Ribenboim) написала две отличных справочных работы по простым числам вообще [1307, 1308].

Наибольший общий делитель

Два числа называются взаимно простыми, если у них нет общих множителей кроме 1. Иными словами, е с-ли наибольший общий делитель a и n равен 1. Это записывается как:

H0(a,n)=1

Взаимно просты числа 15 и 28. 15 и 27 не являются взаимно простыми, а 13 и 500 - являются. Простое число взаимно просто со всеми другими числами, кроме ч исел, кратных данному простому числу.

0дним из способов вычислить наибольший общий делитель двух чисел является алгоритм Эвклида. Эвк-лид описал этот алгоритм в своей книге, Элементы, написанной в 300 году до нашей эры. 0н не изобрел его. Историки считают, что этот алгоритм лет на 200 старше. Это самый древний нетривиальный алгоритм, который дошел до наших дней, и он все еще хорош. Кнут описал алгоритм и его современные модификации в [863]. На языке C:

/* возвращает НОД (gcd) x и y */ int gcd (int x, int y) {

if (x < 0)

x = -x;

if (y < 0)

y = -y;

if (x + y == 0 ) ERROR ;

while (x > 0) { g = x; x = y % x;

return g;

Этот алгоритм можно обобщить для получения НОД массива m чисел:

/* возвращает НОД (gcd) xl, x2...xm */ int multiple gcd (int m, int *x) {

slze t i;

if (m < 1)

return 0;

g = x [0];

for (i=l; i<m;{

g = gcd(g, x[i]); /* оптимизация, так как для случайных x[i], g==l в 60% случаев: */

if (g == 1)

return 1;

return g;

Обратные значения по модулю

Помните, что такое обратные значения? Обратное значение для 4 - 1/4, потому что 4*1/4 =1. В мире вычетов проблема усложняется:

4*x = 1 (mod 7)

Это уравнение эквивалентно обнаружению x и k, таких что 4x = 7k + 1

где x и к - целые числа. Общая задача состоит в нахождении x, такого что 1 = (a*x) mod n

Это также можно записать как a-1 = x (mod n)

Проблему обратных значений по модулю решить нелегко. Иногда у нее есть решение, иногда нет. Например, обратное значение 5 по модулю 14 равно 3. С другой стороны у числа 2 нет обратного значения по модулю 14.

В общем случае у уравнения a-1 = x (mod n) существует единственное решение, если a и n взаимно просты. Если a и n не являются взаимно простыми, то a-1 = x (mod n) не имеет решений. Если n является простым чи слом, то любое число от 1 до n -1 взаимно просто с n и имеет в точности одно обратное значение по модулю n.

Так, хорошо. А теперь как вы собираетесь искать обратное значение a по модулю n? Существует два пути. Обратное значение a по модулю n можно вычислить с помощью алгоритма Эвклида. Иногда это называется расширенным алгоритмом Эвклида.

Вот этот алгоритм на языке C++:

#define isEven(x) ((x & 0x01) == 0)

#define isOdd(x) (x& 0x01)

#define swap(x,y) (xA = y, yA = x, xA = y)

void ExtBinEuclid(int *u, int *v, int *u1, int *u2, int *u3) {

предупреждение: u и v будут переставлены, если u<v int k, tl, t2, t3;