мя. Если P = NP, то они вскрываются слабыми, детерминированными алгоритмами.

Следующим в иерархии сложности идет класс PSPACE. Проблемы класса PSPACE могут быть решены в полиномиальном пространстве, но не обязательно за полиномиальное время. PSPACE включает NP, но ряд проблем PSPACE кажутся сложнее, чем NP. Конечно, и это пока недоказуемо. Существует класс проблем, так называемых PSPACE-полных, обладающих следующим свойством: если любая из них является NP-проблемой, то PSPACE = NP, и если любая из них является P-проблемой, то PSPACE = P.

И наконец, существует класс проблем EXPTIME. Эти проблемы решаются за экспоненциальное время. М о-жет быть действительно доказано, что EXPTIME-полные проблемы не могут быть решены за детерминир о-ванное полиномиальное время. Также показ ано, что P не равно EXPTIME.

NP-полные проблемы

Майкл Кэри (Michael Carey) и Дэвид Джонсон (David Johnson) составили список более чем 300 NP-полных проблем [600]. Вот некоторые:

- Проблема путешествующего коммивояжера. Путешествующему коммивояжеру нужно посетить разли ч-ные города, используя только один бак с горючим (существует максимальное расстояние, которое он м о-жет проехать). Существует ли маршрут, позволяющий ему посетить каждый голод только один раз, и с-пользуя этот единственный бак с горючим? (Это обобщение проблемы гамильтонова пути - см. раздел

5.1.)

- Проблема тройного брака. В комнате n мужчин, n женщин и n чиновников (священников, раввинов, кого угодно). Есть список разрешенных браков, записи которого состоят из одного мужчины, одной женщины и одного регистрирующего чиновника. Дан этот список троек, возможно ли построить n браков так, чтобы любой либо сочетался браком только с одним человеком или регистрировал только один брак?

- Тройная выполнимость. Есть список n логических выражений, каждое с тремя переменными. Например: если (x и у) то z, (x и w) или (не z), если ((не u и не x) или (z и (и или не x))) то (не z и и) или x), и т.д. Существует ли правильные значения всех переменных, чтобы все утверждения были истинными? (Это ч а-стный случай упомянутой выше проблемы Выполнимости.)

11.3 Теория чисел

Это не книга по теории чисел, поэтому я только набросаю ряд идей, используемых в криптографии. Если вам нужно подробное математическое изложение теории чисел, обратитесь к одной из этих книг: [1430, 72, 1171, 12, 959, 681, 742, 420]. Моими любимыми книгами по математике конечных полей являются [971, 1042]. См. также [88, 1157, 1158, 1060].

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

Вы все учили математику вычетов в школе. Иногда ее называли "арифметикой часов". Если Милдред сказ ала, что она будет дома к 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дно и то же можно сказать разными способами.

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

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

Это определение mod может отличаться от принятого в некоторых языках программирования. Например, оператор получения остатка в языке PASCAL иногда возвращает отрицательное число. 0н возвращает число между -(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 может быть нелегкой проблемой. Арифметика вычетов, к тому же, легче реализуется на компьютерах, поскольку она ограничивает диапазон промежуточных значений и результата. Для к-битовых вычетов 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

Вычисление a*, где 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

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

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

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

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

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

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

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

Н0Д(a,n)=1

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

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

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

int g;

if (x < 0)

x = -x;

if (y < 0)

y = -y; if (x + y == 0 ) ERROR ;