Текст книги "Это база: Зачем нужна математика в повседневной жизни"

Цикл обмена почками длины 3

Следующий, более сложный тип обмена – цикл длины 3. Здесь присутствует третья пара с донором Карлом и реципиентом Кэрол. Предположим, что

 
Альберт совместим с Бернардом;
Берил совместима с Кэрол;
Карл совместим с Амелией.
 

Тогда хирурги могут предложить, чтобы почка Альберта досталась Бернарду, почка Берил – Кэрол, а почка Карла – Амелии. Это опять приемлемый вариант для большинства доноров.

С донорами-альтруистами вроде Зои работать приходится немного иначе, потому что они изначально ни с кем не связаны и у них нет пары. И здесь на сцену выходит небольшой математический фокус. Мы формируем соответствующую вершину графа, поставив в пару к Зои загадочного неизвестного реципиента, обозначив его подписью «кто угодно», и считаем этого реципиента совместимым с любым из наших неальтруистических доноров. На практике этот псевдореципиент представляет всех стоящих в списке ожидания при условии, что каждый из них совместим с кем-то из неальтруистических доноров. Это вполне реально, поскольку список ожидания велик. Теперь мы проводим стрелку от

вершины-Z = (Зои, кто угодно)

к любой вершине, реципиент которой совместим с Зои. Для последовательной цепочки домино, описанной выше, получаем орграф на рисунке ниже.

Подобные цепочки непрактичны: для реализации данного варианта потребовалось бы 10 одновременно оперирующих хирургов. Операции должны проводиться одновременно, иначе, скажем, как только Кэрол получит почку от Берил, Карл может передумать и отказаться отдавать свою почку Дейдре. Люди не всегда выполняют свои обещания, если теряется выгода, даже после подписания необходимых юридических документов. При желании всегда можно найти предлог. Сказаться больным или еще что-нибудь. Сломать ногу.

Эта цепочка слишком длинная, чтобы быть практичной

По этой причине обмены в настоящее время законодательно ограничиваются четырьмя сценариями: это циклы длины 2 и 3, которые мы уже видели, и соответствующие им циклы с участием донора-альтруиста, которые называются короткими и длинными цепочками. В короткой цепочке были бы задействованы только Зои, Альберт, Амелия и кто-то из списка ожидания. В длинную цепочку были бы включены еще Берил и Бернард. Под обменом понимается любой из этих четырех сценариев.

Обратите внимание на небольшое лукавство. Я показал эту цепочку как цикл с пятью вершинами. При реализации обмена это не совсем так, потому что у Зои нет конкретного реципиента. Зои готова уступить свою почку любому, и в конце цепочки Дайана действительно отдает почку любому (то есть списку ожидания в целом). Но на самом деле «кто угодно», кому уступает почку Зои, оказывается Амелией, и это не тот же самый человек, кому жертвует в конечном итоге последний в цепочке – Дайана. С этим помогает разобраться математика, потому что в каждом случае мы определяем занимающего позицию «кто угодно» из структуры орграфа.

Орграф обмена почками, использовавшийся в июле 2015 года, и оптимальное решение (показано сплошными черными линиями). Белые точки – доноры и реципиенты, не имеющие пары, серые точки – доноры-альтруисты, черные точки – доноры и реципиенты, получившие пару[5]5
  Tommy Muggleton (перерисовка).


[Закрыть]

В приведенных выше орграфах отдельные циклы и цепочки показаны при помощи небольшого числа вершин и стрелок. В реальности пар много, доноров-альтруистов заметно меньше, а вот стрелок просто громадное количество. Это происходит потому, что орграф должен иметь стрелку между двумя любыми вершинами X и Y, где донор X совместим с реципиентом Y. Один и тот же донор может быть совместим со множеством реципиентов. Например, в октябре 2017 года было зарегистрировано 226 неальтруистических пар и 9 доноров-альтруистов, между которыми было проведено в совокупности 5964 стрелки. Рисунок иллюстрирует сложность структуры на другую дату. Математическая задача состоит в том, чтобы найти в этом орграфе не просто один обмен, а наилучшее возможное подмножество обменов.

* * *

Чтобы решить эту задачу математически, необходимо точно определить понятие «наилучший возможный». Это не просто множество обменов, при котором задействовано максимальное число людей. Есть и другие соображения, такие как стоимость и вероятный процент успеха. Здесь в дело вступают медицинская консультация и опыт. Служба переливания крови и трансплантации Министерства здравоохранения Великобритании (NHSBT) разработала стандартную систему количественной оценки пользы от каждой пересадки органа. Во внимание принимаются такие факторы, как срок ожидания пациента в очереди, уровни несовместимости по типу тканей и разница в возрасте между донором и реципиентом. При помощи статистического анализа эти факторы собираются в единую числовую оценку – действительное число, которое называют весом. Вес вычисляется для каждой стрелки на орграфе, то есть для каждой потенциальной пересадки.

Имеется одно очевидное условие: одна и та же вершина графа не может быть задействована в двух цепочках, поскольку невозможно отдать одну и ту же почку двум людям. Математически это равноценно утверждению, что циклы, составляющие множество, не пересекаются. Остальные условия тоньше. Некоторые циклы длины 3 имеют дополнительную полезную черту: лишнюю стрелку в обратном направлении между двумя вершинами. На рисунке показан случай, когда, помимо стрелок предыдущего цикла длины 3, в цикле имеется еще одна от пары Берил к паре Амелии. Это означает, что Берил совместима не только с Кэрол, но и с Амелией. Если где-то на поздней стадии Карл вдруг выпадет из договоренности по обмену, то Кэрол тоже можно исключить; останется цикл длины 2, в котором Альберт передает почку Бернарду, а Берил – Амелии, и этот обмен по-прежнему может быть реализован. Математически эти три вершины образуют цикл длины 3, и дополнительно две из его вершин образуют цикл длины 2. Подобная дополнительная стрелка называется обратной дугой. Любой цикл длины 3 с обратной дугой и циклом длины 2 называется эффективным циклом длины 2.

Согласно определению Консультативной группы по почкам при NHSBT, множество обменов почками является оптимальным, если оно:

(1) максимизирует число эффективных циклов длины 2;

(2) содержит как можно больше циклов, при выполнении условия (1);

(3) использует как можно меньше циклов длины 3, при выполнении условий (1) и (2);

(4) максимизирует число обратных дуг, при выполнении условий (1)–(3);

(5) максимизирует суммарный вес всех циклов, при выполнении условий (1)–(4).

Эффективный цикл длины 2

Интуитивно понятно, что это определение отдает приоритет определенным моментам, а когда выполнено главное условие, в дело последовательно вступают остальные, с более низким приоритетом. Например, условие (1) гарантирует, что включение в схему трехсторонних обменов не уменьшит число двухсторонних обменов, которые могли бы быть сделаны. Такой подход обеспечивает, во-первых, простоту, а во-вторых – возможность продолжать с циклом длины 2, если кто-то вдруг выпадет из схемы. Условие (5) означает, что множество обменов должно быть как можно более эффективным и иметь максимальную вероятность успеха, но начинать думать об этом можно только после того, как приняты главные решения по пунктам (1)–(4).

Математическая задача состоит в том, чтобы найти оптимальное множество обменов, соответствующее данным критериям. Если немного подумать и прикинуть цифры, несложно понять, что проверить все возможные множества обменов нереально. Их попросту слишком много. Допустим, у нас имеется 250 вершин и 5000 ребер. В среднем с каждой вершиной связано 20 ребер, и для упрощения оценки будем считать, что 10 из них в эту вершину входят, а 10 – выходят. Предположим, мы хотим найти все возможные циклы длины 2. Выберем какую-нибудь вершину и пройдем вдоль 10 выходящих из нее стрелочек. Каждая стрелочка заканчивается у другой вершины, из которой тоже выходит 10 стрелочек. Мы получаем цикл длины 2, если конечная вершина после этого совпадет с начальной. Получаем 100 вариантов для проверки. Для нахождения цикла длины 3 необходимо проверить 100 × 10 = 1000 вариантов, а это означает 1100 проверок на каждую вершину. Вершин у нас 250, то есть проверять нужно 275 000 вариантов, если не учитывать упрощения, которые, конечно, могут снизить число проверок, но не изменят общего порядка величины.

Однако, даже если все получилось, вам на данный момент удалось всего лишь составить список возможных циклов длины 2 и 3. Обмен – это множество циклов, и число множеств растет экспоненциально с ростом числа циклов. В октябре 2017 года в орграфе были 381 цикл длины 2 и 3815 циклов длины 3. Число наборов из одних только циклов длины 2 составляет 2³⁸¹, а это число с 115 знаками. Число наборов из циклов длины 3 имеет 1149 знаков. А мы еще даже не проверили, какие из множеств не имеют пересечений.

Вряд ли стоит пояснять, что на самом деле эту задачу решают не так. Но из приведенных данных понятно, что для этого необходимо придумать какие-то достаточно эффективные методы. Я лишь набросаю некоторые из задействованных в решении идей. Вообще, все это можно рассматривать как разновидность пресловутой задачи коммивояжера: как задачу комбинаторной оптимизации с другими, конечно, ограничениями, но аналогичными рассуждениями. Принципиально важно, сколько времени требуется на поиск оптимального решения. Эту стратегию можно исследовать с точки зрения вычислительной сложности, как в главе 3.

Если в схеме участвуют только циклы длины 2, то оптимальное множество обменов может быть вычислено за полиномиальное время, класс сложности P, с использованием стандартных методов построения паросочетаний с максимальным весом в графе. Если присутствуют и циклы длины 3, даже без доноров-альтруистов, задача оптимизации становится NP-трудной. Тем не менее Мэнлав с коллегами разработал работоспособный алгоритм на базе линейного программирования, о котором мы говорили в главе 3. Их алгоритм UKLKSS перестраивает задачу оптимизации так, чтобы ее можно решить при помощи последовательности вычислений по методу линейного программирования. Результат каждого расчета подается на вход следующего как дополнительное ограничение. Так что условие (1) оптимизируется; при этом используется метод, известный как алгоритм Эдмондса в реализации Сильвио Микали и Виджая Вазирани. Алгоритм Эдмондса находит максимальное покрытие в графе за время, пропорциональное числу ребер, умноженному на квадратный корень из числа вершин. Покрытие связывает пары вершин на концах общего ребра, и задача в том, чтобы покрыть как можно большее число пар вершин без использования двух ребер, которые имеют одну общую вершину.

После того как оптимизация по условию (1) проведена, полученное решение оптимизируется по условию (2) с использованием алгоритма, известного как целочисленный программный решатель COIN-Cbc, части библиотеки алгоритмов проекта Вычислительной инфраструктуры для исследования операций, и т. д.

К концу 2017 года при помощи этих методов теории графов было найдено 1278 потенциальных вариантов пересадки, но реализовали только 760 из них, потому что на последних этапах оценки вылезают разные проблемы: выясняется, например, что типы тканей не так хорошо совместимы, как считалось ранее, или что доноры или реципиенты по состоянию здоровья не могут выдержать операции. Однако систематическое использование алгоритмов из теории графов для эффективной организации пересадки почек – серьезный шаг вперед по сравнению с прежними методами. Кроме того, это указывает нам путь к дальнейшим усовершенствованиям, поскольку сегодня мы можем хранить почки вне тела дольше, так что все операции в цепочке не обязательно проводить в один день. Теперь можно задуматься и о более длинных цепочках, а это ставит перед нами новые математические задачи.

Я не пытаюсь утверждать, что Эйлер умел предвидеть будущее. Он, конечно, не думал, что его остроумное решение глупой головоломки когда-нибудь пригодится в медицине. И уж точно он не мог предположить, что оно найдет применение в трансплантологии – ведь в те времена хирургия не слишком отличалась от ремесла мясников. Но я хочу отдать ему должное – даже в те далекие дни он видел, что эта головоломка намекает математикам на нечто более глубокое, и прямо говорил об этом. Взгляните на эпиграф к этой главе. Эйлер неоднократно упоминает «геометрию положения» в контексте данной задачи. Это понятие он обозначает на латыни как analysis situs и отдает Лейбницу честь изобретения термина и, косвенно, осознания того, что такой предмет может оказаться важен. Самого Эйлера, очевидно, заинтриговала идея геометрии, имеющей дело не с традиционными евклидовыми фигурами. Он не отвергает эту идею из-за ее неортодоксальности, совсем наоборот. Ему приятно внести свой вклад в развитие такой геометрии. Он развлекается.

Мечта Лейбница осуществилась в XX веке после весьма существенных достижений XIX века. Мы сегодня называем эту область математики топологией, и в главе 13 я покажу некоторые ее новые применения. Теория графов по-прежнему не теряет связи с топологией, но их развитие шло разными путями. Такие понятия, как вес ребра, имеют численный, а не топологический характер. Но идея о том, что графы можно использовать для моделирования сложных взаимодействующих систем и решения задач оптимизации, восходит к Эйлеру. Он занялся вопросами нового типа потому, что они захватили его воображение, и придумал собственные способы поиска ответов на них. Произошло это в Санкт-Петербурге, в России, куда он приехал по приглашению недавно созданной Академии наук почти три столетия назад. Всякий, кому пересаживают почку, будь то в Великобритании или в любой другой стране, где пользуются методами теории графов для более эффективного распределения органов, должен восхищаться тем, что сделал Эйлер.

5
Будьте осторожны в киберпространстве

Никому еще не удалось обнаружить ни одну военную или имеющую отношение к войне задачу, которой служила бы теория чисел или теория относительности, и маловероятно, что кому-нибудь удастся обнаружить нечто подобное, на сколько бы лет мы ни заглядывали в будущее.

ГОДФРИ ХАРОЛЬД ХАРДИ.

Апология математика (1940)

Пьер де Ферма знаменит своей Великой теоремой, которая гласит, что если n равно по крайней мере 3, то сумма двух n-х степеней целых чисел не может также быть n-й степенью целого числа. Эндрю Уайлс в конечном итоге нашел этому современное формальное доказательство в 1995 году, примерно 358 лет спустя после того, как Ферма высказал свою гипотезу{39}39
  Точная дата, когда Ферма сформулировал свою Великую теорему, наверняка неизвестна, но обычно считают, что это произошло в 1637 году.


[Закрыть]. По профессии Ферма был юристом, советником парламента в Тулузе, но большую часть времени посвящал математике. У него был друг по имени Френикль де Бесси, парижский математик, известный прежде всего полным каталогом 880 магических квадратов четвертого порядка. Они активно переписывались, и 18 октября 1640 года Ферма написал де Бесси (по-французски), что «каждое простое число делит… одну из степеней любой прогрессии за вычетом единицы, а показатель этой степени делит данное простое число за вычетом единицы».

Если перевести этот текст на алгебраический язык, то Ферма утверждал, что если p – простое число и a – произвольное число, то a^p–1–1 делится на p (без остатка). Например, поскольку 17 – простое число, то, согласно его утверждению, все числа

1¹⁶–1 2¹⁶–1 3¹⁶–1 … 16¹⁶–1 18¹⁶–1…

кратны 17. Очевидно, 17¹⁶–1 придется пропустить: это число никак не может быть кратно 17, поскольку оно на единицу меньше такого числа, а именно 17¹⁶. Ферма понимал, что такое дополнительное условие необходимо, но не упомянул этого в письме. Проверим такой случай:

16¹⁶–1 = 18 446 744 073 709 551 615

и, разделив это число на 17, получим 1 085 102 592 571 150 095 ровно. Как вам такое?

Этот любопытный факт в настоящее время называют Малой теоремой Ферма, в отличие от Последней (или Великой) теоремы. Ферма был одним из пионеров теории чисел, изучающей глубокие свойства целых чисел. Как в его время, так и в последующие три столетия теория чисел представляла собой самую что ни на есть чистую математику. Она не имела важных применений, и было непохоже, чтобы они когда-нибудь появились. Один из ведущих специалистов Великобритании по чистой математике Годфри Харольд Харди, несомненно, думал именно так, о чем и заявил в своем небольшом шедевре – эссе «Апология математика», опубликованном в 1940 году. Теория чисел была для Харди одной из любимых областей математики, и в 1938 году он вместе с Эдвардом Мейтлендом Райтом выпустил классический труд «Введение в теорию чисел». В нем можно найти и Малую теорему Ферма – это Теорема 71 в главе VI. Мало того, вся глава, по существу, рассказывает о ее следствиях.

Политические и математические взгляды Харди отражали веяния, преобладавшие в то время в высших кругах академического сообщества, и сегодня представляются в значительной мере предвзятыми, но стиль изложения у него легок и элегантен, а кроме того, его статьи позволяют лучше понять академический менталитет тех времен, что тоже весьма ценно. Некоторые из изложенных им взглядов актуальны и сегодня. Харди говорил, что «писать о математике – сплошная тоска для профессионального математика. Математик должен делать что-то значимое, доказывать новые теоремы, чтобы расширять математические знания, а не рассказывать о том, что сделал он сам или другие математики». Такой вот своеобразный подход к «распространению знаний», так высоко ценимому сегодня в академическом мире, но именно он превалировал в общении с неспециалистами еще 40 лет назад.

Одна из причин, по которым Харди считал необходимым оправдывать свою профессию перед публикой, была в том, что, по его мнению, математика того сорта, которой он посвятил свою жизнь, никогда не имела полезных приложений и перспектив их обрести. Математика не оправдывала себя. Интерес Харди к ней был чисто интеллектуальным: удовлетворение от решения сложных задач и расширение абстрактного человеческого знания. Его не особенно беспокоила утилитарная полезность математики, но он испытывал по этому поводу легкое чувство вины. Однако его, как убежденного пацифиста, тревожила возможность использования математики в военных целях. Бушевала Вторая мировая война, а некоторые области математики всегда применялись в военном деле. Архимед, как говорят, использовал свойства параболы, чтобы сфокусировать солнечные лучи на вражеских кораблях и поджечь их, а рычаги – чтобы сконструировать громадную лапу, способную вытащить корабль из воды. Баллистика позволяет нам прицельно метать предметы – от каменных ядер до разрывных снарядов. Ракеты и дроны не могут достичь цели без помощи сложной математики, в частности теории управления. Но Харди был убежден, что его любимая теория чисел никогда – по крайней мере, еще очень-очень долго – не будет иметь военного применения, и гордился этим.

* * *

Харди писал в то время, когда типичный кембриджский «дон» (преподаватель) тратил около четырех часов в день на научные изыскания и, может быть, часок на работу со студентами, а остальное время отдыхал, заряжая свои интеллектуальные батарейки. Он смотрел крикет и читал газеты. Ему, по всей видимости, просто не приходило в голову, что даже ведущий математик-исследователь мог бы использовать свободное время с пользой и рассказывать неспециалистам, чем в настоящее время занимаются математики. Это позволило бы творить новую математику и параллельно писать о ней. Именно этим многие из нас, профессиональных математиков, занимаются сегодня.

Общее утверждение Харди о том, что значительная доля чистой математики не имеет практического применения и, вероятно, никогда не найдет его, остается верным{40}40
  То же можно сказать и о значительной части прикладной математики. Однако здесь есть разница: отношение самого математика. В чистой математике движущей силой является внутренняя логика предмета: не просто обезьянье любопытство, а поиск структуры и чувство того, где в наших представлениях имеются серьезные пробелы. В прикладной математике движущей силой служат в основном задачи, возникающие в «реальном мире», но сама она лучше переносит необоснованные сокращения и аппроксимации при поиске ответа, а ответ может иметь или не иметь практических следствий. Однако, как показывает эта глава, тема, которая в какой-то момент кажется совершенно бесполезной, может внезапно обрести громадное значение в практических вопросах в ходе серьезных изменений в культуре или технике. Более того, математика представляет собой внутренне взаимосвязанное целое, даже деление на чистую и прикладную искусственно. Теорема, которая кажется бесполезной сама по себе, может вдохновить или повлечь за собой результаты огромной практической важности.


[Закрыть]. Но вот при выборе конкретных примеров бесполезных тем он сильно рисковал попасть впросак. Сказав, что теория чисел и теория относительности еще много лет не смогут послужить никакой военной цели, он, что называется, попал пальцем в небо, хотя нужно признать, что его предсказание не исключало подобное применение полностью. Очень трудно решить заранее, какие идеи найдут применение, а какие нет. Научитесь делать это, и вы сможете без труда разбогатеть. Интересно, что именно те области, которые не кажутся практически применимыми, могут внезапно выскочить на передний план в промышленности, коммерции и, к несчастью, в военном деле. Именно это произошло с теорией чисел и конкретно с Малой теоремой Ферма, которая теперь стала основой того, что мы считаем абсолютно стойкими шифрами.

Ирония ситуации в том, что за два года до того, как Харди написал свою «Апологию…», глава британской контрразведки MI6 купил поместье Блетчли-парк, в котором в будущем должна была разместиться Правительственная школа кодирования и шифрования, секретный дешифровальный центр cоюзников во время Второй мировой войны. Там, как известно, криптоаналитики взломали шифр машины Enigma, которую Германия использовала в военных целях, и ряд других шифровальных систем стран Оси. Самый известный сотрудник Блетчли-парка Алан Тьюринг начал обучение в 1938 году и прибыл в школу в день объявления войны. Криптоаналитики Блетчли-парка использовали для взлома германских шифров неординарные подходы и математику, в том числе и идеи из теории чисел. Всего лишь через неполные 40 лет после этого произошла настоящая революция в криптографии, фундаментом которой стала теория чисел. Естественно, для новой криптографии нашлось не только гражданское, но и военное применение. Вскоре она приобрела принципиально важное значение для работы интернета. Сегодня мы сильно зависим от нее, по большей части даже не сознавая, что она существует.

Теория относительности тоже нашла свое место не только в гражданской, но и в военной сфере. Можно сказать, что она сыграла определенную роль в реализации Манхэттенского проекта по созданию атомной бомбы. В соответствии с популярной легендой, знаменитая формула Эйнштейна E = mc² убедила физиков, что в небольшом количестве вещества содержится громадное количество энергии. Это, конечно, сильное упрощение, которое использовалось после ударов по Хиросиме и Нагасаки для объяснения публике принципа действия такого оружия. Не исключено, что таким образом пытались также отвлечь внимание от настоящего секрета: физики ядерных реакций. Более близкий к нам пример – Глобальная система позиционирования, GPS (глава 11), точность которой зависит как от специальной, так и от общей теории относительности. Разработка системы финансировалась американскими военными, а сама она первоначально предназначалась исключительно для них.

Счет 2:0 в пользу военных.

Я совершенно не виню Харди. Он понятия не имел, что происходит в Блетчли-парке, и едва ли мог предугадать стремительный взлет цифровых вычислений и средств связи. Слово «цифровой» означает в основном работу с целыми числами, а ведь именно этим занимается теория чисел. Внезапно оказалось, что результаты, полученные многими поколениями специалистов по чистой математике исключительно из интеллектуального любопытства, теперь можно использовать для инновационной технологии. Сегодня в электронных устройствах, которые четверть рода человеческого ежедневно носит с собой, воплощен огромный пласт математики – и это не только теория чисел, но и многое другое, от комбинаторики до абстрактной алгебры и функционального анализа. Секретность онлайн-операций, осуществляемых частными лицами, компаниями, а также военными, обеспечивается хитроумными математическими преобразованиями, основанными на столь любимой Харди теории чисел. Это совсем не удивило бы Тьюринга, который был настолько впереди всех, что уже в 1950 году всерьез задумывался об искусственном интеллекте. Но Тьюринг был мечтателем. В те времена это было даже не научной фантастикой, а просто фантазией.

* * *

Код, или шифр, – это метод преобразования сообщения на обычном языке, то есть открытого текста, в зашифрованный текст, который выглядит как тарабарщина. При этом преобразовании, как правило, используется ключ – принципиально важная часть информации, которую держат в секрете. Говорят, например, что Юлий Цезарь пользовался шифром, в котором каждая буква алфавита сдвигалась на три позиции. «Три» здесь и есть ключ. Такой тип шифра подстановки, в котором каждая буква алфавита заменяется на другую букву по постоянному правилу, несложно взломать, если в вашем распоряжении имеется достаточное количество шифровок. Для этого достаточно знать частоты, с которыми буквы алфавита встречаются в открытом тексте. Тогда можно сделать достаточно достоверное предположение о принципе шифрования и проверить его. Поначалу будут встречаться ошибки, но если часть текста вдруг расшифруется как JULFUS CAESAR, то легко догадаться, что на месте F должна быть I.

Каким бы простым и ненадежным ни казался шифр Цезаря, он служит хорошим примером для иллюстрации общего принципа, который до недавнего времени лежал в основе практически всех систем шифрования. Это симметричный шифр, то есть и отправитель, и получатель пользуются, по существу, одним и тем же ключом. Я говорю «по существу», потому что они пользуются им по-разному: Юлий сдвигает алфавит на три позиции вправо, а получатель сдвигает его на три позиции в обратном направлении. Однако если вы знаете, как ключ используется при шифровании, то легко можете обратить процесс вспять и использовать тот же ключ для расшифровки. Даже весьма хитроумные и надежные шифры симметричны. Поэтому безопасность требует, чтобы используемый ключ держался в секрете от всех, за исключением отправителя и получателя сообщений.

Как сказал Бенджамин Франклин, «трое могут сохранить секрет, если двое из них мертвы». В симметричном шифре ключ должны знать как минимум двое, что, по мнению Франклина, слишком много. В 1944 или 1945 году кто-то (возможно, Клод Шеннон, изобретатель теории информации) в исследовательском центре Bell Labs в США предложил защищать голосовую связь от подслушивания при помощи добавления к сигналу случайного шума, а затем, после получения сигнала, его вычитания. Это тоже симметричный метод, поскольку ключ здесь – случайный шум и вычитание компенсирует его добавление. В 1970 году Джеймс Эллис, инженер Центра правительственной связи Великобритании, бывшей Правительственной школы кодирования и шифрования, заинтересовался, нельзя ли генерировать шум математически. Если да, то в принципе можно создать систему, где это будет результатом не простого добавления сигналов, а математического процесса, который очень трудно обратить, даже если знать, что он собой представляет. Конечно, получатель должен иметь возможность обратить процесс, но этого можно добиться с помощью второго ключа, известного только получателю.

Эллис назвал свою идею «несекретным шифрованием». Сегодня используют термин «криптосистема с открытым ключом». Обе эти фразы означают, что правило для шифрования сообщения можно свободно опубликовать в общедоступных источниках, но без знания второго ключа никто не сможет понять, как обратить эту процедуру и расшифровать сообщение. Оставалась единственная проблема: Эллис не смог разработать подходящий метод шифрования. Он хотел получить то, что сегодня называется функцией с потайным входом: легко вычислить, но трудно обратить (в потайной вход легко провалиться, но трудно выбраться). Как всегда, здесь должен иметься секретный второй ключ, позволяющий законному получателю обратить процесс так же легко, как спрятанная лестница позволяет провалившемуся выбраться.

