— Это очень просто. Это несложная задача. Её можно решить хотя бы перебором. Подумайте. Ты уже сказал про функцию Эйлера. Для чего она нужна?
— Это модуль, по которому делаются вычисления.
И тут Катя воскликнула:
— Я поняла! Функция Эйлера равна произведению двух простых множителей, из которых сначала вычли по единице. И если мы знаем простые множители, то можем легко подсчитать функцию Эйлера. Но мы этих множителей не знаем, а потому расшифровать зашифрованное этим алгоритмом сообщение очень сложно.
— Всё правильно. Именно на гипотезе, что разложить очень большое число на простые множители крайне сложно, и основана криптографическая сложность этого алгоритма. Но я хочу вам сказать, что это только гипотеза. Пока что нет алгоритма разложения, который работал бы за приемлемое время на современных компьютерах. Но есть понимание того, как эту задачу можно решить быстро и просто. И сейчас я вам про это расскажу…
Я спросил:
— Погоди-ка. Если ты говоришь, что есть метод быстрого взлома этого алгоритма RSA, но при этом на нем основана вся криптозащита в мире, то не собираешься ли ты нам рассказать страшную тайну, за которую могут и чикнуть?
— Ну что это за выражения: «чикнуть»? Нет, не собираюсь, поскольку расскажу только про абстрактную математическую модель. Она ещё не реализована, и когда мы сможем её реализовать — вообще непонятно. Но фундаментальных ограничений нет, так что когда-нибудь мы сможем создать компьютер, подходящий для этой цели, и вы будете к этому готовы.
Отец немного поразмыслил, а потом сказал:
— Итак, давайте с самого начала. Кто мне скажет, как при помощи двух простых множителей взломать шифрограмму RSA?
Я, не дожидаясь разрешения, выпалил:
— Надо от каждого простого числа отнять единицу, а результаты перемножить. Это получится значение функции Эйлера. Оно берётся в качестве модуля, по которому надо найти обратный элемент для открытой экспоненты. Этот обратный элемент и будет закрытой экспонентой. Зная её, мы сможем расшифровать сообщение.
Отец похвалил меня, а потом обратился к Кате:
— Катерина, скажи теперь ты, что такое «обратный элемент»?
— Это такое число, которое, если его перемножить с заданным, даст единицу по некоторому модулю.
— Отлично! Никак не думал, что вы сможете так просто оперировать математическими понятиями, которые изучаются на специальных курсах абстрактной алгебры. Теперь давайте поговорим о новой математической модели, про которую я обещал вам рассказать. Она называется «квантовые вычисления».
Я даже выдохнул от таких известий. Дело в том, что я точно знал: в научной лаборатории у отца уже сейчас проходит испытания прототип квантового компьютера. При его разработке использовались те же самые технологии, которые он применял ко мне для создания искусственной памяти. Неужели теперь он посвятит меня в тайну этих методов?
Вместе с тем отец продолжал:
— Вы хорошо знаете, что в информатике и теории информации используется понятие «бит». Это единица количества информации, и один бит представляет собой количество актов выбора между двумя альтернативами. Если у нас есть два различных предмета, то для того, чтобы выбрать между ними, требуется один бит. Если есть четыре предмета, то для выбора одного требуется два бита. Для восьми предметов требуется три бита. Ну и так далее, вы уже должны это прекрасно понимать. Традиционно для представления битов используются две цифры — 0 и 1. Так и выглядит альтернатива между двумя предметами: 0 или 1. Если у нас четыре предмета, то требуется два бита, которые дают четыре варианта: 00, 01, 10 и 11. Вспомнили?
Мы с Катей дружно кивнули. Отец улыбнулся и продолжил лекцию:
— А теперь представьте, что мы оперируем не чёткими битами, а некоторой их нечёткой комбинацией. В физике это называется «суперпозицией», но мне не очень нравится это слово, так как оно не отражает сущности. Возьмём один бит. В обычной математике он может принимать значение 0 или 1, да? А в квантовых вычислениях один бит может принимать бесконечное количество значений, каждое из которых равно сумме значений 0 и 1 с некоторыми коэффициентами, причём сами коэффициенты являются комплексными числами, а сумма их квадратов должна равняться 1. Понятно? Конечно же, непонятно.
Мы с Катей опять кивнули, потом замотали головами, а потом рассмеялись. Отец воздел руки к небу, но потом сосредоточился и сказал:
— Ладно, про комплексные числа говорить не будем. В целом для решения задачи они не требуются. Просто надо помнить, что наша реальность, похоже, устроена так, что в ней используются именно комплексные числа. Но это я вам потом еще напомню. Итак, пусть это будут действительные коэффициенты. Каждая единица информации в модели квантовых вычислений представляет собой сумму битов 0 и 1 с действительными коэффициентами, сумма квадратов которых равна 1. Выглядит это так.
Отец записал формулу:
— Так понятно?
Мы с Катей опять синхронно покачали головами. Я не выдержал и сказал:
