Алгоритм Шора, разработанный Питером Шором (Peter Shor) в 1994 году, – квантовый алгоритм разложения числа на простые множители. Значимость его в том, что он делает потенциально возможным взлом мощнейших современных криптографических систем, в частности, шифра RSA.
Система RSA сейчас широко применяется в протоколах, использующихся в электронной коммерции, в защите программного обеспечения, в цифровых подписях. Шифр был создан в 1977 году американскими математиками Райвестом (Rivest), Шамиром (Shamir) и Адлеманом (Adleman). RSA является шифром с открытым ключом, то есть ключ, который нужен для шифрования данных, не хранится в тайне, зашифровать сообщение может кто угодно. Для расшифровки, однако, необходим второй ключ, секретный.
Для взлома шифра необходимо, в частности, разложить открытый ключ на два простых множителя. Эта задача решается перебором вариантов, поэтому надежность шифра зависит от длины ключа. Шифр с коротким ключом можно взломать даже на персональном компьютере, но если ключ достаточно длинный, то и современным суперкомпьютерам, и сетям распределенных вычислений для взлома потребуются десятки лет.
Алгоритм Шора, однако использует сильные стороны квантовых компьютеров, не имеющие аналогов в классических компьютерах: способность их информационных единиц – кубитов – принимать несколько значений одновременно и находиться в состоянии “запутанности”. Теоретические работы показывают, что при наличии достаточно мощного квантового компьютера алгоритм способен взломать RSA за ограниченное время.
Прототипы квантовых компьютеров, созданные китайскими и австралийскими исследователями, очень примитивны: пока на два простых множителя удалось разложить лишь число 15. Однако эти работы показывают, что реализация алгоритма Шора возможна в принципе, дальнейшее – скорее инженерная задача (правда, по мнению некоторых специалистов, нерешаемая).
В 2001 году корпорация IBM также создала управляемый ядерно-магнитным резонансом (ЯМР) квантовый компьютер из семи кубит, который тоже мог разложить число 15 на 5 и 3. Однако и китайская, и австралийская группы считают, что компьютер IBM имел серьезные недостатки: во-первых, использование ЯМР (сложной и дорогой технологии) при возрастании числа кубитов приводит к помехам, так что возможности развития сильно ограничены, во-вторых, исследователи сомневаются, что в компьютере действительно использовалась квантовая запутанность.
Управляемые короткими вспышками обычного лазера новые компьютеры свободны от этих недостатков, утверждают их разработчки.