Группа китайских ученых опубликовала статью о факторизации чис | RUH8

Группа китайских ученых опубликовала статью о факторизации чисел с помощью квантового компьютера и равноапостольный Шнайер прокомментировал, что алгоритм может оказаться неверным, но не очевидно неправильным (хотя и честно предупредил, что не очень знаком с решетками и квантовыми компьютерами). Давайте попробуем разобраться.

Для начала, чтобы не путаться запомним, что Шора зовут Питер, а Шнорра - Клаус. Питер придумал как использовать квантовое преобразование Фурье для факторизации. Проблема только в том, что квантовых компьютеров способных выполнить алгоритм Питера Шора не существует. Ни со сколькью кубитами, их просто нет, и в ближайшее время не предвидится.

Кроме "нормальных" квантовых компьютеров есть еще компьютеры построенные на "отжиге" (annealing). Суть в том, что рано или поздно система перейдет в наиболее энергоэффективное состояние. Если кинуть горсть шариков на волнистую поверхность, то шарики будут скапливаться в углублениях. Мало того что "нормальные" квантовые компьютеры не универсальны, но "отжигатели" во многом похожи на аналоговые компьютеры прошлого, которые не решают, а моделируют задачу. Не всякую задачу можно свести к подобной энерго-оптимизации.

Клаус Шнорр известный в своей области ученый, ему мы обязаны цифровыми подписями, потому когда Клаус залил препринт статьи, в которой было написано, что "this destroyes RSA cryptosystem" к ней отнеслись серьезно. Алгоритм Клауса классический. Я в комментарии добавлю ссылку на пост, который может дать примерное представление об алгоритме Клауса Шнорра.

Клаус пытается использовать решетки и алгоритм поиска ближайшего вектора (CVP). В его статье с тех пор специалисты нашли ошибки, как в теоретической части, так и в практической. Для чисел интересного размера "отношения" просто не находятся за указанное Клаусом количество попыток. Его алгоритм неверный, хотя и весьма неочевидным способом.

Более того, сам по себе CVP - NP-hard, а факторизация NP-intermediate, CVP более сложная задача чем факторизация. Если бы китайцы нашли алгоритм для CVP, то это был бы значительный результат, который сильно подорвал бы пост-квантовую криптографию (которой и так в последнее время достается). Если бы они смогли улучшить алгоритм Питера, сократив количество кубитов или операций, или исправить алгоритм Клауса, то тоже интересно. Но нет.

So, imho, this does not destroyes RSA cryptosystem. Not yet.