Текущее положение дел

Мы еще никогда не были настолько далеки от решения проблемы P и NP. Не в том смысле, что для этого требуется огромная подготовительная работа; просто мы уже испробовали все мыслимые и немыслимые подходы и исчерпали все известные науке методы доказательства, так что в ближайшем будущем прогресса ждать не приходится.

Единственную на сегодняшний момент потенциальную возможность открыл Кетан Мулмулэй из Чикагского университета. Ученый показал, что решение некоторых трудных проблем из области математики под названием «алгебраическая геометрия» (и это не помесь школьной алгебры и геометрии, а нечто гораздо более сложное) может дать ключ к доказательству неравенства P и NP. Вот только для решения этих алгебраически-геометрических проблем потребуются такие техники, которых в нашем арсенале нет и которые в ближайшее время вряд ли появятся. Несколько лет назад Мулмулэй предположил, что реализация этого плана займет около ста лет. Теперь тот прогноз уже кажется ему чересчур оптимистичным.

Так сколько нам еще ждать? Не исключено, что сейчас, когда вы читаете эти строки, проблему уже решили. Хотя, скорее всего, над ней будут биться еще очень долго; дольше даже, чем над Великой теоремой Ферма, которая поддалась лишь через 357 лет. А может, она так навсегда и останется одной из величайших загадок в истории математики и вообще всей науки.

Глава 8. Совершенно секретно

У каждого из нас есть секреты. Как минимум мы храним в тайне пароли и не желаем, чтобы кто-то читал нашу почту. Если P ≠ NP, то секреты есть и у NP-полных задач: это их решения, найти которые не так-то просто. В 1976 году Уитфилд Диффи и Мартин Хеллман предложили шифровать информацию при помощи класса NP. В истории криптографии, т. е. науки о шифровании, наступил поворотный момент.

Очень краткая история классической криптографии

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

Фраза The early bird gets the worm («Кто рано встает, тому бог дает») после такой кодировки превращается в Wkh hduob elug jhwv wkh zrup. Способ шифрования, при котором все буквы циклически сдвигаются на определенное число позиций, стали называть шифром Цезаря.

В Древнем Риме этот метод работал хорошо. Зашифрованные сообщения выглядели как случайный набор букв, а люди пока еще не обладали необходимыми навыками для взлома шифров. К IX веку математики разработали методы восстановления исходного сообщения; эти методы учитывали частоту появления букв и анализировали короткие слова. Глядя на фразу Wkh hduob elug jhwv wkh zrup, можно заметить, что буква h встречается четыре раза, т. е. чаще остальных. Самая распространенная буква английского алфавита – это e, ее частота составляет примерно 12 процентов. Вы можете предположить, что буква h кодирует букву e, – и будете совершенно правы. Сочетание wkh встречается дважды; вы уже знаете, что h – это e, поэтому делаете вывод, что wkh – это, наверно, the. Еще чуть-чуть – и исходное сообщение будет восстановлено!

Рис. 8.1. Шифр Цезаря

В XV веке, в эпоху Возрождения, итальянский ученый Леон Баттиста Альберти разработал более сложный метод. Это был шифр многоалфавитной замены, в котором сообщение разбивалось на несколько частей, и для каждой части использовался свой алфавит подстановки. Система Альберти практически не поддавалась взлому вплоть до XIX века, когда на шифры началось систематическое наступление.

Американский писатель и поэт Эдгар Аллан По мастерски владел техникой криптоанализа. В 1839 году он обратился к широкой публике с предложением присылать ему тексты, зашифрованные сложным, не поддающимся взлому шифром, и обещал разгадать их все. Годом позже По опубликовал эссе «Несколько слов о тайнописи», в котором утверждал, что человеческий разум не способен изобрести такой шифр, который разум другого человека был бы не в силах разгадать. В нашумевшем рассказе По «Золотой жук», появившемся в 1843 году, события вертятся вокруг расшифровки тайного сообщения. Это было одно из первых художественных произведений, в котором речь шла о секретных кодах.

В 1903 году выходят «Пляшущие человечки» Конан Дойля, где Шерлок Холмс взламывает подстановочный шифр, состоящий из странных пляшущих фигурок.

Наступила эра механики; люди начали изобретать машины, способные создавать ключи для шифровки и дешифровки. Самая известная шифровальная машина – это, пожалуй, «Энигма», первую версию которой в 1918 году в Германии разработал Артур Шербиус.

В «Энигме» было несколько роторов, искажавших набранные на клавиатуре символы. Роторы вращались в разных режимах, и каждый символ получал свой индивидуальный шифр замены. В результате машина выдавала усложненную версию многоалфавитного шифра Альберти, взломать которую было чрезвычайно трудно.

Рис. 8.2. Пляшущие человечки

Рис. 8.3. Шифровальная машина «Энигма»

У немцев во время Второй мировой большинство сообщений шифровалось при помощи «Энигмы». Незадолго до начала войны Великобритания получила от польской разведки описание машины и некоторых методов дешифровки. Британское правительство запустило засекреченный проект с кодовым названием «Ультра», целью которого был взлом шифров «Энигмы». В штат набирали известных шахматистов, чемпионов по решению кроссвордов и, конечно, талантливых математиков, среди которых был и основоположник теории вычислений Алан Тьюринг. В рамках проекта был спроектирован и построен «Колоссус» – первый в мире программируемый цифровой компьютер. «Именно благодаря проекту „Ультра“ мы выиграли войну», – скажет позже Уинстон Черчилль.

Криптография всегда была – и будет – чем-то вроде игры в кошки-мышки между теми, кто создает шифры, и теми, кто их взламывает. Впрочем, в семидесятых годах XX века игра заметно усложнилась, поскольку трудоемкость некоторых NP-задач послужила отправной точкой в создании новых методов шифрования.