Алгоритм Шора позволит квантовым компьютерам будущего быстро факторизовывать большие числа, нарушая многие протоколы онлайн-безопасности. Теперь учёные показали, как сделать это ещё быстрее.
Питер Шор не собирался ломать Интернет. Но алгоритм, который он разработал в середине 1990-х годов, грозил сделать именно это. В знаковой статье Шор показал, как гипотетический компьютер, использующий особенности квантовой физики, может разбивать большие числа на простые множители гораздо быстрее, чем любая обычная классическая машина.
Результат имел последствия, выходящие далеко за рамки математики. В то время жизненно важная компонента интернет-безопасности, называемая криптографией с открытым ключом, основывалась на гипотезе, что факторизация больших чисел настолько сложна в вычислительном отношении, что практически невозможна. Эта гипотеза до сих пор лежит в основе некоторых важных протоколов. Алгоритм Шора показал, что она окажется неверной в мире с мощными квантовыми компьютерами.
За последние 30 лет учёные оптимизировали алгоритм Шора, готовясь к тому дню, когда квантовая технология станет достаточно развитой, чтобы его можно было использовать. Но новый вариант, разработанный учёным Нью-Йоркского университета Одедом Регевом, быстрее в принципиально ином смысле. Впервые удалось улучшить взаимосвязь между размером факторизуемого числа и количеством квантовых операций, необходимых для его факторизации.
Далее — по ссылке
