Математики, шпионы и хакеры. Кодирование и криптография | страница 15
(3) 3 х 3 = 9
(4) 5 x 4 = 20
(5) 7
(6) 35
(7) -44 = -44 + 0 = -44 + 7 х 7
(8) -33 = -33 + 0 = -33 + 5 x 7
(1) 6 меньше, чем модуль, поэтому не меняется
(2) 3 + 14 = 17; 17: 7 = 2 и в остатке 3.
(3) 3 X 3 = 9; 9: 7 = 1 и в остатке 2.
(4) 5 х 4 = 20; 20: 7 = 2 и в остатке 6.
(5) 7 = 7; 7: 7 = 1 и в остатке 0.
(6) 35 = 35; 35: 7 = 5 и в остатке 0.
(7) -44 = -44 + 0; 44 + 7 х 7
(8) -33 = -33 + 0; -33 + 5 x 7
* * *
ТАБЛИЦА УМНОЖЕНИЯ ПО МОДУЛЮ 5 В EXCEL
Построить такую и подобные таблицы очень легко даже с базовыми знаниями офисной программы Excel. В нашем случае синтаксис функций для ячеек Excel (для столбцов и строк на нашем компьютере) показан ниже. Действие «остаток отделения числа на 5» переводится на язык Excel как «=ОСТАТ(число;5)». Конкретная операция по нахождению произведения 4 на 3 по модулю 5 записывается как «=ОСТАТ (4∙3;5)» и дает результат 2. Подобные таблицы очень помогают в расчетах по модульной арифметике.
* * *
Какая связь между модульной арифметикой и шифром Цезаря? Чтобы ответить на этот вопрос, мы запишем в таблице стандартный алфавит и алфавит со сдвигом на три буквы, добавив титульный ряд из 26 чисел.
Мы видим, что зашифрованное значение буквы под номером х (в стандартном алфавите) является буквой, стоящей на позиции х + 3 (также в стандартном алфавите). Поэтому необходимо найти преобразование, которое каждому числу ставит в соответствие число, сдвинутое на три единицы, и взять результат по модулю 26.
Заметим, что 3 является ключом нашего шифра. Таким образом, наша функция записывается как
C(х) = (х + 3) (mod 26),
где х — изначальное значение, а С(х) — зашифрованное значение. Теперь достаточно подставить вместо буквы ее числовое значение и применить трансформацию.
Возьмем в качестве примера слово PLAY и зашифруем его.
Буква Р стоит на позиции 15, С(15) = 15 + 3
Буква L стоит на позиции 11, С(11) = 11 + 3
Буква А стоит на позиции 0, С(0) = 0 + 3
Буква Y стоит на позиции 24, С (24) = 24 + 3 = 27
Таким образом, слово PLAY, зашифрованное с ключом 3, превратится в слово SODB.
В общем случае, если х означает позицию буквы, которую мы хотим зашифровать (0 для А, 1 для В, и т. д.), позиция зашифрованной буквы [обозначаемая С(х)] выражается формулой
С(х) = (х + k) (mod n)
