Сложение по модулю 2
Сложе́ние по мо́дулю 2 (логи́ческое сложе́ние, исключа́ющее «ИЛИ», строгая дизъюнкция, XOR, поразрядное дополнение, побитовый комплемент) — булева функция, а также логическая и битовая операция. В случае 2 переменных результат выполнения операции является истинным тогда и только тогда, когда лишь один из аргументов является истинным. Для функции трёх и более переменных результат выполнения операции будет истинным только тогда, когда количество аргументов равных 1, составляющих текущий набор — нечетное. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.
Сложение по модулю 2 следует отличать от простого сложения, которое соответствует обыкновенному неисключающему «или» (логической дизъюнкции).
В теории множеств сложению по модулю 2 соответствует операция симметричной разности двух множеств.
Содержание
Обозначения
Запись может быть префиксной («польская запись») — знак операции ставится перед операндами, инфиксной — знак операции ставится между операндами и постфиксной — знак операции ставится после операндов. При числе операндов более 2-х префиксная и постфиксная записи экономичнее инфиксной записи. Чаще всего встречаются следующие варианты записи: 
a ≡ b (операция равнозначности или сравнения по модулю)
Булева алгебра
В булевой алгебре сложение по модулю 2 — это функция двух, трёх и более переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества 
, а «ложь» как 
.
Эту операцию нередко сравнивают с дизъюнкцией потому, что они очень похожи по свойствам, и обе имеют сходство с союзом «или» в повседневной речи. Сравните правила для этих операций:
истинно, если истинно 
исключает последний вариант («оба сразу») и по этой причине называется исключающим «ИЛИ». Операция 
включает последний вариант («оба сразу») и по этой причине иногда называется включающим «ИЛИ». Неоднозначность естественного языка заключается в том, что союз «или» может применяться в обоих случаях.
Квантовые вычисления
В квантовых компьютерах аналогом операции сложения по модулю 2 является вентиль CNOT.
Сложение по модулю два (нечетность)
Ниже показаны его обозначение на электрических схемах (рисунок 4.9) и таблица истинности (таблица 4.7).
Элемент суммирует значения переменных по модулю два (символ (псевдоплюс) означает mod2: 0 + 0 = 0; 1 + 1 = 0; 1 + 0 = 1; 0 + 1 = 1).
Если при суммировании число единиц нечетно, то функция равна 1, в противном случае — F=0.
Сложение по модулю два с отрицанием (четность)
Элемент реализует логическую функцию
Ниже показаны его обозначение на электрических схемах (рисунок 4.10) и таблица истинности (таблица 4.8).
Элемент формирует сумму по модулю два, которая затем инвертируется на выходе. Если при суммировании число единиц четно, то функция равна 1, в противном случае — F = 0.
Модульная арифметика.
Пусть m – некоторое натуральное число. Не все натуральные числа делятся на m . Возможными остатками от деления являются 1, 2, . m – 1, 0 (последний при делении нацело). По модулю m каждое натуральное число воcпринимается как остаток от деления этого числа на m : $$25\,mod\,3 = 1, \\ 9\,mod\,7=2, \\ 100\,mod\,26=22, \\ 100\,mod\,32=4$$ и т.п.
Два числа a и b называются сравнимыми по модулю m , если при делении на m они дают одинаковые остатки, т.е. если %%a\,mod\,m=b\,mod \,m%%.
В этом случае пишут %%a≡b (mod\,m)%% («a сравнимо с %%b%% по модулю %%m%%»). Так, например, $$5\equiv11(mod\,3),\\ 25\equiv0(mod\,5), \\ 48\equiv6(mod \,7).$$
На множестве чисел %%1, 2, . m – 1%%, %%0%% вводится сложение по модулю %%m%%: в качестве результата берется остаток от деления обычной суммы слагаемых на модуль %%m%%, т.е. %%a+_m b=(a+b)mod\, m%%. Например, при сложении по модулю 2 получаем %%0+_2 0=1+_2 1=0%% и %%0+_21=1+_20=1%%. Составим таблицу сложения по модулю 3:
| %%+_3%% | 0 | 1 | 2 |
| 0 | 0 | 1 | 2 |
| 1 | 1 | 2 | 0 |
| 2 | 2 | 0 | 1 |
Как видим, %%2+_32 = (2+2)mod\,3 = 4\,mod\,3 = 1%%.
При вычитании по модулю m для соответствующих чисел осуществляют обычное вычитание и, если в результате получится отрицательное число, к нему прибавляют m . Например, по модулю 5 имеем: %%1 –_5\,4 = -3\,mod\,5 = 2%%.
Если некоторый алфавит имеет мощность m (т.е. в нем m букв), то сложение и вычитание по модулю m можно истолковывать как сложение и вычитание букв с соответствующими номерами. Так, при m=32 (русский алфавит) имеем: $$Й — Ц = 10 -_ <32>23 = -13\,mod\,32 = 19 = Т,$$ $$Т + Т = 19 +_ <32>19= 38\,mod\,32=6=Е $$ и т.п.
При таком истолковании модульных операций сложения и вычитания, шифрование по Виженеру – это сложение блока открытого текста с ключом по модулю мощности алфавита. Например, зашифруем открытый текст шифр Виженера на ключе з а д а ч а . Длина блоков (и ключа) равна 6. Текст разбивается на два блока:
каждый из которых побуквенно складывается с ключом:
$$(шифрви) + (задача) = (25,9,21,17,3,9) +_ <32>(8,1,5,1,24,1) =\\ (33,10,26,18,27,10)mod\,32 = (1,10,26,18,27,10) = АЙЩСЪЙ,$$
$$(женера) + (задача) = (7,6,14,6,17,1) +_ <32>(8,1,5,1,24,1) =\\ (15,7,19,7,9,2)=ОЖТЖИБ$$
Итоговая криптограмма: АЙЩСЪЙОЖТЖИБ .
При дешифровании из блока криптограммы побуквенно вычитается ключ. Так, зная, что криптограмма LAGZJEUUXRTJE получена на ключе Виженера p r o b l e m («задача»), легко восстанавливаем открытый текст. Сначала из первого блока криптограммы побуквенно вычитаем ключ:
$$LAVGZJE – PROBLEM = (12,1,22,7,26,10,5) –_ <26>(16,18,15,2,12,5,13) = \\ (-4, -17,7,5,14,5,-8)mod\, 26 = (22,9,7,5,14,5,18) = vigener$$
затем ключ побуквенно вычитается из второго блока криптограммы:
$$UUXRTJE — PROBLEM = (21,21,24,18,20,10,5) -_<26>(16,18,15,2,12,5,13) =\\ (5,3,9,16,8,5,-8)mod \,26=(5,3,9,16,8,5,18)= ecipher.$$
Открытый текст: Vigenere cipher (шифр Виженера).
В дальнейшем понадобится и умножение по модулю m: оно выполняется аналогично сложению – в качестве результата берется остаток от деления на m обычного произведения сомножителей. Например, для умножения по модулю 4 получаем следующую таблицу:
| %%×_4%% | 0 | 1 | 2 | 3 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 |
| 2 | 0 | 2 | 0 | 2 |
| 3 | 0 | 3 | 2 | 1 |
Отметим необычное равенство %%2 ×_4 2=0%%, оба сомножителя отличны от нуля, а их произведение равно нулю.