Математики, шпионы и хакеры. Кодирование и криптография - [8]
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. Делитель последней операции деления и будет наибольшим общим делителем данных чисел.
Многие из нас слышали о том, что современная наука уже довольно давно поставила под сомнение основные постулаты евклидовой геометрии. Но какие именно теории пришли на смену классической доктрине? На ум приходит разве что популярная теория относительности Эйнштейна. На самом деле таких революционных идей и гипотез гораздо больше. Пространство Минковского, гиперболическая геометрия Лобачевского и Бойяи, эллиптическая геометрия Римана и другие любопытные способы описания окружающего нас мира относятся к группе так называемых неевклидовых геометрий.
В книге развита теория квантового оптоэлектронного генератора (ОЭГ). Предложена модель ОЭГ на базе полуклассических уравнений лазера. При анализе доказано, что главным источником шума в ОЭГ является спонтанный шум лазера, обусловленный квантовой природой. Приводятся схемы и экспериментальные результаты исследования малошумящего ОЭГ, предназначенного для применения в различных областях военно-космической сферы.
Произведения Э. Эбботта и Д. Бюргера едины по своей тематике. Авторы в увлекательной форме с неизменным юмором вводят читателя в русло важных геометрических идей, таких, как размерность, связность, кривизна, демонстрируя абстрактные объекты в различных «житейских» ситуациях. Книга дополнена научно-популярными статьями о четвертом измерении. Ее с интересом и пользой прочтут все любители занимательной математики.
Любую задачу можно решить разными способами, однако в учебниках чаще всего предлагают только один вариант решения. Настоящее умение заключается не в том, чтобы из раза в раз использовать стандартный метод, а в том, чтобы находить наиболее подходящий, пусть даже и необычный, способ решения.В этой книге рассказывается о десяти различных стратегиях решения задач. Каждая глава начинается с описания конкретной стратегии и того, как ее можно использовать в бытовых ситуациях, а затем приводятся примеры применения такой стратегии в математике.
Давид Гильберт намеревался привести математику из методологического хаоса, в который она погрузилась в конце XIX века, к порядку посредством аксиомы, обосновавшей ее непротиворечиво и полно. В итоге этот эпохальный проект провалился, но сама попытка навсегда изменила облик всей дисциплины. Чтобы избавить математику от противоречий, сделать ее «идеальной», Гильберт исследовал ее вдоль и поперек, даже углубился в физику, чтобы предоставить квантовой механике структуру, названную позже его именем, — гильбертово пространство.
Саймон Сингх рассказывает о самых интересных эпизодах мультсериала, в которых фигурируют важнейшие математические идеи – от числа π и бесконечности до происхождения чисел и самых сложных проблем, над которыми работают современные математики.Книга будет интересна поклонникам сериала «Симпсоны» и всем, кто увлекается математикой.На русском языке публикуется впервые.
На протяжении многих веков симметрия оставалась ключевым понятием для художников, архитекторов и музыкантов, однако в XX веке ее глубинный смысл оценили также физики и математики. Именно симметрия сегодня лежит в основе таких фундаментальных физических и космологических теорий, как теория относительности, квантовая механика и теория струн. Начиная с древнего Вавилона и заканчивая самыми передовыми рубежами современной науки Иэн Стюарт, британский математик с мировым именем, прослеживает пути изучения симметрии и открытия ее основополагающих законов.