Тот факт, что репертуар универсального квантового компьютера содержит среды, передача которых является труднообрабатываемой для классического вычисления, говорит о том, что новые классы чисто математических вычислений тоже должны стать легкообрабатываемыми на этом компьютере. Как сказал Галилео, законы физики выражаются на языке математики, а передача среды эквивалентна оценке определенных математических функций. Действительно, в настоящее время обнаружено множество математических задач, которые можно было бы эффективно решить с помощью квантового вычисления, так как для всех известных классических методов они являются труднообрабатываемыми. Наиболее эффектной из этих задач является задача разложения на множители больших чисел. В 1994 году Питер Шор, работающий в Bell Laboratories, открыл метод, известный как
Алгоритм Шора чрезвычайно прост и довольствуется гораздо более скромным аппаратным обеспечением, чем то, которое понадобилось бы для универсального квантового компьютера. А потому вероятно, что
Как я уже сказал, не существует практической возможности разложения на множители 250-значного числа с использованием классических средств. Но квантовое устройство разложения на множители, работающее по алгоритму Шора, могло бы это сделать, выполнив всего несколько тысяч арифметических операций, что, возможно, было бы минутным делом. Таким образом, любой человек, имеющий доступ к такой машине, смог бы легко прочитать любое перехваченное сообщение, зашифрованное с помощью криптосистемы RSA.
Шифровальщикам не помогло бы даже использование больших чисел в качестве ключей, потому что ресурсы, необходимые для работы алгоритма Шора, очень медленно увеличиваются с увеличением раскладываемого на множители числа. В квантовой теории вычисления разложение на множители – очень легко обрабатываемая задача. Считается, что при данном уровне декогерентности снова появится практическое ограничение величины числа, которое можно разложить на множители, но неизвестен нижний предел технологически достижимой степени декогерентности. Поэтому, мы должны сделать вывод, что однажды в будущем, во время, которое сейчас невозможно предсказать, криптосистема RSA с любой данной длиной ключа может стать несекретной. В определенном смысле это делает ее несекретной даже сегодня. Любой человек или организация, которые сейчас записывают сообщения, закодированные в системе RSA, и ждут того времени, когда смогут купить квантовое устройство разложения на множители с достаточно низкой декогерентностью, смогут расшифровать эти сообщения. Возможно, это произойдет только через века, возможно всего через несколько десятилетий, а может, и еще раньше – кто знает? Но вероятность, что это произойдет еще не скоро, – это все, что теперь осталось от бывшей абсолютной секретности системы RSA.