Модульная арифметика.

Пусть 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%%, оба сомножителя отличны от нуля, а их произведение равно нулю.