ОПЕРАЦИИ ПО МОДУЛЮ
Как посчитать 231 по модулю 17 на калькуляторе?
Сначала мы разделим 231 на 17 и получим 13,58823529.
Затем найдем произведение 13 x 17 = 221. Таким образом мы избавимся от дробной части.
Наконец, найдем разность 231–221 = 10, получив остаток отделения.
Итак, 231 по модулю 17 равно 10. Этот результат записывается как 231
10 (mod 17). * * *
Математика
для расчетов на наших часах со стрелками, циферблат которых разделен на
12 частей, называется арифметикой по модулю 12. В общем случае мы
говорим, что a
b (mod m), если остаток от деления а на m равен b, при условии что а, b и m — целые числа. Число b сравнимо с остатком от деления а на m. Следующие утверждения эквивалентны:
a
b (mod m)
b
a (mod m)
а — b 0 (mod m)
а — b кратно m
Вопрос
«Которому часу на часах со стрелками соответствует время 19 часов?»
эквивалентен в математических терминах следующему вопросу: «С каким
числом сравнимо число 19 по модулю 12?» Чтобы ответить на этот вопрос,
мы должны решить уравнение
19
х (mod 12).
Разделив 19 на 12, мы получим частное 1 и остаток 7, поэтому
19
7 (mod 12).
А в случае 127 часов? Разделив 127 на 12, мы получим частное 10 и остаток 7, поэтому
127
7 (mod 12).
Чтобы повторить изученное до сих пор, давайте рассмотрим следующие операции по модулю 7:
(1) 3 + 3
6 (2) 3 + 14
3 (3) 3 х 3 = 9
2 (4) 5 x 4 = 20
6 (5) 7
0 (6) 35
0 (7) -44 = -44 + 0 = -44 + 7 х 7
5 (8) -33 = -33 + 0 = -33 + 5 x 7
2 (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
5. (8) -33 = -33 + 0; -33 + 5 x 7
2. * * *
ТАБЛИЦА УМНОЖЕНИЯ ПО МОДУЛЮ 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
18 (mod 26), а число 18 соответствует букве S.
Буква L стоит на позиции 11, С(11) = 11 + 3
14 (mod 26), а число 14 соответствует букве О.
Буква А стоит на позиции 0, С(0) = 0 + 3
3 (mod 26), а число 3 соответствует букве D.
Буква Y стоит на позиции 24, С (24) = 24 + 3 = 27
1 (mod 26), а число 1 соответствует букве В.
Таким образом, слово PLAY, зашифрованное с ключом 3, превратится в слово SODB.
В общем случае, если х означает позицию буквы, которую мы хотим зашифровать (0 для А, 1 для В, и т. д.), позиция зашифрованной буквы [обозначаемая С(х)] выражается формулой
С(х) = (х + k) (mod n),
где n — длина алфавита (26 в английском алфавите), a k — ключ, используемый в данном шифре.
Расшифровка
такого сообщения включает в себя расчеты, обратные тем, что
использовались для шифрования. В нашем примере расшифровка означает
применение формулы, обратной той, что использовалась выше:
С-1(х) = (х — k) (mod n).
В
случае сообщения SODB, зашифрованного шифром Цезаря с ключом 3 с
применением английского алфавита, то есть k = 3 и n = 26, мы получим:
С-1(х) = (х — 3) (mod 26).
Применим эту формулу следующим образом:
Для S: х = 18, С-1(18) = 18 — 3
15 (mod 26), что соответствует букве Р.
Для О: х = 14, С-1(14) = 14 — 3
11 (mod 26), что соответствует букве L.
Для D: х = 3, С-1(3) = 3–3
0 (mod 26), что соответствует букве А.
Для В: x = 1, С-1(1) = 1–3 = —2 + 26
24 (mod 26), что соответствует букве Y.
Сообщение SODB, зашифрованное шифром Цезаря с ключом 3, соответствует, как мы уже знаем, оригинальному тексту PLAY.
В
заключении нашего первого знакомства с математикой криптографии мы
рассмотрим новое преобразование, известное как аффинный шифр, частным
случаемкоторого является шифр Цезаря. Оно определяется следующим
образом:
С(a,Ь)(x) = (а∙х + b) (mod n),
где а и b — два целых числа, меньших, чем число (n) букв в алфавите. Наибольший общий делитель (НОД) чисел а и n должен быть равен 1 [НОД (а, n)
= 1], потому что иначе, как мы увидим позже, получится несколько
возможностей для шифрования одной и той же буквы. Ключ шифра
определяется парой (а, Ь). Шифр Цезаря с ключом 3 является, следовательно, аффинным шифром со значениями
а = 1 и b = 3.
Обобщенный
аффинный шифр имеет более высокий уровень безопасности, чем обычный
шифр Цезаря. Почему? Как мы видели, ключом аффинного шифра является пара
чисел (а, b). Если сообщение написано с использованием алфавита из 26 букв и зашифровано с помощью аффинного шифра, то и а, и b
могут принимать любые значения от 0 до 25. Таким образом, в этой
системе шифрования с алфавитом из 26 букв возможное количество ключей
составит 25 х 25 = 625. Заметим, что количество ключей для алфавита из n букв в n раз больше, чем в шифре Цезаря.
Это значительное улучшение, но аффинный шифр все еще возможно расшифровать методом перебора всех возможных вариантов.
* * *
НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ (НОД)
Наибольший
общий делитель двух чисел может быть найден с помощью алгоритма
Евклида. Этот алгоритм заключается в делении одного числа на другое, а
затем проведении последовательных делений предыдущего делителя на новый
остаток. Процесс заканчивается, когда остаток равен 0. Делитель
последней операции деления и будет наибольшим общим делителем данных
чисел.
Например, найдем НОД (48,30).
Разделим 48 на 30, получим остаток 18 и частное 1.
Разделим 30 на 18, получим остаток 12 и частное 1.
Разделим 18 на 12, получим остаток 6 и частное 1.
Разделим 12 на 6, получим остаток 0 и частное 2.
Мы закончили алгоритм.
НОД (48,30) = 6.
Если НОД (а, n) = 1, мы говорим, что а и n взаимно просты.
Соотношение Везу, имеющее большое значение в криптографии, устанавливает следующий факт: для двух целых чисел а и n, больших нуля, существуют целые числа k и q, такие что НОД (а, n) = kа + nq.