Навстречу квантовой катастрофе

Однажды утром у вас не получится отправить электронную почту. По странному совпадению, одновременно упадут все мессенджеры, не откроется фейсбук и еще добрая половина сайтов в интернете. Зависнет и ваше банковское приложение. Вы выйдете на улицу и обнаружите, что банки заперты, банкоматы выключены, а в немногих открытых магазинах принимают только наличные. Перед вами постепенно
вырисовывается картина тотальной катастрофы: финансовая система страны полностью парализована, в государственных учреждениях хаос. Надо немедленно бежать — но купить билет на самолет тоже невозможно...
Теракт? Война?! Нет, никакой войны нет, террористы ни при чем. Просто кто-то наконец построил квантовый компьютер.
Общественность не ждет с этой стороны никакого подвоха. Кого в наше время удивишь компьютером? Это вам не Большой адронный коллайдер, который многие всерьез подозревали в способности уничтожить Вселенную. Что может изменить появление еще одного компьютера, пусть даже самого замечательного, современного, мощного и квантового как бог знает что?!
Проблема шифра
Поднимите глаза к адресной строке вашего браузера. В самом начале там стоят буквы https. Это последнее s означает, что данные, которыми вы обмениваетесь с сайтом snob.ru, шифруются по протоколу SSL.
Но, даже если вы не участник проекта «Сноб», криптографические технологии сопровождают вас постоянно. Вы сталкиваетесь с шифрованием всякий раз, когда снимаете деньги в банкомате или заходите в банковское приложение, когда пишете сообщение в мессенджере, когда отправляете электронную почту. Современная банковская система, документооборот крупных компаний, государственные сервисы, системы связи немыслимы без криптографических технологий, не говоря уже о военных и спецслужбах.
Значительная часть этого инструментария основана на использовании асимметрии умножения и обратной операции — разложения на множители. Допустим, вам надо перемножить два двузначных числа — например, 19 и 41. Если вы не обладаете феноменальными способностями, вы станете делать это в столбик, и вся процедура займет у вас, видимо, секунд десять. Если числа трехзначные, времени потребуется чуть больше. Перемножьте пятизначные числа — тут придется повозиться несколько минут, но в целом с увеличением числа знаков время вашего вычисления будет расти почти линейно. Числа увеличились в 10 раз, а время возросло на чуть-чуть.
А теперь скажите, пожалуйста, какие два целых числа надо умножить друг на друга, чтобы получить 391. Промучившись над этой задачкой некоторое время, вы, наверное, все же дадите ответ: 23 х 17. Теперь попробуем другое число: 4717. Что-то нам подсказывает, что эту задачу вы и вовсе не сможете решить без таблиц (ответ на нее: 53 х 89). Число увеличилось опять же в десять раз, но сложность задачи, то есть продолжительность вычисления возрастает гораздо быстрее (экспоненциально, если вы понимаете, о чем мы).
Поверьте нам на слово: компьютеру решать такие задачи тоже нелегко. Перемножить 250-значные числа он может почти мгновенно, а вот чтобы разложить на множители 250-значное число, самому быстрому современному компьютеру понадобится 800 тысяч лет вычислений.
Но при чем тут шифры?
( Collapse )