Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 84

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 78 79 80 81 82 83 < 84 > 85 86 87 88 89 90 .. 311 >> Следующая

Часть II. Математические основы
равны нулю, ее полный ранг равен г, и, следовательно, система (6.2.11) имеет единственное решение.
Если модули в системе (6.2.10) являются попарно взаимно простыми, нетрудно найти систему классов, состоящих из вычетов единицы.
Теорема 6.7 (Китайская теорема об остатках). Если модули системы линейных уравнений (6.2.10) являются взаимно простыми, т.е. gcd(mj,mj) = 1 при 1 ^ i < j ^ г, то существует класс вычетов lmi, удовлетворяющий условию
lmi = 0(mod rrij). (6.2.16)
Следовательно, существует число х € Ъи, являющееся единственным решением системы (6.2.10), где М = т\т2. ¦ ¦ тг.
Доказательство. Сначала докажем существование, а затем — единственность решения.
Существование. Для каждого числа г — 1,2,..., г выполняется условие gcd(mj, М/тпг) = 1. По теореме 4.2 (раздел 4.3.2.5) существует число yi G Z^, удовлетворяющее условию
(M/mJyi = 1 (mod mi). (6.2.17)
Более того, поскольку rrij | (M/mj) для всех j ф г, имеем
{М/гщ)уг - 0(mod rrij). (6.2.18)
Итак, число (М/тщ)у1 является искомым. Пусть
г
х <— lm^mod М). (6.2.19)
г=1
Следовательно, вектор х является решением системы (6.2.10) и образует класс вычетов единицы по модулю М.
Единственность. Рассмотрим такую линейную систему (6.2.11), (6.2.12), (6.2.13) и (6.2.14), в которой все элементы матрицы А и правой части С являются целыми числами. Заметим, что в поле Z
det(yl) = lmi lm2 ... lmr ф 0. (6.2.20)
Отсюда следует, что г столбцов матрицы А образуют базис r-мерного векторного пространства Z х Z х^... х Z (этот базис напоминает так называемый "естествен-
г
ный базис" в линейной алгебре, в котором каждый базисный вектор содержит только одну единицу, а остальные элементы равны нулю). Таким образом, при
Глава 6. Теория чисел
223
любом векторе C€Z х Ъ х ... х Ъ система (6.2.11) имеет единственное решение
г
X € Ъ х Ъ х^... х Ъ. Как показано выше, элементы вектора X вычисляются по формуле (6.2.19). ?
Доказательство теоремы 6.7 является конструктивным, поскольку мы построили алгоритм, позволяющий находить решение системы (6.2.10).
В алгоритме 6.1 затраты времени происходят только на шаге 2.1, на котором с помощью обобщенного алгоритма Евклида вычисляется мультипликативная инверсия большого целого числа. Если тщ < М при всех г = 1,2,..., г, временная сложность алгоритма 6.1 имеет порядок Os(r(logM)2).
Перечислим некоторые выводы из теоремы 6.7.
1. Каждое число х € Ъм порождает вектор С € Zmi х х ... х Zmr. Из выражения (6.2.19) следует, что все элементы вектора С вычисляются по формуле
Cj *— ж(тоа mi) при г = 1,2,..., г.
2. В частности, числа 0 и 1 в фактор-группе Ъм порождают векторы 0 и 1 соответственно из векторного пространства Zmi х Zm2 х ... х Ътг.
3. Пусть числа хих' порождают векторы
С2
4
соответственно. Тогда
число х • х порождает вектор
(с\ ¦ dx (mod гп\)^ С2 ¦ C2(modm2)
\Cr -^(modm^y Итак, мы доказали следующую теорему.
Теорема 6.8. Если gcd(mi,mj) = 1 для 1 ^ г < j ^ г, то для числа М = = mi?7i2... тщ- фактор-группа Ъм является изоморфной векторному пространству Ътх х Zm2 х ... х Ътг, причем изоморфизм
f : ZM ^ Zm, х
¦'ТП2
задается формулой
f(x) = (a;(mod mi), a;(mod гаг),.. -, a;(mod mr)).
224
Часть II. Математические основы*
Алгоритм 6.1. Китайская теорема об остатках
ВВОД: кортеж целых попарно взаимно простых чисел (mi, m2, -.., т,-);
кортеж целых чисел (ci mod(mi), с2 mod(m2),..., cr mod(mr)).
ВЫВОД: целое число х < М = mim2 ... тг — решение системы (6.2.10).
1. М *— т\гп2 ¦ - - тг;
2. for (г = 1, г + +, г) do
а) yi *— (M/mj)_1(modmj); (* Обобщенный алгоритм Евклида *)
б) Тщ; «- yiM/ггц;
3. return (jT, lmiCi(modM)^.
Теорема 6.8 весьма полезна при изучении криптографических систем и протоколов, в основе которых лежат группы по составным целым модулям. Во многим местах книги мы будем применять изоморфизм между группой 2? и декартовым произведением групп Zp1 х Z*, где тг = pq, apnq — простые числа. Например, мь| будем использовать тот факт, что нециклическая группа Z* порождается двумя элементами циклических групп 2^ и Z* соответственно.
Рассмотрим одно из приложений китайской теоремы об остатках: упрощение] вычислений с помощью изоморфизма.
Пример 6.2. Пока мы не умеем вычислять квадратный корень по целочисленном}! модулю (этот метод будет рассмотрен в разделе 6.6). Однако иногда квадратные корни в некотором пространстве (например, в поле Z) легко угадать, не применяя операций модулярной арифметики. Применим теорему 6.8 для вычисления одной! из квадратных корней числа 29 в группе Z35.
Сведения, которыми мы владеем на данный момент, не позволяют нам утверждать, что число 29 является квадратом в группе Z35, поэтому его квадратный корень нам неизвестен. Однако, применяя теорему 6.8 и отображая число 2Я в изоморфное пространство Z5 х z7, получаем
29(mod 5) ^ 4, 29(mod 7) н-> 1,
т.е. его образом выступает пара (4,1). Очевидно, что оба числа 4 и 1 являются] квадратами: число 4 — квадрат числа 2, а число 1 — единицы. Благодаря изомор-| физму становится очевидным, что один из квадратных корней числа 29 в груп-] пе Z35 соответствует паре (2,1) в пространстве Z5 х Z7. Применяя китайскую] теорему об остатках (алгоритм 6.1), получаем
Предыдущая << 1 .. 78 79 80 81 82 83 < 84 > 85 86 87 88 89 90 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed