Криптографические приключения: таинственные шифры - Страница 65

Отец немного поразмыслил, а потом сказал:

— Итак, давайте с самого начала. Кто мне скажет, как при помощи двух простых множителей взломать шифрограмму RSA?

Я, не дожидаясь разрешения, выпалил:

— Надо от каждого простого числа отнять единицу, а результаты перемножить. Это получится значение функции Эйлера. Оно берётся в качестве модуля, по которому надо найти обратный элемент для открытой экспоненты. Этот обратный элемент и будет закрытой экспонентой. Зная её, мы сможем расшифровать сообщение.

Отец похвалил меня, а потом обратился к Кате:

— Катерина, скажи теперь ты, что такое «обратный элемент»?

— Это такое число, которое, если его перемножить с заданным, даст единицу по некоторому модулю.

— Отлично! Никак не думал, что вы сможете так просто оперировать математическими понятиями, которые изучаются на специальных курсах абстрактной алгебры. Теперь давайте поговорим о новой математической модели, про которую я обещал вам рассказать. Она называется «квантовые вычисления».

Я даже выдохнул от таких известий. Дело в том, что я точно знал: в научной лаборатории у отца уже сейчас проходит испытания прототип квантового компьютера. При его разработке использовались те же самые технологии, которые он применял ко мне для создания искусственной памяти. Неужели теперь он посвятит меня в тайну этих методов?

Вместе с тем отец продолжал:

— Вы хорошо знаете, что в информатике и теории информации используется понятие «бит». Это единица количества информации, и один бит представляет собой количество актов выбора между двумя альтернативами. Если у нас есть два различных предмета, то для того, чтобы выбрать между ними, требуется один бит. Если есть четыре предмета, то для выбора одного требуется два бита. Для восьми предметов требуется три бита. Ну и так далее, вы уже должны это прекрасно понимать. Традиционно для представления битов используются две цифры — 0 и 1. Так и выглядит альтернатива между двумя предметами: 0 или 1. Если у нас четыре предмета, то требуется два бита, которые дают четыре варианта: 00, 01, 10 и 11. Вспомнили?

Мы с Катей дружно кивнули. Отец улыбнулся и продолжил лекцию:

— А теперь представьте, что мы оперируем не чёткими битами, а некоторой их нечёткой комбинацией. В физике это называется «суперпозицией», но мне не очень нравится это слово, так как оно не отражает сущности. Возьмём один бит. В обычной математике он может принимать значение 0 или 1, да? А в квантовых вычислениях один бит может принимать бесконечное количество значений, каждое из которых равно сумме значений 0 и 1 с некоторыми коэффициентами, причём сами коэффициенты являются комплексными числами, а сумма их квадратов должна равняться 1. Понятно? Конечно же, непонятно.

Мы с Катей опять кивнули, потом замотали головами, а потом рассмеялись. Отец воздел руки к небу, но потом сосредоточился и сказал:

— Ладно, про комплексные числа говорить не будем. В целом для решения задачи они не требуются. Просто надо помнить, что наша реальность, похоже, устроена так, что в ней используются именно комплексные числа. Но это я вам потом еще напомню. Итак, пусть это будут действительные коэффициенты. Каждая единица информации в модели квантовых вычислений представляет собой сумму битов 0 и 1 с действительными коэффициентами, сумма квадратов которых равна 1. Выглядит это так.

Отец записал формулу:

a | 0 > + b | 1>, a + b = 1

— Так понятно?

Мы с Катей опять синхронно покачали головами. Я не выдержал и сказал:

— Ну послушай. Мне кажется, что ты хочешь объяснить что-то слишком сложное. Ты можешь рассказать самыми простыми словами, как можно взломать шифр? Не важно, какие там формулы. Главное для нас сейчас — понять, как это может быть.

Отец тяжело вздохнул. Потом подумал и сказал:

— Ну ладно. Это действительно высшая математика, и если вдаваться в тонкости, то мы просидим здесь неделю, а то и больше. Я просто расскажу вам, как квантовые компьютеры решают задачи и как этот способ решения можно применить для взлома метода RSA.

Отец начал рассказ. Если взять некоторое количество квантовых битов, или кубитов, то общее число возможных их состояний вычисляется как двойка в степени этого количества. Добавляя один кубит, мы увеличиваем число состояний в два раза. И, самое главное, все эти состояния находятся в суперпозиции друг с другом с такими же коэффициентами, сумма квадратов которых равна 1. Это было бы простой и интересной математической абстракцией, если бы не оказалось, что элементарные частицы, из которых состоит всё в нашем мире, не ведут себя именно так.

Другими словами, если взять атом и представить его в качестве кубита, то он будет находиться в суперпозиции двух состояний. Если к нему добавить второй атом, то они оба уже будут находиться в суперпозиции четырёх состояний. Три атома находятся в суперпозиции восьми состояний. Десять атомов — в суперпозиции одной тысячи двадцати четырёх состояний. Число состояний в суперпозиции трёхсот атомов больше, чем число атомов и других частиц во всей Вселенной.

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