Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ЭЛЕМЕНТЫ ТЕОРИИ И ПРАКТИКИ КОДИРОВАНИЯ

Криптография и, шире, кодирование основываются на ряде областей математики, включая элементы теории чисел, теории групп и т.д. В данном учебнике рассматриваются наиболее базовые понятия, иллюстрирующие основные подходы к кодированию и декодированию сообщений. Одной из таких основ является алгебра вычетов, также называемая модулярной арифметикой или алгеброй сравнений [13, 14].

Алгебра вычетов

Основы алгебры вычетов

Алгебра вычетов — один из тех разделов математики, которые рождались как некоторые формальные рассуждения и только спустя годы нашли свое практическое применение. Так, одной из ее основ является т.н. китайская теорема об остатках. Около 100 г. до н.э. китайский математик Сун Цу (Бип-Тзи) решил такую задачу: найти число, дающее при делении на 3, 5, 7, остатки 2, 3, 2 соответственно.

Теорема 5.1. Китайская теорема об остатках

Если числа ах, а2, ..., ап попарно взаимно просты, то для любых остатков г{, г2, ..., гп таких, что 0 < г,< а, при всех / = 1,2, ..., п, найдется число ТУ, которое при делении на а і дает остаток г, при всех /'= 1,2,..., п.

Рассмотрим множество целых чисел Zи зафиксируем натуральное число т. Целые числа а и Ь называются сравнимыми по данному модулю т, если (а - Ь)т.

В этом случае говорят также, что числа а и Ь находятся в отношении сравнения, и записывают:

а = Ь(тодт),

такая запись называется сравнением.

Замечания.

  • 1. Число т, стоящее под знаком модуля, везде далее будет считаться натуральным, т.е. целым положительным, поскольку сравнение по модулю будет совпадать со сравнением по модулю т.
  • 2. Если числа а и Ь несравнимы по модулю т, то этот факт обозначается записью вида а Ф 6(тос1 т).

Рассмотрим основные свойства сравнений.

Теорема 5.2

Целые числа а и Ь сравнимы по данному модулю т тогда и только тогда, когда а и Ь дают одинаковые остатки при делении на т.

Теорема 5.3

Отношение сравнения по модулю т является отношением эквивалентности.

Непустое множество С называется абелевой группой, если в нем определена коммутативная алгебраическая операция, называемая умножением, которая каждым двум элементам а, Ь из С ставит в соответствие элемент аЬ также из С, называемый их произведением, и обладает свойствами ассоциативности и обратимости.

Кольцо — это множество Я, на котором заданы две бинарные операции: + и х (называемые сложением и умножением), со следующими свойствами.

  • 1. Для любых а, Ь из Яа+Ь=Ь+а — коммутативность сложения.
  • 2. Для любых а, Ь, с из Я а + (Ь + с) = (а + Ь) + с — ассоциативность сложения.
  • 3. Существует 0 из Я; для любого а из Яа + 0 = 0 + а = а — существование нейтрального элемента относительно сложения.
  • 4. Для любых а из Я существует ЬизЯа + Ь = Ь + а = 0 — существование обратного элемента относительно сложения.
  • 5. Для любого а из Я (аЬ)с = а(Ьс) — ассоциативность умножения.
  • 6. Для любых а, Ь, с из Я а ? (Ь + с) = а ? Ь + а • с и (Ь + с) ? а = = Ь ? а + с ? а — дистрибутивность.

Кольца могут обладать следующими свойствами.

  • 1. Существование единицы: существует е из Я: для любого а из Я а ? е = е ? а = а (кольцо с единицей).
  • 2. Коммутативность умножения: для любых а, Ь из ЯаЬ = Ьа (коммутативное кольцо).
  • 3. Отсутствие делителей нуля: для любых а, Ь из Я а ? Ь - 0, следовательно, а = 0 или Ь - 0. Обычно под кольцом понимают ассоциативное кольцо с единицей.

Кольца, для которых выполнены все вышеперечисленные условия, называются целостными.

Класс эквивалентности отношения сравнения по данному модулю т называется классом вычетов по модулю т:

а/ = (mod т) = {х е Z / х = «(mod т)} = «(mod т).

Вычетом класса вычетов по модулю т называется любое из чисел, принадлежащих этому классу вычетов.

Теорема 5.4. Теорема о структуре класса вычетов

Класс вычет «(mod т) совпадает с множеством чисел вида а + к, где клюбое натуральное число:

«(modm) = {« + кт / кN}.

Теорема 5.5

Любые два класса вычетов по модулю т либо совпадают, либо не пересекаются.

Замечание. Введение классов вычетов по модулю позволяет, во-первых, заменять сравнение целых чисел равенством соответствующих классов вычетов, и наоборот, равенство классов вычетов по данному модулю — сравнением вычетов; во-вторых, показывает равноправность всех вычетов класса вычетов.

Теорема 5.6

Если какой-либо вычет класса вычетов по данному модулю т имеет при делении на т остаток г, то все числа, входящие в этот класс вычетов, имеют вид г + тк, где к — любое целое число.

Замечание. Теорема 5.5 очень важна с той точки зрения, что она позволяет сформулировать признак, по которому целые числа объединяются в один класс вычетов: числа, которые при делении на т дают одинаковый остаток, принадлежат одному и тому же классу вычетов.

Теорема 5.7

Число классов вычетов по модулю т конечно и равно т.

Например, классами вычетов по модулю 6 будут следующие счетные множества:

  • 0 = {..., -12, -6, 0, 6, 12, 18, ...};
  • 1 = {..., -17, -11, -5, 1, 7, 13, ...};
  • 2 = {..., -16, -10, -4, 2, 8, 14, ...};
  • 3 = {..., -13, -9, -3, 3, 9, 15, ...};
  • 4 = -14, -8, -2, 4, 10, 16,
  • 5 = -13, -7, -1, 5, И, 17,

Обозначим множество классов вычетов по модулю т символом

Z / т! = {0, I, 2, ..., т - 1}.

Введем на множестве Z / mZ операции сложения и умножения классов вычетов.

Суммой двух классов вычетов а и Ь называется класс вычетов, порожденный элементом а + Ь, т.е.

а © Ь - ал- Ь.

Произведением двух классов вычетов а и Ь называется класс вычетов, порожденный элементом а ? Ь, т.е.

а ® Ь = а ? Ь.

Теорема 5.8

Справедливы следующие утверждения.

  • 1. Алгебра ^ / т1, ©> является абелевой группой.
  • 2. Алгебра / mZ, ©, 0> является коммутативным кольцом.
 
<<   СОДЕРЖАНИЕ   >>