Математические основы защиты информации. Ишмухаметов Ш.Т - 16 стр.

Глава 1. Системы шифрования с открытым ключом                            17

модулю p, записывается,

             a ≡ b ( mod p),

если p|(a − b) (разность a − b делится на p без остатка).

      Отношение сравнения по модулю натурального числа обладает
следующими свойствами:
       1. Рефлексивность: a ≡ a ( mod p).
       2. Симметричность: a ≡ b ( mod p) → b ≡ a ( mod p).
       3. Транзитивность: a ≡ b ( mod p) & b ≡ c ( mod p) → a ≡ c ( mod p).

      Значит отношение сравнения по модулю является отношением
эквивалентности на множестве целых чисел. Классы эквивалентности,
образованные целыми числами по этому отношению, называются вычетами.
Вычет, содержащий число k , обозначается k . Множество классов вычетов
по модулю числа натурального n > 0 содержит ровно n элементов,
записываемых как Z n = {0, 1, ... n − 1}.
      Над вычетами можно выполнять арифметические операции сложения,
вычитания, умножения и возведения в степень, а если число n простое или
является некоторой степенью простого числа, то и деление. Будем обозначать
множество вычетов по модулю n через Zn .
      Отметим, что для любых a и b выполняется формула a + b = a + b
(то же для других перечисленных выше операции), поэтому операции над
вычетами выполняются как над обычными числами, приводя результат к
значению, принадлежащему интервалу [0, n−1] путем выполнения операции
вычисления остатка от деления результата на число n (т.е. операции,
обозначаемой mod n). Например, в множестве Z7 2 · 5 = 10 = 3 ( mod 7).
Чаще пишут просто: 2 · 5 = 3 ( mod 7).
      Множество классов вычетов по модулю n образует структуру,
являющуюся кольцом. Кольцом          K      называется непустое множество
элементов, на котором определены две арифметические операции сложения
+ и умножения ·, относительно которых выполняются следующие формулы: