Агниджо Банерджи - Эта странная математика. На краю бесконечности и за ним

Большинство ученых, занимающихся вычислительными системами, полагают, что P ≠ NP . Это мнение подкреплено десятилетиями исследований, в результате которых ни для одной из более чем 3000 известных NP -полных задач не было найдено ни единого алгоритма, позволяющего решить ее за полиномиальное время. И все же аргумент, основанный на отрицательном опыте, не слишком убедителен, особенно в свете неожиданного доказательства Великой теоремы Ферма – очень просто сформулированной задачи, для решения которой потребовались огромные усилия и самые передовые методы. Чисто философские аргументы в пользу того, что P ≠ NP , также не очень убедительны. Скотт Ааронсон, математик, специалист в области теории вычислительных систем, преподающий в Массачусетском технологическом институте, заявил: “Если окажется, что P = NP , то мир станет совершенно не таким, каким мы его обычно считаем. Не будет больше никакой особой ценности в «творческих скачках», исчезнет принципиальная разница между решением задачи и признанием правильности найденного решения”. Тем не менее и в математике, и в других науках с завидной частотой происходят события, полностью переворачивающие наши представления об окружающем мире. Если действительно окажется, что P = NP , то, прежде всего, вряд ли это открытие будет иметь большое практическое значение – ведь доказательство, скорее всего, будет неконструктивным. Другими словами, даже если будет доказано, что для решения NP -полных задач существуют полиномиальные алгоритмы, ни одного конкретного алгоритма в доказательстве приведено не будет. Так что по крайней мере в ближайшем будущем нашим защищенным данным ничто не угрожает – хотя не совсем ясно, как долго это продлится, ведь математики уже всерьез занялись поиском такого алгоритма.

В любом случае, прежде чем существенные сдвиги в решении проблемы равенства P и NP или в разработке более эффективных алгоритмов поставят под угрозу безопасность наших данных, на помощь нам, вероятно, подоспеет квантовая механика. Разработки в области квантовой криптографии могут привести к созданию абсолютно стойкого шифра, не поддающегося дешифровке никакими методами. Один из действительно нераскрываемых шифров был изобретен еще в 1886 году и получил название “одноразовый блокнот”. Ключ представляет собой случайную последовательность букв той же длины, что и сообщение. Сообщение объединяется с ключом путем присвоения каждой букве числового значения ( A = 1, B = 2 и так далее), сложения числовых значений букв сообщения и соответствующих им букв ключа, вычитания из получившихся сумм 26, в случае если сумма превышает 26, и последующего обратного превращения чисел в буквы [24] 26 – по числу букв в алфавите, в данном случае английском. . Доказано, что этот метод является абсолютно криптостойким. Даже если у кого-то найдется достаточно времени, чтобы перебрать все возможные комбинации, будет совершенно невозможно отличить правильную расшифровку от множества неправильных вариантов. Важное условие: чтобы шифр невозможно было взломать, ключ должен после использования уничтожаться. Если его использовать повторно, то любой человек, имеющий в своем распоряжении оба зашифрованных сообщения и знающий, что ключ один и тот же, сможет их расшифровать. Кроме того, ключи должны передаваться секретно, поскольку доступ к ключу грозит мгновенной расшифровкой. Одноразовые шифры в свое время использовались советскими шпионами. Они сшивались в крошечные блокноты и пропитывались специальным горючим составом, чтобы при уничтожении от них не оставалось и следа. Такие шифры и сейчас используются для защиты данных, передаваемых по линии прямой связи между президентами США и России. Но необходимость секретно обмениваться ключами – серьезный недостаток метода, делающий его непригодным для большинства практических целей, например для передачи данных онлайн.

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