И тут на сцену выходит Клиффорд Кокс, британский математик, также работавший в Центре правительственной связи. В сентябре 1973 года Кокса неожиданно осенила блестящая идея. Он понял, что мечту Эллиса можно реализовать, создав функцию с потайным входом при помощи простых чисел. С точки зрения математики перемножить два или более простых числа легко. Можно, например, вручную перемножить два 50-значных простых числа, получив при этом 99– или 100-значный результат. Обратная операция – взять 100-значное число и найти его простые делители – намного труднее. Стандартный школьный метод «пробовать все возможные делители по очереди» здесь бесполезен: возможностей слишком много. Кокс придумал функцию, основанную на произведении двух больших простых чисел, то есть на результате их перемножения. Получившийся шифр настолько надежен, что это произведение (но не его простые сомножители) можно не держать в секрете. Для расшифровки необходимо знать эти два простых числа по отдельности, в них и кроется секретный второй ключ. Без этих чисел вы ничего не сможете сделать, знания только их произведения недостаточно. Допустим, я говорю вам, что нашел два простых числа, произведение которых равно

1192 344277 257254 936928 421267 205031 305805 339598 743208 059530 638398 522646 841344 407246 985523 336728 666069.

Сможете ли вы найти эти простые числа?{41}41
  Ответ:
  p = 12277 385900 723407 383112 254544 721901 362713 421995 519,
  q = 97117 113276 287886 345399 101127 363740 261423 928273 451.
  Я нашел эти два простых числа методом проб и ошибок и перемножил их на компьютере, воспользовавшись символьной алгеброй. Это заняло несколько минут, причем время в основном тратилось на ручную замену случайных цифр, пока я не наткнулся-таки на простое число. После этого я велел компьютеру найти простые множители произведения. Расчет продолжался очень долго и не дал результата.


[Закрыть] По-настоящему быстрый суперкомпьютер сможет это сделать, а вот ноутбук вряд ли. А если взять побольше знаков, то и суперкомпьютер выйдет из игры.

Итак, Кокс, до этого занимавшийся теорией чисел, придумал метод создания функции с потайным входом с помощью пары простых чисел – как он это сделал, я объясню чуть позже, когда мы познакомимся с необходимыми понятиями. Метод был настолько прост, что поначалу Кокс даже не записал его. Позже он изложил идею подробно в отчете для начальства. В то время никто не мог представить, как применить этот метод с тогдашними слабыми компьютерами, поэтому его засекретили. Кроме того, его передали в Агентство национальной безопасности США. Обе организации видели военный потенциал метода, потому что даже при медленных расчетах можно было переслать ключ к какому-то совершенно иному шифру по электронной связи. Это основной способ применения подобных шифров на сегодняшний день как в военных, так и в гражданских целях.

Британские бюрократы не раз не могли разглядеть гигантские перспективы предлагаемых новинок, взять хотя бы пенициллин, реактивный двигатель, ДНК-идентификацию. В данном случае, однако, они могут оправдать свои действия патентным правом: чтобы получить патент, необходимо раскрыть суть изобретения. Как бы то ни было, революционную идею Кокса положили под сукно подобно тому, как в финале фильма «Индиана Джонс: В поисках утраченного ковчега» ящик с ковчегом отправляют на гигантский правительственный склад, до самой крыши забитый одинаковыми ящиками.

Однако в 1977 году появился точно такой же метод, который независимо придумали и быстро опубликовали три американских математика: Рональд Ривест, Ади Шамир и Леонард Адлеман. Теперь в их честь эта система называется криптосистемой Ривеста – Шамира – Адлемана (RSA). В конце концов, в 1997 году британские службы безопасности рассекретили работу Кокса, и мы теперь знаем, что именно он первым додумался до этого.