[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3]

Операции над вычетами и их свойства

Над вычетами (по модулю n) определены операции сложения и умножения по модулю n, обозначаемые, соответственно, +_n и *_n и определяемые следующим образом:
a +_n b:= (a + b) mod n, a *_n b:= (а * b) mod n.

Замечания
Если из контекста ясно, что подразумеваются операции по модулю n, то индекс n опускается.
mod - оператор определения остатка от деления в Pascal.

Свойства операций над вычетами

Если a ≡ c (mod n) и b ≡ d (mod n), то

• a+b ≡ c+d (mod n)
• a-b ≡ c-d (mod n)
• a*b ≡ c*d (mod n)

Примеры: n=5; 3≡8, 1≡-14(mod 5) , отсюда
3+1=4≡8+(-14)=-6 (mod 5)
3*1=3≡8*(-14)=-112 (mod 5)

Операции между классами вычетов корректно определены, т.е. не зависят от того какой из представителей каждого класса выбран. Это позволяет при шифровании избежать работы с чрезмерно большими числами.
Для сложения, вычитания и умножения вычетов коммутативные, ассоциативные и дистрибутивные свойства аналогичны свойствам операций над числами:

• a+b ≡ b+a (mod n)
  a*b ≡ b*a (mod n)
• (a+b)+c ≡ a+(b+c) (mod n)
  (a*b)*c ≡ a*(b*c) (mod n)
• a*(b+c) ≡ a*b+a*c (mod n)

Сокращать вычеты нельзя.
Например 2*5≡2*2 (mod 6),
но 5 2 (mod 6)
Обе части сравнения можно умножить на одно и то же целое число, обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем сравнения.

Таблицы сложения и умножения

Для операций над вычетами при фиксированном модуле удобно составить таблицы сложения и умножения. Например n=6:

Таблица сложения + 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4	Таблица умножения * 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1

Важную роль в компьютерной технике играют таблицы для n=2, которые определяют таблицы истинности логических операций и &.

[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3]