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

В криптографии и криптоанализе часто бывает необходимо сложить две последовательности чисел или же вычесть одну последовательность из другой. Такое сложение и вычитание производится, как правило, не с помощью обычных арифметических действий, а с помощью операций, называемых модульной арифметикой. В модульной арифметике сложение, вычитание (а также и умножение, которое понадобится нам в главах 12 и 13) выполняется относительно некоторого фиксированного числа, которое называется модуль. Типичными значениями модулей, используемых в криптографии, являются 2, 10 и 26. Какой бы модуль мы ни взяли, все встречающиеся числа заменяются на остатки от деления этих чисел на модуль. Если в остатке получается отрицательная величина, то к ней прибавляют значение модуля, чтобы остаток стал неотрицательным. Например, если используется модуль 26, то единственно возможные числа лежат в диапазоне от 0 до 25. Так, если прибавить 17 к 19, то результат равен 10, поскольку 17+19=36, а 36 при делении на 26 дает остаток 10. Чтобы указать, что используется модуль 26, принята форма записи:

17+1910(mod 26).

Если вычесть 19 из 17, то результат (-2) получается отрицательным, поэтому к нему прибавляется 26, и в итоге получается 24.

Символ  читается "сравним с", и поэтому мы скажем

"36 сравнимо с 10 по модулю 26" и "-2 сравнимо с 24 по модулю 26".

При сложении по модулю 26 двух числовых последовательностей сформулированные правила сложения применяются к каждой паре чисел по отдельности, без "переноса" на следующую пару. Аналогично, при вычитании по модулю 26 одной числовой последовательности из другой правила вычитания применяются к каждой паре чисел по отдельности, без "заимствования" из следующей пары.

Пример 1.1

Сложить по модулю 26 последовательности 15 11 23 06 11 и 17 04 14 19 23.

Решение

15 11 23 06 11

17 04 14 19 23

32 15 37 25 34

(mod 26) 06 15 11 25 08,

и в результате получаем 06 15 11 25 08.

Если модуль равен 10, то используются только числа от 0 до 9; при модуле 2 - только 0 и 1. Арифметика по модулю 2, или, как ее обычно называют, двоичная (бинарная) арифметика, имеет особое значение, поскольку в этом случае сложение и вычитание являются идентичными операциями, то есть всегда дают одинаковый результат, а именно:

 0  0  1  1  0  0  1  1

+0  1  0  1 -0  1  0  1

 0  1  1  2  0 -1  1  0

0  1  1  0  0  1  1  0 (mod 2) в обоих случаях.