анятия под шум дождевых капель.
Итак, нам надо было найти треугольник из сел или деревень, который совпал бы на плане и на карте. По вчерашним расчётам было всего 35 троек населённых пунктов, так что нам надо было просто их перебрать. Для начала мы с Катей выписали все такие тройки. Затем мы разделили этот список: отдали первый треугольник для проверки отцу, а остальные поделили пополам, и начали проверку. Это помогло нам в два раза ускорить изучение.
Минут через двадцать Катя воскликнула:
— Есть!
Подняв голову, я увидел, что она улыбается. Она протягивала нам свою копию плана, на котором был отмечен один треугольник: Старотомниково — Новотомниково — Вислый бор. Папа угрюмо покачал головой:
— Совсем не то, что я ожидал.
Я удивился.
— Проверьте остальные тройки населённых пунктов. Вдруг там ещё что-нибудь обнаружится.
Мы быстро доделали свою работу, тем более что оставалось совсем немного. Других треугольников не нашлось. Еще я обнаружил, что один треугольник выродился в прямую, которая к тому же находилась на линии «запад — восток», а потому эти три села не подходили. Это были наше Раёво, Альдия и Старотомниково.
Я вновь спросил отца, почему он недоволен результатами поиска. Он ответил, что этот треугольник находится слишком далеко от нужной точки, поэтому могут быть большие искажения и потеря точности, когда он будет проводить преобразования. Намного лучше было бы, если бы таким треугольником оказались Благодатка — Новотомниково — Вислый бор. Но потом он сказал, что попытка — не пытка и можно попробовать.
Поскольку было ещё утро, а на улице шёл дождь, отец решил устроить нам очередное занятие. Он попросил нас вспомнить шифр на основе редкой книги. Катя сразу же достала «Тихий Дон». Тогда отец спросил:
— Видите ли вы какую-либо проблему в подобных методах шифрования?
Я начал рассуждать, что через какое-то время сложно будет подобрать неповторяющиеся числа, но отец отмахнулся и сказал, что есть ещё более глубокая проблема. Но нам с Катей в голову ничего не шло. Папа подождал немного и сказал:
— Ну что же вы? Эта проблема называется «распределением ключей».
Я хлопнул себя по лбу, Катя недоумённо посмотрела на меня, а отец сказал:
— Кирилл, поясни.
Я потёр виски и начал:
— Хорошо. Представим, что есть какой-нибудь мозговой центр, с которым связано множество шпионов, разбросанных по всему свету…
Отец замахал на меня руками, перебил и сказал:
— Так, давай попроще. Вот есть мы втроём. Рассказывай про нас.
Ну что ж. Про нас, так про нас. Я начал снова:
— Представим, что папа сидит в штабе и занимается разработкой какой-нибудь сложной стратегии по захвату мира, а нас с Катей отправил в разные концы деревни собирать информацию о том, где какие грибы растут. У нас с собой есть рации, и мы можем быть на связи. Но информация идет по открытым каналам, так что нам надо её шифровать. Следовательно, перед тем, как отправить нас в путь, папа должен и мне, и Кате выдать ключ для шифрования. Это и есть задача распределения ключей.
Отец спросил:
— И в чём же проблема? Отправляя вас в путь, я каждому выдал по книге. И возможно, даже вы с Катей используете разные книги в качестве ключей.
— В самом начале никаких проблем нет. Они начинаются, когда я, к примеру, надолго застряну где-нибудь в лесах и использую все буквы в своей книге. Тогда мне придётся вернуться и получить у тебя новую книгу. А это может быть очень долго, сложно или даже невозможно. Катя, например, свою книгу может потерять, или её у неё украдут, или ещё что-то. И тогда тоже нужно будет возвращаться за новым ключом. А ещё я могу доехать до Альдии и там завербовать кого-нибудь, чтобы он тоже присылал в штаб важную для захвата мира информацию. А у него нет ключа, и снова надо будет ехать в штаб, чтобы его получить. В общем, может быть много разных вариантов. Вот в этом-то и проблема.
Отец слушал, улыбался и кивал. Я, глядя на него, понимал, что всё говорю правильно. Когда я закончил, взял слово отец:
— Итак, проблема в том, что для того, чтобы передать ключ для шифрования, с адресатом тайной переписки надо встретиться лично. А можно ли передать ключ по открытому каналу связи так, чтобы никто, кроме того, кому этот ключ предназначен, не смог его понять?
Мы с Катей были несколько обескуражены. Отец, на наш взгляд, задал довольно странный вопрос. По открытому каналу надо передать тайную информацию. А для того, чтобы передать тайную информацию, её для начала необходимо зашифровать. А чтобы её зашифровать, необходим ключ, который известен только двум людям. Получился как будто бы замкнутый круг. В общем, мы не смогли ответить и вернули слово отцу. Он прокашлялся и начал объяснять новую тему.
— Начнём с простого. Давайте вспомним, что такое целочисленное деление. Если взять два целых числа, то одно можно поделить на другое, и в результате тоже получится два числа. Как они называются?
Такими вопросами отец всегда сбивал меня с толку. Проблема была в том, что отец пользовался совершенно другими терминами, чем те, что употребляются в школе. Мне часто было не понятно, что он имеет в виду, хотя потом оказывалось, что я ответил бы на вопрос, если бы только он задал его правильными словами. Однако вмешалась Катя:
— Если одно целое число поделить на другое целое число, то в результате получится частное и остаток. Так?
Отец согласился и записал на листке формулу:
M/N=Q, ост. P ↔ M=N*Q+P
Это было понятно. Остаток всегда меньше делителя или равен нулю, если делимое делится на делитель нацело. Отец продолжил:
— Теперь давайте изучим так называемую «модульную арифметику», или, по-другому, «арифметику остатков». Она простая, если помнить несложные правила. Самое главное правило: два целых числа равны по некоторому модулю, если остатки от деления каждого из них на этот модуль равны:
M1/N=Q1, ост. P, M2/N=Q2, ост. P ↔ M1=M2 (mod N)
— При этом нас не интересуют полученные частные. Мы будем интересоваться только остатками. Это понятно?
Я кивнул, Катя тоже. Тут действительно всё было понятно. Тем временем отец продолжал:
— Эта специальная арифметика имеет интересное свойство. Если зафиксировать делитель, для которого мы вычисляем остатки, то получается, что результаты всех операций не превышают этот делитель. Ну то есть если выбранный делитель — это число N, то все результаты любых операций будут находиться в интервале от 0 до N — 1. Что это значит?
Я больше не мог сдержаться:
— Папа, рассказывай всё от начала и до конца. Не надо спрашивать: «Что это значит» и всё такое. Нам в школе про такое не рассказывали.
— Хорошо. Тогда слушайте внимательно. Это очень важная тема. Если что-то перестаёте понимать, останавливайте меня и сразу задавайте вопросы.
Мы кивнули, и отец продолжил:
— Что ж. Поскольку у нас результаты всех операций всегда будут находиться в интервале от 0 до N — 1, при этом все такие результаты будут целыми числами, то при сложении и вычитании чисел друг из друга по заданному модулю будет происходить циклический переход. У нас получится как будто бы кольцо. Ну вот представьте себе циферблат старых часов, где стрелки ходят по кругу. Только давайте договоримся, что на месте числа 12 находится 0. Тогда это будет арифметика по какому модулю? Кирилл?
— Очевидно, 12.
— Правильно. Давайте потренируемся складывать и вычитать в этой арифметике.
Отец начал задавать нам задачи. Сперва простые:
1 + 2, 2 + 3, 7 + 4…
Потом сложнее:
7 + 5, 9 + 8, 10 + 11…
Но всё оказалось просто. Чтобы сложить два числа, надо было стрелку установить на первое, а потом перемотать её по ходу часов на столько шагов, сколько составляло второе число. Поэтому 7 + 5 = 0 (mod 12), 9 + 8 = 5 (mod 12), а 10 + 11 = 9 (mod 12). Я спросил:
— А как быть, если хочешь в этой арифметике сложить большие числа, например, 1739 и 3412?
Однако и это было несложно. Ведь каждое целое число в этой арифметике равно своему остатку от деления на модуль. То есть в нашем примере число 1739 = 11 (mod 12), а число 3412 = 4 (mod 12). Так что с такими большими числами нужно действовать чуть сложнее, но всё равно просто: 1739 + 3412 (mod 12) = 11 + 4 (mod 12) = 3 (mod 12).
Ещё больше нам с Катей понравилось, что остальные арифметические операции — вычитание, умножение и возведение в степень — они обладали в этой арифметике тем же удобным свойством: сначала каждое число можно было привести к его остатку от деления на модуль, а потом выполнить нужную операцию, после чего вновь взять остаток, если результат оказывался больше модуля. Правда, при вычитании «стрелку на часах» надо крутить в противоположную сторону, то есть против хода часов. При умножении и возведении в степень — как обычно, то есть по ходу часов.
Более того, умножение и возведение в степень стали очень простыми операциями, не требующими так много вычислений, как в обычной арифметике. Ведь умножение — это сложение числа с самим собой заданное число раз. И в этом случае число можно сложить с собой первый раз и тут же получить остаток по модулю, а в следующий раз можно прибавлять это число уже к остатку и вновь получать остаток. И так до самого результата. То же самое и с возведением в степень — поскольку надо умножить число на само себя заданное число раз, то вначале можно умножить один раз, взять остаток по модулю, и повторять до результата.
Мы с Катей потренировались и решили с десяток примеров, которые дал нам папа. В примерах были разные модули, а не только 12, как на часах, так что пришлось попотеть.
После этого отец продолжил:
— Это всё были приготовления. Теперь давайте вернёмся к проблеме, которую мы обсуждали в самом начале занятия. Есть задача секретного распределения ключей. Как с ней справиться? На помощь приходит модульная арифметика. Давайте рассмотрим пример. Возьмём модуль 13 и посмотрим, чему равны по этому модулю все степени числа 2 от нулевой до двадцатой. Кирилл, выпиши эти степени.