Тайны чисел: Математическая одиссея Сотой Маркус
Начало Симфонии № 5 Бетховена – три короткие ноты, за которыми следует длинная, – одно из самых знаменитых в истории музыки. Но почему радиостанция Би-би-си начинала каждый выпуск новостей во время Второй мировой войны с известного мотива Бетховена? Ответ состоит в том, что в нем содержалось закодированное сообщение. Этот новый код опирался на технику, умевшую посылать сигналы по проводам в виде последовательности электромагнитных импульсов.
Одним из первых людей, экспериментировавших с этим видом связи, был Карл Фридрих Гаусс. С его исследованиями по простым числам мы познакомились в главе 1. Но Гаусс интересовался не только математикой, но и физикой, включая развивавшуюся область электромагнетизма. Он и физик Вильгельм Вебер протянули километр провода от лаборатории Вебера в Гёттингене до обсерватории, где жил Гаусс, чтобы посылать сообщения друг другу.
Для этого им потребовалось разработать код. В приемной части аппаратуры имелся горизонтально расположенный постоянный магнит, к которому была прикреплена стрелка. Вокруг магнита была намотана проволочная катушка, и под действием импульсов тока, менявших направление, магнит сдвгался влево или вправо. Гаусс и Вебер придумали код, в котором буквы соответствовали комбинациям левых и правых смещений магнита (см. таблицу 4.04).
Таблица 4.04. Код Гаусса – Вебера[15]
Вебер был настолько воодушевлен потенциалом их открытия, что пророчески заявил:
Когда земной шар будет покрыт сетью железных дорог и телеграфных проводов, эта сеть будет служить человечеству подобно тому, как нервная система служит телу. Она будет использоваться и как средство транспорта, и как средство распространения идей и ощущений со скоростью света.
Для реализации потенциала электромагнетизма по передаче сообщений было предложено множество различных кодов. Однако код, разработанный американцем Сэмюэлом Морзе в 1838 г., был настолько успешен, что вытеснил все остальные. Подобно схеме Гаусса – Вебера, в нем каждая буква превращалась в комбинацию длинных и коротких импульсов электричества – тире и точек.
Рис. 4.10. Код Морзе
Логика, которой руководствовался Морзе при создании кода, в чем-то соответствует частотному анализу, используемому дешифровщиками для того, чтобы взломать шифр подстановки. Наиболее употребительные буквы английского алфавита – e и t, поэтому имеет смысл использовать максимально короткие последовательности для их кодирования. Поэтому e представляется точкой, коротким импульсом электричества, а t – тире, длинным импульсом. Для менее употребительных букв задействуются более длительные последовательности. Так, z соответствует тире-тире-точка-точка.
С помощью кода Морзе мы можем расшифровать сообщение, спрятанное в Симфонии № 5 Бетховена. Если мы интерпретируем драматичное начало этого произведения как код Морзе, то соотнесем последовательность точка-точка-точка-тире с буквой v, которой Би-би-си символизировала победу (victory).
Разумеется, Бетховен не собирался прятать в своей музыке сообщения на морзянке, ведь он умер до того, как она была изобретена. Но другие композиторы использовали ее ритмическую структуру, чтобы придать дополнительный смысл своим произведениям. Мелодия, сопровождающая знаменитый детективный сериал «Инспектор Морс» (Inspector Morse), совершенно оправданно начинается с ритмической последовательности, воспроизводящей фамилию детектива на коде Морзе:
Рис. 4.11. Код Морса
В некоторых сериях композитор даже вплел посредством морзянки имя убийцы в побочную музыкальную тему, хотя порою в партитурах встречается и ложный след.
Несмотря на то что код Морзе крайне широко использовался, причем не только композиторами, но и телеграфными операторами по всему миру, в нем имеется врожденная проблема. Если вы приняли точку, за которой следует тире, то как нужно декодировать эту последовательность? С одной стороны, она отвечает букве a, с другой стороны, это может быть буква e, за которой следует t. В результате математики предложили иной вид кода, использующий последовательности 0 и 1, который лучше подходит для восприятия машинами.
Как называется третий альбом группы Coldplay?
Когда фанаты устремились за покупкой третьего альбома группы Coldplay, выпущенного в 2005 г., они были сильно заинтригованы рисунком на обложке, пытаясь постичь его смысл. На нем были изображены расположенные на сетке разноцветные прямоугольники. В чем же заключалось значение картинки? Оказалось, она представляла название альбома, написанное с помощью одного из первых двоичных кодов, предложенного в 1870 г. французским инженером Эмилем Бодо. Цвета на рисунке не имели значения: смысл был лишь в том, что каждый прямоугольник представлял 1, а каждый пропуск нужно было истолковать как 0.
Немецкий математик XVII в. Готфрид Лейбниц одним из первых осознал приспособленность нулей и единиц к эффективному хранению информации. Он почерпнул эту идею из китайской «И цзин» – «Книги перемен», где исследуется динамический баланс противоположностей. В ней имелись 64 графических символа, называемые гексаграммами, каждый из которых представляет ту или иную ситуацию с точки зрения ее развития. Именно они побудили Лейбница создать двоичную математику (с ней мы познакомились в предыдущей главе, когда изучали выигрышную стратегию «Ним»). Каждая гексаграмма представляет стопку из шести горизонтальных линий, причем любая из линий либо цельная, либо прерванная посередине. В «И цзин» объясняется, как эти символы могут использоваться для гадания, в котором также совершаются подбрасывания монеток и веточек.
Например, если у прорицателя выпадет гексаграмма, изображенная на рис. 4.12, то она будет означать «тяжбу».
Но если линии сложатся иным образом и цельные поменяются с прерванными (рис. 4.13), то получится «поражение света».
Рис. 4.12
Рис. 4.13
Однако Лейбница больше заинтересовало то обстоятельство, что, как отметил Шао Юн, китайский философ XI в., каждому символу может быть приписано число. Если вы будете обозначать единицей сплошную линию, а нулем прерванную, то первая гексаграмма при чтении сверху вниз даст вам 111010. В числах, записанных в десятичной системе, каждый разряд соответствует степени 10, и число в этом разряде говорит вам, сколько этих степеней десяти нужно взять. Так, 234 обозначает 4 единицы, 3 десятка и 2 сотни.
Но Лейбниц и Шао Юн работали не в десятичной, а в двоичной системе, где каждый разряд соответствовал степени 2. Число 111010 в двоичной системе обозначает отсутствие единиц, одну двойку, отсутствие четверки, одну восьмерку, один набор из 16 и один набор из 32. При сложении мы получим 2 + 8 + 16 + 32 = 58. Красота двоичной записи заключается в том, что для представления любого числа нужны лишь два символа, вместо десяти в десятичной системе. Два (десятичных) набора по 16 становятся одним набором следующей степени 2, то есть 32.
Лейбниц понял, что этот способ представления чисел становится крайне действенным, если вы хотите автоматизировать вычисления. Правила сложения двоичных чисел крайне просты. В каждом разряде 0 + 1 = 1, 1 + 0 = 1 и 0 + 0 = 0. Четвертая возможность заключается в 1 + 1 = 0, что сопровождается эффектом домино – 1 переносится и прибавляется к следующему разряду слева. Например, когда мы прибавляем 1000 к 111010, то видим каскад перемещений 1 к высшим разрядам:
1000 + 111010 = 10000 + 110010 = 100000 + 100010 = 1000000 + 000010 = 1000010.
Лейбниц сконструировал великолепные механические калькуляторы. В одном из них использовались шарики для обозначения 1, а отсутствие шарика представляло 0, так что процесс сложения напоминал фантастическую машину для пинбола. Лейбниц полагал, что «не пристало одаренному человеку тратить, подобно рабу, часы на вычислительный труд, который можно надежно доверить любому лицу при использовании машин». Я думаю, что большинство математиков согласятся с этим.
Люди начали обозначать цепочками 0 и 1 не только числа, но и буквы. Хотя человеческому роду код Морзе представлялся мощным инструментом для коммуникации, машины были менее приспособлены к улавливанию тонких различий между точками и тире, прописывающими буквы, и пониманию того, когда закончилась предыдущая буква и началась следующая.
Рис. 4.14. Реконструкция двоичного калькулятора Лейбница
В 1874 г. Эмиль Бодо предложил кодировать каждую букву алфавита цепочкой из пяти нулей и единиц. Благодаря одинаковой длине обозначений всех букв стало совершенно очевидно, где заканчивалась предыдущая буква и начиналась следующая. Использование пяти 0 и 1 позволило Бодо представить в общей сложности 2 2 2 2 2 = 32 различных символа. Буква Х соответствовала цепочке 10111, а Y обозначалась как 10101. Это было огромным прорывом, потому что сообщения теперь могли кодироваться на бумажной ленте, на которойперфорировались отверстия для обозначения 1, а отсутствие отверстия соответствовало 0. Машина могла считывать эту ленту и посылать сигнал по проводному соединению с высокой скоростью, а на другом конце телетайп автоматически распечатывал сообщение.
Со временем код Бодо был вытеснен на обочину огромным разнообразием других кодов, использующих ту же идею представления всего, от текста до звуковых волн, от jpeg-изображений до видеофайлов, с помощью 0 и 1. Каждый раз, когда вы заходите на iTunes и скачиваете трек Coldplay, ваш компьютер подвергается натиску огромной армии 0 и 1, которые декодируются вашим MP3-проигрывателем. Внутри этих чисел содержатся указания, предписывающие, как вибрировать вашим колонкам или наушникам, чтобы вы могли услышать сладкий голос Криса Мартина. Наверное, то обстоятельство, что в наш цифровой век музыка представляет поток 0 и 1, и вдохновило на создание обложки третьего альбома Coldplay.
Но ключом к пониманию секретного сообщения, погруженного в рисунок на обложке, служит исходный код Бодо. Узор может быть разделен на четыре столбца с пятью блоками в каждом столбце. Окрашенные блоки нужно интерпретировать как 1, а пропуски – как 0. Поскольку порою трудно сказать, какой край ленты должен быть сверху, машина перфорирует тонкую линию, отделяющую два верхних блока от трех нижних. Вот почему на рисунке обложки видна линия, разделяющая серые и цветные блоки.
Рис. 4.15. На обложке третьего альбома группы Coldplay используется код Бодо
Блоки первого столбца обложки чередуются как цветной-пустой-цветной-цветной-цветной, что переводится в 10111, а это код Бодо для Х. Последний столбец становится кодом Бодо для Y. Два средних столбца чуть интереснее. Пять нулей и единиц дают возможность закодировать 32 символа, но очень часто требуется большее, поскольку имеются числа, знаки пунктуации и другие символы, которые также хотелось бы передать. Чтобы удовлетворить этим требованиям, Бодо нашел хитрый способ расширить допустимый диапазон. Вспомните, как на клавиатуре нажимается Shift для доступа ко всему набору символов при использовании тех же клавиш, и Бодо использовал одну из цепочек из 5 нулей и единиц в качестве эквивалента Shift. Итак, если вам встретится 11011, то следующая цепочка будет относиться к расширенному набору символов.
Этот веб-сайт позволит вам создать собственные обложки альбомов в стиле Coldplay: http://bit.ly/Coldcod.
Второй столбец на обложке как раз и представляет клавишу Shift для кода Бодо. Чтобы декодировать последовательность пустой-пустой-пустой-цветной-цветной третьего столбца, нужно обратиться к расширенному набору символов, показанному на схеме ниже. И уверен, что большинство людей ожидает увидеть символ &. Но 00011 обозначает не &, а цифру 9. Итак, настоящим названием третьего альбома Coldplay, изображенным с помощью кода Бодо, будет X9Y, а не X&Y. Подшутила ли группа Coldplay над нами? Возможно, нет. Ведь код Бодо для 9 и & различается лишь на один блок, и, скорее всего, на рисунке допущена ошибка, которая наглядно иллюстрирует проблему с многими из этих кодов: трудно сказать, совершен ли промах. Именно в детектировании подобных ошибок математика кодов в полной мере проявляет себя.
Рис. 4.16. Код Бодо
Какое из этих чисел будет кодом книги: 0521447712 или 0521095788?
Я уверен, что вы видели ISBN, Международный стандартный книжный номер (International Standard Book Number), на обложке каждой книги. Его 10 цифр однозначно идентифицируют книгу, а также сообщают о стране происхождения и об издательстве. Но это отнюдь не все, что делает код. В ISBN также встроено немного магии.
Скажем, я хочу заказать книгу и знаю ее ISBN. Я печатаю номер, но из-за спешки допускаю ошибку. Вы могли бы подумать, что у меня окажется не та книга, но этого не произойдет, потому что у ISBN есть поразительное свойство: эти номера могут детектировать ошибки внутри самих себя. Давайте я покажу, как это получается.
Вот подлинные ISBN некоторых моих любимых книг:
Таблица 4.05
Под каждой цифрой я привел результат умножения на ее порядковый номер в коде. Так, в первом ISBN 0 умножается на 1, 5 на 2, 2 на 3 и т. д. Затем я сложил все новые числа и написал полученную сумму в конце строки. Вы заметили особенность чисел, приготовленных по этому рецепту из ISBN? А вот результат вычислений с использованием некоторых других настоящих ISBN: 264, 99, 253.
Вы подметили закономерность? Расчет всегда приводит к числу, которое делится на 11. Это не чудесное совпадение, а следствие искусного математического замысла. Информация о книге содержится только в первых девяти цифрах. А десятая цифра добавляется в ISBN таким образом, чтобы результат вычислений по данному рецепту был кратен 11. Вы могли заметить, что у некоторых книг на последней позиции находится Х вместо арабской цифры. Например, у другой моей любимой книги следующий ISBN: 080501246X. X просто обозначает 10 (вспомните римские числа). В этом случае потребовалось дописать 10 в конец ISBN, чтобы результат вычисления делился на 11.
Ошибись я в одной из цифр при вводе ISBN, вычисление привело бы к результату, который не делится на 11. В таком случае компьютер будет знать, что я допустил ошибку, и мне будет предложено ввести ISBN еще раз. Даже если я переставлю местами две цифры – а люди часто допускают подобную ошибку, когда набирают номер, – то компьютер не даст команду послать мне неверную книгу, а попросит меня ввести правильный ISBN. Придумано довольно умно. Теперь вы можете проверить номера в заголовке этого раздела, чтобы определить, какой из них является настоящим ISBN, а какой – самозванцем.
Поскольку книги продолжают издаваться в больших количествах, номера ISBN начали заканчиваться. Поэтому было решено, что с 1 января 2007 г. в ISBN будет 13 цифр. 12 из них по-прежнему идентифицируют книгу, издателя и страну происхождения, а тринадцатая будет отслеживать, не вкрались ли ошибки. Но ключевым для номера ISBN теперь является делимость на 10, а не на 11. Найдите номер ISBN этой книги. В нем 13 цифр. Сложите 2, 4, 6, 8, 10 и 12-ю цифру, а сумму умножьте на 3. Теперь прибавьте к промежуточному результату все остальные цифры. Итоговый результат будет делиться на 10. Если же вы сделали ошибку при записи номера ISBN, то у вас, скорее всего, получится число, которое не делится на 10.
Как использовать коды для чтения мыслей
Для того чтобы показать этот фокус, вам понадобится 36 монет. Дайте вашему ничего не подозревающему другу 25 монет и попросите его расположить их на сетке 5 5 со случайным распределением орлов и решек. Он, к примеру, мог бы расположить монеты так:
Таблица 4.06
Потом вы говорите: «Через минуту я попрошу тебя перевернуть одну из монет, после чего я прочитаю твои мысли и скажу, какую именно ты перевернул. Ты можешь решить, что я могу запомнить порядок 25 монет, поэтому давай сделаем мою задачу еще более сложной и увеличим квадрат».
Затем вы добавляете монеты, создав дополнительный ряд и столбец, так что получается сетка 6 6. На первый взгляд вы распределяете орлы и решки случайно… хотя на самом деле это вовсе не так. Вы считаете, сколько решек имеется в каждом ряду и каждом столбце начиная с первого столбца. Если в первом столбце нечетное число решек, то положите дополнительную монету в первом столбце решкой вверх. Если же число решек четно (0 считается четным числом), то положите дополнительную монету в конец первого столбца вверх орлом.
Сделайте то же с каждым столбцом и затем добавьте монету в конец каждого ряда, используя прежний критерий. Теперь в правом нижнем углу появится ячейка, которую необходимо заполнить для завершения квадрата. Положите монету вверх орлом или решкой в зависимости от того, четное или нечетное число решек в столбце над этим углом. Интересно, что это акже зафиксирует четность или нечетность числа решек в дополнительном нижнем ряду. Вы можете доказать, что это всегда так? Прием состоит в том, чтобы заметить, что это число говорит вам, четно или нечетно количество решек во всей сетке 5 5.
Как бы то ни было, сетка теперь будет выглядеть следующим образом:
Таблица 4.07
И вы готовы показать фокус. Повернитесь спиной и попросите вашего друга перевернуть какую-либо монету. Когда это сделано, снова повернитесь лицом к монетам. Сосредоточьтесь на сетке и объявите, что вы намерены прочитать мысли друга и идентифицировать перевернутую монету.
Разумеется, вы вовсе не читаете мысли вашего друга. Вы возвращаетесь к исходному квадрату 5 5 и считаете орлы и решки в каждом ряду и столбце. Вы проверяете четность числа решек и сопоставляете ее с добавленным вами орлом или решкой, указывающими на четность в каждом столбце или ряду. Если ваш друг перевернул одну из монет на сетке 5 5, то будет один ряд и один столбец, где показания добавленных вами монет будут неправильными. Посмотрите на место пересечения этих ряда и столбца – лежащая там монета и была перевернута.
Теперь вы, скорее всего, сумеете определить, какая монета была перевернута на данной сетке:
Таблица 4.08
В первом столбце сетки 5 5 четное число решек, но добавленная вами монета лежит решкой вверх, указывая, что изначально там было нечетное число решек. Итак, монета, перевернутая вашим другом, находится в первом столбце. Перейдем теперь к рядам. Во втором ряду наблюдается рассогласование: там нечетное число решек, но ваша «контрольная цифра» говорит, что должно быть четное число. Теперь вы можете прочесть мысли вашего друга и возвестить: «Ты перевернул монету в первом столбце, во втором ряду». Вас ждет взрыв аплодисментов впечатленной публики.
Но что будет, если ваш друг перевернул одну из добавленных вами монет? Никаких проблем. Теперь нижний правый угол будет неправильно указывать на четность последнего ряда или последнего столбца. Если он не соответствует последнему ряду, то вы будете знать, что изменение произошло в последнем ряду. Поэтому вы можете проверить поочередно столбец за столбцом, чтобы понять, где произошло рассогласование. Если вы обнаружите, что несоответствие имеется в шестом столбце, значит, ваш друг перевернул монету в нижнем правом углу.
Вот опять та же сетка, где была перевернута одна из добавленных вами монет. Вы можете идентифицировать ее?
Таблица 4.09
Она находится в верхнем правом углу. Орел в нижнем правом углу говорит вам, что выше его в нижнем столбце должно быть четное число решек, но оно оказалось нечетным. Теперь выполните проверку по рядам. В первом ряду имеется рассогласование, поскольку орел в конце ряда говорит, что должно быть четное число решек слева от него. Но их нечетное число, из чего следует, что была перевернута монета в верхнем правом углу.
Подобные приемы лежат в основе так называемого кода с коррекцией ошибок, применяемого компьютерами для исправления ошибок, которые могли вкрасться в сообщения при их передаче. Замените орлы и решки на нули и единицы, и внезапно сетка становится цифровым сообщением. Например, каждый столбец в сетке 5 5, первоначально выложенной для показа фокуса, мог бы представлять букву в коде Бодо. Тогда сетка 5 5 стала бы сообщением длиной в пять букв. Дополнительные строки и столбцы добавляются компьютером для отслеживания ошибок.
Следовательно, пожелай мы отправить кодированное сообщение о третьем альбоме Coldplay, можно воспользоваться тем же приемом, что и ранее, примененным к сетке 5 4. Это даст возможность понять, где и когда вкрадываются ошибки. Вот как должно выглядеть название альбома, если цветные блоки заменить на 1, а пропуски на 0:
Таблица 4.10
Теперь добавим дополнительную строку и столбец с нулями и единицами, чтобы обозначить, четное или нечетное количество единиц имеется в каждой из строк и столбцов:
Таблица 4.11
Теперь представим, что при передаче сообщения произошла ошибка, и одно из чисел изменилось. В результате графический дизайнер получил вот что:
Таблица 4.12
Проверяя контрольные цифры в последнем столбце и строке, дизайнер может заметить ошибку. В данном случае имеется несоответствие во второй строке и в третьем столбце.
Подобные коды с коррекцией ошибок используются повсюду, от CD-дисков до связи с космическими аппаратами. Вы знаете, как бывает при разговоре по телефону, когда вы не можете разобрать все, что говорит ваш собеседник. При связи компьютеров друг с другом могут возникнуть схожие проблемы. Но использование умной математики позволило нам предложить такие варианты кодирования данных, которые помогают избавиться от этих сбоев. Именно так поступило агентство НАСА, когда космический аппарат «Вояджер-2» выслал первые фотографии Сатурна. Использование кодов с коррекцией ошибок позволило специалистам НАСА превратить неразборчивые изображения в кристально четкие.
Как честно кидать монету через интернет
Коды с коррекцией ошибок позволяют четко передавать информацию. Но зачастую мы хотим воспользоваться нашими компьютерами, чтобы поделиться секретными сведениями. Мария, королева Шотландии, лорд Нельсон или кто-либо другой, вознамерившийся обмениваться секретными сообщениями, должен был сначала встретиться со своим агентом, чтобы договориться о коде, который будут использовать обе стороны. Но в наш компьютерный век у нас то и дело появляется необходимость послать секретные сведения. При совершении покупок онлайн мы щелкаем по веб-сайтам и посылаем данные своих кредитных карт людям, с которыми никогда не встречались. Совершение сделок через интернет было бы невозможно со старой криптографией, когда требовалась первоначальная встреча с глазу на глаз. К счастью, у математики есть решение.
Чтобы объяснить его идею, давайте начнем с простого сценария. Я собираюсь играть в шахматы через интернет. Я живу в Лондоне, а мой соперник – в Токио. Мы хотим бросить монету, чтобы решить, кто будет ходить первым. «Орел или решка?» – спрашиваю я у своего соперника по электронной почте. «Орел», – отвечает он. Я подбрасываю монету и пишу: «Решка. Я начинаю». Существует ли возможность удостовериться, что я не сжульничал?
Как это ни поразительно, вы можете честно бросать монету через интернет. Такая возможность появляется благодаря математике простых чисел. Все простые числа нечетны за исключением 2 (это странное простое число, ведь лишь оно четно). Если мы разделим одно из этих нечетных простых чисел на 4, то получим в остатке 1 или 3. Например, остаток от деления 17 на 4 равен 1, а при делении 23 на 4 в остатке получается 3.
Как мы узнали в главе 1, две тысячи лет назад древние греки доказали, что существует бесконечно много простых чисел. Но существует ли бесконечно много тех из них, которые дают при делении на 4 остаток 1, или бесконечно много дающих остаток 3? Это один из тех вопросов, которые Пьер де Ферма поставил перед математиками 350 лет назад, однако ответ был дан лишь в XIX в. немецким математиком Густавом Лежёном Дирихле. Используя очень сложный математический аппарат, он сумел доказать, что половина простых чисел дает остаток 1, а другая половина 3 – никакой из остатков не оказывается предпочтительнее. Впрочем, не совсем легко понять, что математики имеют в виду под половиной, когда речь идет о бесконечном множестве. Но, по существу, это означает, что если вы возьмете простые числа, меньшие заданного большого числа, то почти в точности половина из них даст при делении на 4 остаток 1.
Итак, остаток 1 или 3 при делении простого числа на 4 не более «предвзят», чем выпадение орла или решки при подкидывании честной монеты. Для изучения нашей задачи по бросанию монеты давайте отождествим орлы с простыми числами, дающими остаток 1 при делении на 4, а с решками мы отождествим простые числа, дающие остаток 3. А теперь поледует искусный математический пассаж. Если я возьму два простых числа, скажем 17 и 41, оба из которых относятся к орлам – они дают остаток 1 при делении на 4, – и перемножу их, то произведение также будет характеризоваться остатком 1 при делении на 4. Например, 41 17 = 697 = 174 4 + 1. Если же я возьму два простых числа, скажем 23 и 43, оба из набора решек – они дают остаток 3 при делении на 4… то получится не то, чего вы могли бы ожидать. У произведения этих двух чисел при делении на 4 также будет остаток 1: в данном случае 23 43 = 989 = 247 4 + 1. Итак, произведение простых чисел не дает намека на то, взяты ли сомножители из набора орлов или из набора решек. Этим свойством мы можем воспользоваться, чтобы играть в «орла или решку по интернету».
Если я подброшу монету и выпадет орел, я выберу два простых числа из набора орлов и перемножу их. Если выпадет решка, я выберу два простых числа из набора решек и перемножу их. После того как я подкинул свою монету и сделал вычисления, я посылаю ответ моему сопернику в Токио. Оказалось, что он равен 6497. Поскольку ответ при делении на 4 всегда дает остаток 1, мой соперник не может, не зная простых чисел, сказать, выбрал ли я их из набора орлов или же из набора решек. Теперь он может сказать «орел» или «решка».
Чтобы мой соперник убедился, что он выиграл или проиграл, мне достаточно будет выслать ему два выбранных мною простых числа. В данном случае ими были 89 и 73, два простых числа из набора орлов. Поскольку никакие другие числа при перемножении не дадут 6497, то я предоставил ему достаточно информации, чтобы доказать, что я не жульничал. С другой стороны, я не предоставил ему достаточно информации, чтобы мой соперник мог жульничать.
На самом деле это не совсем верно. Если соперник сумеет разложить 6497 на простые множители 89 и 73, то он поймет, что нужно сказать «орел». Но, если я буду выбирать достаточно большие простые числа (много-много большие двузначных чисел), то будет почти невозможно даже с современными вычислительными возможностями разложить произведение на простые множители. Схожий принцип используется в кодах, которые защищают номера кредитных карт, посылаемые через интернет.
Легкое заданиеЯ бросил монету, выбрал два простых числа из набора орлов или из набора решек и перемножил их. У меня получилось число 13 068 221. Что выпало? Орел или решка? Постарайтесь найти ответ без компьютера (решение приведено в конце главы).
Трудное заданиеА что скажете, если получилось число
5 759 602 149 240 247 876 857 994 004 081 295 363 338151 725 852 938 901 132 472 828 171 992 873 665 524 051005 072 817 707 778 665 601 229 693?На этот раз можно использовать компьютер.
Почему разложение чисел означает взлом кода?
Боб – администратор веб-сайта, продающего футболки в Англии. Элис живет в Сиднее, и она намеревается купить футболку на сайте и при этом послать данные своей кредитной карты так, чтобы никто другой не смог увидеть их. Боб размещает специальное кодовое число на своем веб-сайте, скажем 126 619. Это кодовое число чем-то напоминает ключ, который запирает сообщение Элис и делает его защищенным. Поэтому, когда Элис посещает веб-сайт, она получает копию кодирующего ключа, опубликованного Бобом, и использует его, чтобы «запереть» свою кредитную карту.
В реальности компьютер Элис совершает специальное математическое вычисление, использующее этот ключ, 126 619, и номер ее кредитной карты. Теперь этот номер зашифрован и может быть послан открытым образом через интернет на веб-сайт Боба. (Детали упомянутого вычисления приведены в следующем разделе.) Но постойте, разве при этом не возникнет проблема? Предположим, я хакер. Тогда что помешает мне посетить веб-сайт Боба, получить копию кодирующего ключа и расшифровать сообщение? Однако кодирование в интернете устроено довольно интригующе: вам нужен другой ключ, чтобы отпереть дверь, а этот отпирающий ключ хранится в большом секрете в офисе Боба.
Декодирующий ключ представляет собой два простых числа, которые при умножении дают то самое число 126 619. В действительности Боб выбирает два простых числа 127 и 997, чтобы изготовить свой кодирующий ключ. Именно с помощью этих двух простых чисел Боб дешифрует то математическое вычисление, которое совершил компьютер Элис, чтобы закодировать номер ее кредитной карты. Боб поместил кодирующий ключ 126 619 на своем веб-сайте, но хранит в тайне декодирующие простые числа 127 и 997.
Если я смогу найти два простых числа, которые при умножении дают 126 619, я сумею получить доступ к номерам кредитных карт, посылаемым на веб-сайт Боба. Но 126 619 – достаточно небольшое число, чтобы я мог делить его на одно число за другим. Так, потратив не слишком много времени, я нашел бы два простых числа 127 и 997. Однако вы не сможете воспользоваться этим приемом на настоящих веб-сайтах, потому что их ключи основаны на значительно больших числах – они настолько велики, что найти пару простых чисел методом проб и ошибок почти невозможно. Математики, придумавшие эти коды, были настолько уверены в их надежности, что на протяжении многих лет предлагали приз $ 200 000 тому, кто сможет найти два простых множителя следующего числа из 617 цифр:
25 195 908 475 657 893 494 027 183 240 048 398 571 429282 126 204 032 027 777 137 836 043 662 020 707 595 556264 018 525 880 784 406 918 290 641 249 515 082 189 298559 149 176 184 502 808 489 120 072 844 992 687 392 807287 776 735 971 418 347 270 261 896 375 014 971 824 691165 077 613 379 859 095 700 097 330 459 748 808 428 401797 429 100 642 458 691 817 195 118 746 121 515 172 654632 282 216 869 987 549 182 422 433 637 259 085 141 865462 043 576 798 423 387 184 774 447 920 739 934 236 584823 824 281 198 163 815 010 674 810 451 660 377 306 056201 619 676 256 133 844 143 603 833 904 414 952 634 432190 114 657 544 454 178 424 020 924 616 515 723 350 778707 749 817 125 772 467 962 926 386 356 373 289 912 154831 438 167 899 885 040 445 364 023 527 381 951 378 636564 391 212 010 397 122 822 120 720 357.
Если вы попытаетесь взломать это число из 617 цифр, поочередно пробуя одно простое число за другим, вы переберете больше чисел, чем имеется атомов во Вселенной, до того, как доберетесь до множителей. Неудивительно, что никто не подал заявку на приз, и в 2007 г. данное предложение было снято.
Эти коды, основанные на простых числах, не только не поддаются взлому, но и обладают довольно инновационным свойством, которое решило проблему, преследовавшую все предыдущие коды. Ведь обычные коды были подобны ключу, который используется как для того, чтобы запереть дверь, так и для того, чтобы открыть ее. А изобретенные коды для интернета схожи с замком нового образца: он запирается одним ключом, а отпирается другим. Это позволяет веб-сайту свободно раздавать ключи для запирания сообщений, в то время как другой ключ, позволяющий отпирать их, хранится в большой тайне. Если вы достаточно отважны, изучите славные детали того, как на самом деле работает кодирование в интернете. Мы начнем с того, что познакомимся с любпытным калькулятором.
Что такое часовой калькулятор?
Передовые коды, которые используются в интернете, на самом деле опираются на математическое изобретение, которому сотни лет, сделанному, когда никто и не мечтал об интернете. Я имею в виду часовой калькулятор. В следующем разделе мы узнаем, как часовые калькуляторы используются при кодировании в интернете, но сначала давайте познакомимся с принципом их работы. Сперва рассмотрим случай 12-часового циферблата. Мы все знакомы со сложением на таких часах – мы понимаем, что через четыре часа после 9 будет 1 час. Это то же самое, что сложение чисел с последующим нахождением остатка при делении суммы на 12. Данное действие можно записать так:
4 + 9 = 1 (modulo 12).
Мы пишем «modulo 12», потому что 12 – это модуль, точка, после которой числа стартуют снова. Мы можем находить подобные суммы и на часах с другим количеством часовых делений, не ограничиваясь двенадцатью. Так, в случае 10 часов на циферблате:
9 + 4 = 3 (modulo 10).
А как умножаются числа на часовом калькуляторе? Умножение сводится к прибавлению определенное количество раз. Например, 4 9 означает, что нужно взять четыре девятки и сложить их вместе. Где окажется стрелка на 12-часовом циферблате после сложения четырех девяток? 9 + 9 – то же самое, что 6 часов. Каждый раз, когда мы прибавляем последующую девятку, часовая стрелка движется назад на 3 часа. В конце она окажется на 12 часах. Поскольку 0 – крайне важное число в математике, мы далее будем называть это положение, которое заканчивает круг и начинает следующий, 0 часов. Итак, у нас получится странный на вид ответ:
4 9 = 0 (modulo 12).
А как будет происходить возведение какого-либо числа в степень? Давайте рассмотрим 94, что означает перемножение четырех девяток. Мы только что научились делать модульное умножение, поэтому должны легко справиться и с этим. Поскольку числа становятся большими, будет легче взять остаток от деления на 12, чем следить за числами на часах. Начнем с 9 9, что равняется 81. Каков будет остаток при делении на 12, другими словами, чему соответствует 81 час на циферблате? Оказывается, остаток равен снова 9. Сколько бы мы ни перемножали 9, всякий раз мы опять придем к 9:
9 9 = 9 9 9 = 9 9 9 9 = 94 = 9 (modulo 12).
Ответ на часовом калькуляторе можно получить, сделав вычисления на обычном калькуляторе и затем взяв остаток от деления на число часовых делений. Но сила часового калькулятора состоит в том, что часто вам вовсе не требуется совершать вычисление на обычном калькуляторе. Вы можете найти, чему равно 799, на 12-часовом калькуляторе? Подсказка: сначала вычислите 7 7, а потом снова умножьте результат на 7. Вы видите закономерность?
Ферма сделал фундаментальное открытие о вычислениях на калькуляторе, у которого имеется простое число часовых делений. Обозначим его, к примеру, p. Ферма обнаружил, что если вы возьмете какое-то число с циферблата и возведете его в степень p, то придете к тому же числу, с которого стартовали. Это утверждение сейчас называется малой теоремой Ферма, в отличие от его знаменитой Великой теоремы.
В таблице 4.13 приведены некоторые вычисления на калькуляторах с простым и составным числом часов.
Таблица 4.13
Поскольку число 5 – простое, при возведении 2 в пятую степень на 5-часовом калькуляторе получится снова 2. Итак, 25 =2 (modulo 5). Магия будет гарантированно работать, если на калькуляторе простое число часов. Она может не удаться, если вы возьмете калькулятор с составным числом часов. Например, 6 – составное число, и на 6-часовом калькуляторе 26оказывается равным не 2, а 4.
По мере того как стрелка перемещается по часам, начинает проступать закономерность. Поскольку после p – 1 шагов мы гарантированно возвращаемся в то место, с которого стартовали, последовательность начинает повторяться через p – 1 шаг. Порою последовательность повторяется несколько раз на протяжении p – 1 шагов. Вот что мы увидим на циферблате с 13 часами, когда будем возводить 3 в последовательные степени 3, 3 и так далее вплоть до 3:
3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3.
Стрелка не посещает все деления на часах, тем не менее по-прежнему имеется повторяющаяся закономерность, которая приводит стрелку назад к 3 часам после перемножения тринадцати троек.
Мы уже сталкивались с похожей математикой в главе 3, когда рассматривали жульнический прием совершенных тасовок в покере. Там мы варьировали число карт в колоде и задавались вопросом, сколько совершенных тасовок необходимо сделать, чтобы карты возвратились к первоначальному расположению. В колоде с 2N картами порою необходимо выполнить все 2N – 2 совершенных тасовок, но бывает, их требуется сделать значительно меньше. Если в колоде 52 карты, то после всего лишь 8 совершенных тасовок они вернутся к исходному расположению. Но колода с 54 картами требует 52 совершенных тасовок.
Ферма никогда не излагал в полной мере свои рассуждения, поэтому он оставил в виде задания для будущих поколений математиков объяснение своего открытия, что магия всегда срабатывает для часов с простым числом делений. В конечном счете доказательство было найдено Леонардом Эйлером.
Малая теорема ФермаНиже приведено объяснение малой теоремы Ферма. Теорема утверждает, что в случае циферблата с простым числом p часовых делений
Ap = A (modulo p).Для понимания доказательства нужны усилия, но не специальные знания: чтобы вы могли проследить его, требуется лишь сосредоточенность.
В качестве первого шага рассмотрим простой случай. Если A = 0, то теорема верна, потому что сколько бы раз мы ни умножили 0 на себя, все равно получится 0. Поэтому давайте предположим, что А не равно нулю. Мы намереваемся показать, что произведение p – 1 множителя А равно 1. Этого достаточно для доказательства теоремы, поскольку умножение 1 на А возвратит нас к А.
Теперь давайте составим список всех часов на циферблате за исключением 0. В этом списке p – 1 элемент:
1, 2, …, p – 1.Теперь умножим каждое число в этом списке на А и получим
А 1, А 2, …, А (p – 1) (modulo p).Позвольте мне показать, что часы в этом списке будут теми же, что и в первоначальном списке 1, 2, …, p – 1, хотя они будут расположены в другом порядке. Если бы это было не так, то либо одно из произведений равнялось бы 0, либо какие-то два произведения были равны друг другу. Не может произойти что-либо другое, поскольку на циферблате имеется лишь p часов.
Предположим, что А n и А m дают один и тот же ответ на нашем p-часовом циферблате, где n и m лежат между 1 и p – 1 (я покажу, почему это означает, что n = m). Итак, А n – А m = А (n – m) равно нулю на часовом калькуляторе, то есть А (n – m) на обычном калькуляторе делится на p.
Ключевым в следующем шаге доказательства будет использование того факта, что p – простое число. Подобно химической молекуле, число А (n – m) построено из произведения атомов (простых чисел), составляющих А, и простых чисел, составляющих n – m. Но число p – простое, атом арифметики, и его нельзя расщепить далее. Поскольку А (n – m) делится на p, это число должно быть одним из атомов, использованных при построении А (n – m), ведь каждое число однозначно разлагается на простые множители. Но А не делится на p без остатка, поэтому p должно входить в список атомов, использованных при построении n – m. Другими словами, n – m делится на p. Но что это означает? Это означает, что n и m соответствуют одному и тому же времени на нашем p-часовом циферблате. Вы можете использовать схожую аргументацию, чтобы показать, что А n не может быть нулем часов, если ни А, ни n не равны нулю часов.
Заметьте, что крайне важно то, что на циферблате простое число часов. Мы уже видели, что 4 9 равняется нулю на 12-часовом калькуляторе, хотя ни 4, ни 9 не равно нулю.
Теперь у нас есть два списка – 1, 2, …, p – 1 и А 1, А 2, …, А (p – 1), – составленные из одних и тех же чисел, хотя и расположенных в разном порядке. Теперь мы можем воспользоваться эффектным трюком, который, вероятно, открыл сам Ферма. Если мы перемножим все числа в каждом из списков, то получим один и тот же ответ, потому что порядок перемножения не имеет значения. Первый список даст нам 1 2 … (p – 1), что мы можем записать как (p – 1)!. Второй список приводит к p – 1 множителю А и опять-таки произведению чисел от 1 до p – 1. После небольшой перестановки мы можем переписать это как (p – 1)! Аp – 1. И эти два ответа равны на нашем часовом калькуляторе:
(p – 1)! = (p – 1)! Аp – 1 (modulo p).Из этого следует, что (p – 1)! (1 – Аp – 1) делится на p, и мы можем использовать тот же трюк, что и ранее. Никакое из чисел 1, 2, …, p – 1 не делится на p, значит, (p – 1)! не может делиться на p. Единственная возможность состоит в том, что 1 – Аp – 1 делится на p. А это приводит к тому, что вычисление Аp – 1 на часовом калькуляторе всегда будет давать ответ 1 – предложением объяснить данный результат Ферма и раззадорил математиков.
В этой аргументации есть несколько интересных ингредиентов. Разумеется, немаловажно то обстоятельство, что если A B делится без остатка на простое число p, то либо А, либо B должно также делиться на данное простое число. Это следует из специального свойства простых чисел. Но мне представляется красивым взгляд на список 1, 2, …, p – 1 с двух различных перспектив. Для меня это образец умения рассматривать задачу с разных сторон.
Как использовать часы для отправки секретных сообщений через интернет
Мы теперь почти готовы показать, как эти часы применяются для обмена секретными сообщениями в интернете.
Когда вы покупаете что-либо на веб-сайте, номер кредитной карты кодируется вашим компьютером, который использует публичный часовой калькулятор данного веб-сайта. Итак, веб-сайт должен сообщить вашему компьютеру, сколько часов на его калькуляторе. Это первое из двух чисел, которые получает ваш компьютер. Давайте назовем его N. В нашем примере с веб-сайтом футболок, администратором которого был Боб, это число равнялось 126 619. Также для совершения вычисления вашему компьютеру требуется второе кодирующее число, которое мы назовем Е. Номер вашей кредитной карты C кодируется путем возведения его в степень Е, причем вычисления совершаются N-часовым калькулятором. Таким образом, получается закодированное число CE (modulo N), и именно его ваш компьютер посылает на веб-сайт.
Но как же веб-сайт декодирует это число? И снова магия простых чисел играет в этом ключевую роль. Давайте предположим, что N – простое число (позже мы увидим, что это не слишком подходит для надежного шифрования, зато данное предположение помогает понять, куда мы направляемся). Если мы перемножим числа CE достаточное количество раз, то чудесным образом снова появится число С. Но сколько множителей (D), каждый из которых представляет CE, мы должны взять? Другими словами, когда (CE)D = C на p-часовом калькуляторе?
Конечно, последнее равенство выполнится, если E D = p. Но p – простое число, поэтому такого числа D не может быть. Однако если мы продолжим перемножать С, то найдется другая точка, где мы гарантированно получим в ответе С. В следующий раз номер кредитной карты появится, когда мы возведем его в степень 2(p – 1) + 1. Он появится снова при возведении в степень 3(p – 1) + 1. Значит, чтобы найти декодирующее число, нам необходимо найти такое D, что E D = 1 (modulo (p – 1)). Такое уравнение значительно легче решить. Но проблема в том, что Е и p – открытые числа, поэтому хакер также может легко найти декодирующее число D. Для безопасной процедуры мы можем воспользоваться открытием, которое сделал Эйлер о часах, на которых p q, a не просто p часовых делений (p и q – простые числа).
Если вы возьмете время С на циферблате, где имеется p q часов, то через сколько шагов последовательность C, C C, C C C, … начнет повторяться? Эйлер обнаружил, что это произойдет через (p – 1) (q – 1) шагов. Итак, чтобы вернуться к первоначальному времени, нужно возвести C в степень (p – 1) (q – 1) + 1, или k (p – 1) (q – 1) + 1, где k – число повторений последовательности.
Теперь мы знаем, что для того, чтобы декодировать сообщение CE на часах с p q часовыми делениями, нам требуется найти такое декодирующее число D, что E D = 1 (modulo (p – 1) (q – 1)). Итак, нам необходимо делать вычисления на секретном часовом калькуляторе с (p – 1) (q – 1) часами. Хакер знает только числа N и Е, и он должен найти секретные простые числа p и q, чтобы получить секретный часовый калькулятор. Следовательно, взлом кодов интернета сводится к разложению числа N на простые множители. А как мы видели в разделе о подкидывании монеты через интернет, это фактически невозможно, когда числа достаточно большие.
Давайте посмотрим на коды интернета в действии, но для очень небольших p и q. Тогда нам легко будет проследить за происходящим. Пусть Боб выбрал для своего веб-сайта футболок простые числа 3 и 11, так что открытый часовой калькулятор, с помощью которого покупатели кодируют номера своих кредитных карт, имеет 33 часа. Бобхранит в тайне простые числа 3 и 11, потому что они являются ключом к декодированию сообщений. Но Боб не делает секрета из числа 33, ведь это число часов на открытом часовом калькуляторе. Вторая порция информации, которая доступна на веб-сайте Боба, – кодирующее число Е. Пусть оно равно 7. Каждый, кто покупает футболку на веб-сайте Боба, делает одно и то же: возводит номер своей кредитной карты в 7-ю степень на 33-часовом калькуляторе.
Сайт Боба посещает покупатель, который был одним из самых первых получателей кредитных карт, и ее номер равен 2. Возведите 2 в 7-ю степень на 33-часовом калькуляторе, что равно 29.
Вот умный способ вычислить 27 на 33-часовом калькуляторе. Мы начинаем с перемножения 2: 22 = 4, 23 = 8, 24 = 16, 25 = 32. Когда мы переходим к более высоким степеням 2, стрелка на циферблате движется дальше и дальше, и, когда мы возводим 2 в 6-ю степень, она совершает более чем оборот. Можно применить следующий небольшой трюк, из-за которого стрелка словно меняет направление движения, вместо того чтобы вращаться и дальше по часовой. Мы просто говорим, что 32 часа на нашем 33-часовом калькуляторе это –1 час. Потом, когда мы делаем два последующих умножения на 2, то получаем –4 часа, или 29 часов. Благодаря этому приему нам не требуется возводить 2 в 7-ю степень, что равно 128, и затем находить остаток при делении на 33. Для очень больших чисел подобный метод экономии неоценим для компьютерных вычислений, когда нужно сделать все как можно быстрее.
Рис. 4.17. Вычисление степеней 2 на 33-часовом калькуляторе
Но как мы можем быть уверены, что 29, закодированное число покупателя, надежно защищено? В конце концов, хакер может перехватить это число, когда оно путешествует по интернету. Также он может легко найти открытый ключ Боба, состоящий из 33-часового калькулятора и инструкции возвести номер кредитной карты в 7-ю степень. Все, что необходимо хакеру, чтобы взломать код, – найти число, 7-я степень которого, вычисленная на 33-часовом калькуляторе, равна 29.
Нет необходимости говорить, что это совсем нелегко. Даже при обычной арифметике, когда можно возвести число в квадрат на клапане конверта, значительно труднее совершить обратное действие и извлечь квадратный корень. При вычислении степеней на часовом калькуляторе появляется дополнительное усложнение. Очень скоро вы теряете из вида число, с которого стартовали, потому что величина ответа совершенно теряет связь с этим числом.
В нашем примере числа достаточно малы, чтобы хакер мог попытаться, пробуя различные изменения, найти ответ. Но на практике веб-сайты используют часовые калькуляторы, у которых в числе часовых делений более 100 цифр, поэтому метод перебора становится невозможным. Вы также можете задаться вопросом, каким же образом компания, ведущая продажи в интернете, извлекает номер кредитной карты покупателя, если настолько трудно решить эту задачу на 33-часовом калькуляторе?
Обобщение малой теоремы Ферма, найденное Эйлером, гарантирует существование магического декодирующего числа D. Боб может найти произведение D множителей, каждый из которых равен закодированному номеру кредитной карты, и восстановить исходный номер кредитной карты. Но вы можете определить число D, только если знаете секретные простые числа p и q. Знание этих простых чисел становится ключом к раскрытию кодов интернета, потому что вам требуется решить следующую задачу на секретном часовом калькуляторе:
E D = 1 (modulo (p – 1) (q – 1)).
Когда мы подставим наши числа, то придем к уравнению
7 D = 1 (modulo 2 10).
Значит, вопрос состоит в нахождении числа, которое при умножении на 7 дает результат, который при делении на 20 дает остаток 1. D = 3 подойдет, потому что 7 3 = 21 = 1 (modulo 20).
И, если мы возведем закодированный номер кредитной карты в третью степень, вновь появится исходный номер:
29 = 2 (modulo 33).
Возможность восстановления номера кредитной карты из закодированного сообщения зависит от знания секретных простых чисел p и q. Поэтому любому, кто захочет взломать коды из интернета, необходимо найти способ разложить число N на простые множители. Каждый раз, когда вы покупаете книгу онлайн или скачиваете музыкальный трек, вы используете магию простых чисел для защиты вашей кредитной карты.
Вопрос на миллион долларов
Те, кто придумывает коды, всегда стараются опережать взломщиков. Математики постоянно придумывают все более изощренные способы отправки секретных сообщений на случай, если когда-либо будет взломан код, основанный на простых числах. Для защиты траекторий полета самолетов уже используется новый вид кодирования, называемый эллиптической криптографией (для краткости ЭК). Приз в миллион долларов данной главы связан с пониманием математики эллиптических кривых, лежащих в основе этих новых кодов.
Существует множество различных эллиптических кривых, но все они описываются уравнениями вида y = x + ax + b. Каждая кривая соответствует различным значениям a и b: например, а = 0 и b = –2 задают y = x – 2.
Это уравнение определяет кривую, которую я могу нарисовать на миллиметровке, как показано ниже, путем нахождения последовательности точек (x, y). Я ввожу значение х, рассчитываю выражение x – 2 и беру из него квадратный корень, чтобы найти соответствующее значение y. Так, если x = 3, мы получим x – 2 = 27 – 2 = 25. Чтобы получить y, мне нужно взять квадратный корень из 25, поскольку y = x – 2. Итак, y равен 5 или –5 (потому что минус при умножении на минус дает плюс, всегда имеется два квадратных корня). Получившийся график симметричен относительно горизонтальной оси, потому что у каждого квадратного корня выше ее есть зеркальный отрицательный корень. Пока мы нашли две точки: (3, 5) и (3, –5).
Рис. 4.18. График эллиптической кривой
Эти точки на эллиптической кривой особенно приятны, потому что и х, и у являются целыми числами. Можете ли вы найти другие такие точки? Давайте попробуем подставить x = 2. Тогда x – 2 = 8–2 = 6, так что y = 6 или – 6. В первом примере у 25 был целочисленный квадратный корень, но квадратный корень из 6 не так хорош. Древние греки доказали, что не существует дроби (не говоря уже о целом числе), которая при возведении в квадрат дает 6. 6 записывается в виде десятичного числа, дробная часть которого уходит в бесконечность без появления повторяющейся последовательности:
6 = 2,449489742783178…
Вопрос на миллион долларов связан с нахождением точек на этой кривой, где и x, и y являются целыми числами или дробями. В большинстве случаев такого не происходит, потому что, когда вы подставляете х, получающееся y не будет целым числом или даже дробью, потому что у большинства чисел нет красивого квадратного корня. Нам повезло найти красивые точки (3, 5) и (3, –5) на кривой, но будут ли другие такие точки?
Древние греки нашли красивое геометрическое построение, показывающее, как получить другие точки (x, y), где и х, и y являются дробями, если вы нашли одну такую точку. Проведите прямую линию, которая слегка касается кривой в первой найденной точке – линия не должн пересекать кривую в этой точке, а проходить под правильным углом, чтобы лишь чуть скользнуть по ней, как показано на графике ниже. Мы называем такую прямую линию касательной к кривой в данной точке. Продолжая прямую, мы найдем ее пересечение с кривой в новой точке. Удивительное открытие состоит в том, что обе координаты новой точки будут дробями.
Рис. 4.19. Как найти другие точки на эллиптической кривой, координаты которых будут дробями
Например, если мы проведем касательную к эллиптической кривой y = x – 2 в точке (x, y) = (3, 5), то найдем, что она пересекает кривую в новой точке (x, y) = (129/100, 383/1000), где обе координаты являются дробями. Мы можем провести касательную и в новой точке, в результате получится еще одна точка, где х и y будут дробями:
Без этого геометрического построения было бы нелегко обнаружить, что подстановка дроби
приведет к у, который также будет дробью.
В данном случае мы можем повторять проведение касательных и получить на эллиптической кривой бесконечно много точек с координатами (x, y), задаваемыми дробями. Если вы нашли такую точку (x1, y1) на эллиптической кривой общего вида y = x – ax + b, то подстановка
и
даст вам другую точку на кривой, где x2 и y2 также будут дробями.
Эта процедура генерирует для нашей кривой y = x – 2 бесконечно много точек с координатами, являющимися дробями. Но есть такие эллиптические кривые, для которых невозможно получить бесконечно много точек с этим свойством. Рассмотрите, например, кривую, задаваемую уравнением
y = x – 43x + 166.
Оказывается, что на этой кривой имеется лишь конечное число точек, у которых x и y являются целыми числами или дробями:
(x, y) = (3, 8), (3, –8), (–5, 16), (–5, –16), (11, 32), (11, –32).
Фактически у всех этих точек целочисленные координаты. Применение геометрического построения или алгебраической подстановки для получения других точек с дробными координатами лишь снова выдаст одну из этих шести точек.
Вопрос на миллион долларов, называемый гипотезой Бёрча – Свиннертон-Дайера, состоит в том, возможно ли сказать, на какой эллиптической кривой будет бесконечно много точек, обе координаты которых являются целыми числами либо дробями.
Вы могли бы заявить: какое нам дело? Что же, это касается нас всех, потому что математика эллиптических кривых сейчас используется в мобильных телефонах и смарт-картах для защиты наших секретов, а также в системах управления воздушным движением для обеспечения нашей безопасности. С помощью этого нового вида кодирования номер вашей кредитной карты либо сообщение конвертируется умной математикой в точки на эллиптической кривой. Чтобы зашифровать сообщение, математика перемещает точки, используя геометрические построения вроде того, которое мы описали ранее, когда обсуждали генерацию новых точек.
Обращение этой геометрической процедуры требует математических действий, которые пока неподвластны нам. Но, если вы решите задачу на миллион долларов данной главы, у вас окажется подспорье для взлома этих кодов. Если вы взломаете их, вам, вероятно, не нужно будет беспокоиться о миллионе долларов, потому что вы станете самым могущественным хакером на планете.
Решения
Декодированный шифр подстановки
A mathematician, like a painter or a poet, is a maker of patterns.
If his patterns are more permanent than theirs, it is because they are made with ideas. The mathematician’s patterns, like the painter’s or the poet’s, must be beautiful; the ideas like the colours or the words, must fit together in a harmonious way. Beauty is the first test: there is no permanent place in the world for ugly mathematics[16].
Шифр таков:
Таблица 4.14
Легкое задание
Выпал орел. 13 068 221 = 3613 3617. И 3613, и 3617 – простые числа, которые дают остаток 1 при делении на 4. Существует возможность быстро разложить исходное число на множители, используя прием, найденный Ферма. Если вы возведете 3615 в квадрат, то получите 13 068 225, что на 4 больше, чем 13 068 221. 4 также является квадратом целого числа. Используйте немного алгебры, сообщающей вам, что a – b = (a + b) (a – b). Вы получите:
13 068 221 = 3615 – 2 = (3615 + 2) (3615 – 2) = 3613 3617.
Глава 5
Поиск предсказания будущего
Будь возможным путешествие во времени, стало бы легко предсказывать будущее – я просто вернулся бы из следующего года и рассказал вам, что произойдет. К сожалению, мы пока не умеем путешествовать во времени, а многие из тех способов, с помощью которых люди якобы предсказывают будущее, вроде составления гороскопов или рассматривания хрустального шара, являются абсолютной чепухой. Если вы действительно хотите знать, что произойдет завтра, в следующем году или в далеком будущем следующего тысячелетия, вашим лучшим подспорьем станет математика.
Математика может предсказать, как долго будет гореть Солнце и столкнется ли с Землей тот или иной астероид. Тем не менее даже математикам оказывается трудно спрогнозировать некоторые вещи. Например, у нас есть уравнения, описывающие погоду, рост населения и турбулентный след за футбольным мячом, движущимся в воздухе. Однако мы не знаем, как решить многие из этих уравнений. Приз в миллион долларов последней главы достанется тому, кто сумеет разобраться с уравнениями турбулентности и предсказать, что произойдет далее.
Умение математиков заглядывать в будущее наделило тех, кто понимает язык чисел, огромным могуществом. От астрономов древних времен, способных предсказать движения планет в ночном небе, до сегодняшних управляющих хедж-фондами, прогнозирующих изменения цен на фондовом рынке, – все они использовали математику, чтобы постичь будущее. Сила математики признавалась святым Августином, предупреждавшим:
Остерегайтесь математиков и всех прочих, делающих пустые пророчества. Существует опасность того, что математики уже заключили договор с дьяволом, чтобы затемнить дух и обречь человека на узы адские.
Правда, что некоторые разделы современной математики дьявольски трудны, но занимающиеся ею вовсе не стремятся держать нас во тьме неведения, а находятся в постоянном поиске новых идей, способных пролить свет на будущие события.
Как математика спасла Тинтина
В созданной Эрже книге комиксов «Храм Солнца» молодой бельгийский репортер Тинтин попадает в плен к племени инков после того, как очутился внутри храма Солнца. Инки приговаривают Тинтина и его друзей – капитана Хэддока и профессора Турнесоля – к смертной казни путем сожжения на костре. Индейцы собирались разжечь огонь с помощью увеличительного стекла, фокусирующего лучи Солнца. Но Тинтину было позволено выбрать время их смерти. Может ли Тинтин воспользоваться этой последней милостью, чтобы спасти себя и своих друзей?
Тинтин выполнил математический расчет и понял, что через несколько дней на этой части Земли должно произойти солнечное затмение, поэтому он решил выбрать время казни, совпадающее с затмением. (На самом деле вычисления сделал кто-то другой, Тинтн увидел предсказание в газетной вырезке.) За несколько мгновений до начала затмения Тинтин воскликнул: «Бог Солнца не услышит ваши молитвы! O великое Солнце, если ты желаешь, чтобы мы жили дальше, дай нам знак!» Как предсказала математика, Солнце исчезло, и повергнутое в ужас племя освободило Тинтина и его друзей.
Математика – это наука улавливания закономерностей, вот почему она наделяет нас возможностью заглянуть в будущее. Первые астрономы, наблюдающие за ночным небом, вскоре поняли, что движение Луны, Солнца и планет повторяется. Многие культуры воспользовались этими небесными закономерностями, чтобы вести счет времени. Однако имеется множество разнообразных календарей, потому что в своем небесном танце Луна и Солнце подчиняются умопомрачительному синкопированному ритму. Но все эти календари объединяет роль математики, с помощью которой постигаются циклы Луны и Солнца, используемые для измерения времени. Весьма любопытно и значение числа 19 для определения того, когда празднуются переходящие праздники, такие как Пасха.
Фундаментальная единица времени, общая для всех этих календарей, – сутки, в которых 24 часа. Но это не то время, которое требуется Земле для совершения одного оборота вокруг своей оси, – на это уходит чуть меньше, 23 часа 56 минут 4 секунды (звездные сутки). Если бы мы использовали этот чуть более короткий промежуток времени в качестве суток, у наших часов и Солнца наступала бы все большая рассинхронизация, и наконец эта ежедневная разность в 3 минуты 56 секунд накопилась бы так, что полдень наступил бы в полночь. Поэтому в целях хронометрии мы определяем сутки – или солнечные сутки, если использовать правильный термин, – как время, по прошествии которого Солнце возвращается в ту же позицию на небе для наблюдателя, находящегося в фиксированном месте на поверхности Земли. После одного оборота вокруг своей оси Земля проходит примерно 1/365 часть своей орбиты вокруг Солнца, поэтому требуется еще приблизительно 1/365 часть оборота, или 1/365 суток по времени – около 3 минут 56 секунд, – чтобы Солнце вернулось в прежнюю точку на небосводе.
Если быть более точным, Земля проходит свою орбиту вокруг Солнца за 365,2422 солнечных суток. Григорианский календарь, используемый в большинстве стран, основан на хорошем приближении этого цикла. Поскольку 0,2422 – это почти четверть, прибавляя каждый четвертый год к календарю один день, мы приходим к хорошему согласованию с движением Земли по орбите вокруг Солнца. Однако необходимы дальнейшие коррекции, ведь 0,2422 не совсем 0,25: каждый год, кратный 100, не является високосным, а раз в четыреста лет мы пропускаем пропуск и сохраняем високосный год (так было в 2000 г.).
А в исламском календаре вместо этого используются циклы Луны. В нем основной единицей является лунный месяц, а год состоит из 12 таких месяцев. Лунный месяц, начало которого определяется новолунием в Мекке, состоит из приблизительно 29,53 суток. Поэтому лунный год на 11 дней короче, чем солнечный год. Если разделить 365 на 11, то получится приблизительно 33, поэтому месяц Рамадан совершает цикл по солнечному году за 33 года. Вот почему происходит смещение Рамадана, если пользоваться григорианским календарем.
Еврейский и китайский календари объединяют движение Земли по орбите вокруг Солнца и циклы лунной орбиты вокруг Земли. Они достигают этого прибавлением високосного месяца, что в грубом приближении происходит каждый третий год. Ключом к расчетам является волшебное число 19. 19 солнечных лет (= 19 365,2422 суток) почти в точности равны 235 лунным месяцам (= 235 29,53). В китайском календаре имеется 7 високосных лет в каждом 19-летнем цикле, чтобы синхронизировать лунный и солнечный календари.
Число 19, наверное, было важным и в вычислениях Тинтина, потому что последовательность затмений Луны и Солнца также повторяется через 19 лет. Этот эпизод «Храма Солнца» основывается на знаменитом случае в истории, когда мореплаватель Христофор Колумб воспользовался лунным (а не солнечным) затмением, чтобы спасти свой экипаж, оказавшийся в трудном положении на Ямайке в 1503 г. Местные жители сначала были настроены дружелюбно, но затем стали враждебны и отказывались снабдить Колумба и его экипаж продовольствием. Над его людьми нависла угроза голода, и Колумб придумал хитрый план. Он обратился к альманаху – книге, содержавшей предсказания приливов, лунных циклов и положений звезд, которые моряки использовали для навигации, – и обнаружил, что 29 февраля 1504 г. должно состояться лунное затмение. Колумб созвал местных жителей за три дня до события и высказал угрозу: если они не обеспечат моряков провизией, то он заставит Луну исчезнуть.
Если вы знаете, когда настанет какое-либо затмение, то можете воспользоваться математическими уравнениями, чтобы определить время другого из них. Вычисления зависят от двух важных чисел. Первое из них – 29,5306, длительность синодического месяца в сутках, обозначим это число как S. Синодический месяц представляет среднее время, за которое Луна обходит вокруг Земли и возвращается к прежнему положению по отношению к Солнцу. Он совпадает со средним временем между двумя новолуниями.
Другое число (D) – драконический месяц, в котором 27,2122 суток. Плоскость орбиты Луны вокруг Земли немного наклонена по отношению к плоскости орбиты Земли вокруг Солнца (эклиптики). Две точки пересечения лунной орбиты с плоскостью эклиптики называются узлами лунной орбиты и показаны на рисунке ниже.
Рис. 5.01. Орбита Луны пересекает плоскость эклиптики в двух точках, называемых восходящим и нисходящим узлом
Драконический месяц – это среднее время, за которое Луна, начиная движение с одного из узлов, проходит другой и возвращается в прежний узел.
Предположим, вы нашли пару целых чисел A и B, таких, что A S очень близко к B D. Тогда знайте, что через A S B D дней после увиденного затмения будет другое затмение. И будет еще одно затмение спустя последующие A S B D дней. Эта последовательность затмений будет продолжаться какое-то время, но затем, поскольку уравнение не выполняется точно, затмения станут все менее впечатляющими. Наконец Солнце, Луна и Земля уже не будут расположены должным образом, что будет означать окончание данного цикла затмений.
Вот пример: A = 223 синодических месяца очень близки B = 242 драконическим месяцам, поэтому спустя каждые 223 29,5306 242 27,2122 дней после затмения будет происходить другое, почти идентичное затмение. Этот период составляет приблизительно 6585 суток, или 18 лет 11 дней и 8 часов. Сдвиг на 8 часов означает, что последующие два затмения будут видны с других территорий на поверхности Земли. Но третье из последующих затмений будет наблюдаться в том же самом месте. Поэтому повторное затмение будет происходить через 3 раза по 18 лет 11 дней и 8 часов, или приблизительно 19 756 суток.
К примеру, полное лунное затмение, наблюдавшееся в Северной Америке 21 декабря 2010 г., было повтором затмения, которое видели европейцы 9 декабря 1992 г. В предпоследний раз оно случилось в Америке 18 ноября 1956 г. Конечно, между этими датами были и другие затмения, но они принадлежали к другим циклам затмений, происходящим наряду с рассчитанным нами. Математика поможет вам вычислить дату следующего затмения в каждом из циклов.
Запасы не были принесены – местные жители не поверили, что Колумб мог заставить Луну исчезнуть. Но вечером 29 февраля, когда Луна поднялась над горизонтом, они заметили, что кусочек ее уже был выщерблен. По словам сына Колумба, Фердинанда, постепенное исчезновение Луны с ночного неба повергло туземцев в ужас, после чего «с громким завыванием и причитаниями, со всех сторон они устремились к кораблям, нагруженные продовольствием, умоляя адмирала походатайствовать перед своим богом от их имени». Основываясь на точном расчете, Колум совместил время своего прощения местных жителей с постепенным возвращением Луны. Возможно, этот рассказ апокрифичен, или приукрашен испанцами для усиления контраста между образованными европейскими завоевателями и несведущими туземцами. Но своей сущностью он демонстрирует могущество математики.
Сила математики в части предсказания событий в ночном небе основывается на улавливании повторяющихся закономерностей. Но как мы можем предугадать что-либо новое? Рассказ о том, как использовать уравнения математики, чтобы заглянуть в будущее, начинается с предсказания поведения простых предметов, таких как футбольный мяч.
Что первым долетит до земли, если я уроню перышко и футбольный мяч?
Разумеется, футбольный мяч. Не нужно быть математиком мирового уровня, чтобы предсказать это. Но что будет, если я уроню два футбольных мяча одинакового диаметра, один из которых наполнен свинцом, а другой воздухом? Первой мыслью большинства людей будет то, что мяч со свинцом первым коснется земли. Именно так полагал Аристотель, один из величайших мыслителей всех времен.
Своим апокрифическим экспериментом итальянский ученый Галилео Галилей показал, что интуитивный ответ совершенно неверен. Галилей работал в Пизе, где находится всемирно известная падающая башня. Нет удобнее места, чтобы одновременно уронить два предмета, а стоящий внизу ученик посмотрел, какой из них приземлится первым. Галилей доказал, что Аристотель ошибался: оба мяча, хотя они и разной массы, ударятся о землю одновременно.
Галилей понял, что масса предмета не имела значения. Перо падало медленнее, чем мяч, из-за сопротивления воздуха, и, если удастся устранить воздух, перо и мяч упадут за одно время. Найдется и место, где можно проверить эту теорию, – поверхность безвоздушной Луны. В 1971 г. командир экипажа корабля «Аполлон-15» Дэвид Скотт воспроизвел эксперимент Галилея на поверхности Луны, одновременно уронив геологический молоток и перо сокола. Они падали значительно медленнее, чем на Земле, из-за меньшего гравитационного притяжения Луны, но оба предмета упали на поверхность одновременно, как и предсказывал Галилей.
Как позднее сказал диспетчер из Центра управления полетом, этот результат «был обнадеживающим, особенно если учесть, что за экспериментом наблюдало огромное количество зрителей, а успешное возвращение экипажа домой критическим образом зависело от истинности испытуемой теории». Это безусловно верно: космические полеты было бы невозможно планировать без математических уравнений, предсказывающих траекторию полета космического корабля, на который действует притяжение Земли, Солнца, Луны и планет, а также тяга его двигателей.
Воспроизведенный агентством НАСА эксперимент Галилея на поверхности Луны можно увидеть, пройдя по ссылке http://bit.ly/Galileoprediction.
После того как Галилей обнаружил, что масса падающего объекта не влияет на его скорость, он заинтересовался, можно ли предсказать, за какое время тело долетит до земли. Но предметы падали настолько быстро с вершины Пизанской башни, что не удавалось точно засечь время, поэтому Галилей решил скатывать шары по наклонной плоскости, чтобы увидеть, как изменяется их скорость. Он обнаружил, что если скатывающийся шар проходил 1 меру длины за 1 секунду, то за 2 секунды он проходил 4 меры длины, а за 3 секунды – 9 мер. После этого Галилей мог предсказать, что за 4 секунды шар должен преодолеть 16 мер длины, – другими словами, расстояние, проходимое падающим телом, пропорционально квадрату времени падения. Если воспользоваться математической символикой,
d = gt,
где d – проходимое расстояние, а t – время падения. Множитель g, отвечающий ускорению, обусловленному гравитацией, говорил Галилею о том, насколько менялась скорость падающего предмета за каждую секунду. Если уронить футбольный мяч с вершины Пизанской падающей башни, то через 1 секунду его скорость будет g, через 2 секунды 2g и т. д. Формула Галилея была одним из первых примеров того, как математическое уравнение может быть использовано для описания природы, что впоследствии будет называться законом физики.
Такое применение математики революционизировало методику нашего понимания мира. До того люди использовали повседневный язык для описания природы, что бывает довольно расплывчатым – вы могли бы сообщить, что какой-то предмет падает, но не могли бы сказать, когда он приземлится. Посредством языка математики люди могут не только более точно описывать природу, но и предсказывать, как она будет себя вести в будущем.
Когда Галилей разобрался с тем, что происходит с падающим мячом, его следующим шагом стало предсказание того, что случится, когда мяч пинают.
Почему Уэйн Руни решает квадратное уравнение всякий раз, когда забивает гол с лета?
«Бекхэм подает со штрафного, Руни идеально рассчитал время для нанесения удара с лета… Гол!!!»
Читать бесплатно другие книги:
