Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
6.1.1 Структурная схема главы
В разделе 6.2 вводятся основные понятия, операции по модулю, а также классы вычетов. В разделе 6.3 описывается функция Эйлера "фи". В разделе 6.4 излагается единообразная точка зрения на теоремы Ферма, Эйлера и Лагранжа. Раздел 6.5 посвящен квадратичным вычетам. В разделе 6.6 рассматриваются алгоритмы извлечения квадратных корней по модулю. Заключительный раздел 6.7 посвящен числам Блюма (Blum).
6.2 Сравнения и классы вычетов
Основы модулярной арифметики изложены в разделе 4.3.2.5. Рассмотрим еще несколько фактов этой теории.
Теорема 6.1. Для целых чисел п > 1 отношение сравнимости по модулю п является рефлексивным, симметричным и транзитивным. Иначе говоря, для любых а,Ь,с€% выполняются следующие условия.
1. а = a(mod п).
2. Если а = 6(mod п), то Ъ = a(mod п).
3. Если а = 6(modи)нЬе c(modп), то а = c(modп). о
216
Часть II. Математические основы
Отношение, обладающее тремя указанными свойствами, называется отношением эквивалентности (equivalence relation). Как известно, отношение эквивалентности между элементами некоего множества порождает разбиение этого множества на классы эквивалентности (equivalence class). Обозначим через "=п" отношение эквивалентности, определяемое сравнением по модулю п. Это отношение определяет во множестве Z ровно п классов эквивалентности, каждый из которых состоит из целых чисел, сравнимых между собой по модулю п. Обозначим эти п классов следующим образом:
0,1,...,п- 1,
где
а — {х 6 Z | a;(modn) = а}. (6.2.1)
Эти классы называются классами вычетов по модулю п (residue class modulo n). Очевидно, что
Zn = {0,1,...,7Г^Т}. (6.2.2)
С другой стороны, если рассматривать множество Z как тривиальное подмножество множества целых чисел Z, то смежный класс nZ (определение 5.7 в разделе 5.2.1) представляет собой множество всех целых чисел, кратных числу п:
nZ = {0, ±п, ±2п,...}. (6.2.3)
Рассмотрим фактор-группу (определение 5.8 в разделе 5.2.1) с операцией сложения.
Z/nZ = {х + nZ | х е Z}. (6.2.4)
Подставляя в выражение (6.2.4) формулу (6.2.3), получаем
Z/nZ = {x + nZ\xeZ} =
= {0 + {0, ±n, ±2n,...},
1 + {0, ±п, ±2п,...},
2 + {0, ±п, ±2п,...},
(п — 1) + {0, ±п, ±2п, --.}}= (6.2.5)
= {{0,±п,±2п,...},
{1,±п + 1,±2п+1,...}, {2,±п + 2,±2п + 2,...},
{(п-1),±п+(п-1),±2п + (п-1),...}}.
Глава 6. Теория чисел
217
В структуре (6.2.5) существует только п разных элементов. Все другие варианты исключены. Например,
п+ {0,±п,±2п,...} = {0, ±п, ±2п,... }
и
(п + 1) + {0, ±п, ±2п,...} = {1, ±п + 1, ±2п + 1,...}
и т.д. Сравнивая множества (6.2.2) и (6.2.5) и учитывая определение класса а в выражении (6.2.1), приходим к выводу, что при п > 1
Ъп = Ъ/nL.
Обозначение Ъ/пЪ является стандартным для классов вычетов по модулю п, хотя для удобства в книге используется более краткое обозначение Ъп.
Теорема 6.2. Для любых чисел а,ЪЕЪ операции сложения и умножения классов вычетов аиЪ определяются следующим образом.
а + Ъ = a + b, a-b = ab.
Следовательно, для любого целого числа п > 1 отображение f : Ъ ¦—> Ъп, определенное отношением сравнимости по модулю п, является гомоморфизмом из поля Ъ в фактор-группу Ъп. ?
6.2.1 Модулярная арифметика в фактор-группе Ъп
Существование гомоморфизма из поля Ъ на фактор-группу Z„ означает, что арифметические операции в группе Ъп (по модулю п) обладают свойствами арифметических операций в поле Z.
Теорема 6.3. Для целых чисел п > 1 из того, что а = 6(mod п) и с = d(raod п), следует, что а ± Ъ = с ± d(mod п) и ас = bd(mod п).
Несмотря на то что справедливость этой теоремы непосредственно следует из существования гомоморфизма между структурами Ъ и Zn, ее доказательство достойно внимания.
Доказательство. Если п | а — Ъ и п \ с — d, то п \ {а ± с) — (b ± d).
Кроме того, п | (а — Ь)(с — d) = (ас—bd) — Ь(с — d) — d(a — b). Итак, п \ (ас — bd).a
Свойства арифметических операций в фактор-группе Zn, описанные в теореме 6.3, называются свойствами сравнимости (congruent property). Это значит, что
218
Часть II. Математические основы
выполнение одних и тех же вычислений с левой и правой частью равенства сохраняет его справедливость. Однако в теореме 6.3 ничего не говорится о делении. Операция деления в поле Z обладает следующим свойством сравнимости:
если Vd ф 0 : ad — bd, то а = Ь. (6.2.6)
Операция деления в фактор-группе Zn также обладает свойством сравнимости, которое лишь немного отличается от выражения (6.2.6). Прежде чем вывести эту формулу, рассмотрим подробнее свойства деления в поле Z. Представим себе, что поле Z — это частный случай фактор-группы Zn, когда п — со, и что число со делится на любое целое число, причем частное от этого деления снова равно со. Следовательно, можно считать, что первое равенство в выражении (6.2.6) выполняется по модулю со, а второе — по модулю oo/d. Поскольку oo/d = со, оба равенства в выражении (6.2.6) являются двумя представлениями одной и той же формулы. Это свойство сравнимости для деления в поле Z наследуется факторгруппой Zn и выражается следующей формулой.
Теорема 6.4. Для целых чисел n>lud=fi0u3 тождества ad = 6d(mod n) следует, что a = b (mod ^щ^)-
