Квантовый алгоритм для решения задачи дискретного логарифмирования: различия между версиями

Применение <math>QFT_{\mathbb{Z}_r}</math> к первым двум регистрам дает состояние вышеприведенного алгоритма на шаге 1(d). Измерение первых двух регистров дает (sl mod r; l) для равномерно распределенного l; 0 < l < r - 1 на шаге 1(e). С помощью элементарной теории чисел можно показать, что если целые числа l\, h равномерно и независимо выбраны между 0 и 1-1, то они будут совпадать с постоянной вероятностью. В этом случае найдутся целые числа k1, k2 такие, что k1 l1 + k2 l2 = 1, что приведет к нахождению дискретного логарифма s на шаге 3 алгоритма с постоянной вероятностью. Поскольку фактически можно применить только e-приближенную версию <math>QFT_{\mathbb{Z}_r}</math>, можно задать e достаточно малой константой, и это все равно даст правильный дискретный логарифм s на шаге 3 алгоритма с постоянной вероятностью. Вероятность успеха алгоритма Шора для задачи дискретного логарифма можно увеличить по крайней мере до 3/4, повторив его постоянное число раз.

Задача о дискретном логарифмировании является частным случаем более общей задачи, называемой задачей о скрытой подгруппе [8].

Идеи, лежащие в основе алгоритма Шора для дискретного логарифмирования, могут быть обобщены для получения эффективного квантового алгоритма для поиска скрытых подгрупп в абелевых группах (краткий обзор см. в [ ]). Оказывается, что нахождение дискретного логарифма b по основанию a в G сводится к задаче поиска скрытой подгруппы в группе Zr x Zr, где r – порядок a в G. Помимо задачи дискретного логарифмирования, другие криптографически важные функции, такие как факторизация целых чисел, нахождение порядка перестановок, а также нахождение эквивалентных относительно сдвига многочленов над конечными полями, могут быть сведены к случаям нахождения скрытой подгруппы в абелевых группах.