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

Заметим, что <math>\{ | \hat{l} \rangle \}_{0 \le l \le r - 1}</math> образует ортонормальный базис <math>\mathbb{C} [ \langle a \rangle ]</math>, где <math>\langle a \rangle</math> – подгруппа, порожденная <math>a</math> в G и изоморфная <math>\mathbb{Z}_r</math>, а <math>\mathbb{C} [ \langle a \rangle ]</math> обозначает гильбертово пространство функций от <math>\langle a \rangle</math> над полем комплексных чисел.

'''Алгоритм 1 (дискретное логарифмирование)'''

Дано: элементы <math>a, b \in G</math>, квантовая схема для U, порядок r для <math>a</math> в G.

Требуется: найти с постоянной вероятностью дискретный логарифм s от b по основанию <math>a</math> в G.

   (d) <math> \mapsto r^{-1/2} \sum_{l = 0}^{r - 1} |sl \; mod \; r \rangle |l \rangle |\hat{l} \rangle</math>

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

   3. Пусть <math>k_1, k_2</math> – целые числа, такие, что <math>k_1 l_1 + k_2 l_2 = 1</math>. Вывести <math>s = k_1(sl_1) + k_2(sl_2) mod \; r</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], где группа состоит из группы точек эллиптической кривой над конечным полем.