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

   (e) <math> \mapsto (sl \; mod \; r, l)</math>

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

Идеи, лежащие в основе алгоритма Шора для дискретного логарифмирования, могут быть обобщены для получения эффективного квантового алгоритма для поиска скрытых подгрупп в абелевых группах (краткий обзор см. в [1]). Оказывается, что нахождение дискретного логарифма <math>b</math> по основанию <math>a</math> в G сводится к задаче поиска скрытой подгруппы в группе <math>\mathbb{Z}_r \times \mathbb{Z}_r</math>, где r – порядок <math>a</math> в G. Помимо задачи дискретного логарифмирования, другие криптографически важные функции, такие как факторизация целых чисел, нахождение порядка перестановок, нахождение эквивалентных относительно сдвига многочленов над конечными полями, могут быть сведены к случаям нахождения скрытой подгруппы в абелевых группах.

Предполагаемая неразрешимость задачи дискретного логарифмирования лежит в основе нескольких криптографических алгоритмов и протоколов. Первый пример криптографии с открытым ключом, а именно обмен ключами с помощью протокола Диффи-Хеллмана [2], использует дискретные логарифмы, обычно в группе <math>\mathbb{Z}^*_p</math> для простого числа p. Безопасность алгоритма цифровой подписи, являющегося национальным стандартом США (подробности и ссылки см. в [7]), зависит от предполагаемой неразрешимости задачи дискретного логарифмирования в <math>\mathbb{Z}^*_p</math>, где p – простое число. Криптосистема Эль-Гамаля с открытым ключом [3] и ее производные используют дискретные логарифмы в соответствующим образом выбранных подгруппах <math>\mathbb{Z}^*_p</math>, где p – простое число. Более поздние варианты применения включают криптографию на эллиптических кривых [6], где группа состоит из группы точек эллиптической кривой над конечным полем.