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

Описание алгоритма приведено ниже. Предполагается знакомство с квантовой нотацией. Достаточное представление о квантовых вычислениях можно найти в книге Нильсена и Чуаня [8]. Пусть <math>(G, a, b, \bar{r})</math> – экземпляр задачи дискретного логарифмирования, где <math>\bar{r}</math> – заданная верхняя граница на порядок <math>a</math> в G. То есть существует положительное целое число <math>r \le \bar{r}</math>, такое, что <math>a^r = 1</math>. Используя эффективный квантовый алгоритм поиска порядка, также разработанный Шором [9], можно предположить, что порядок a в G известен и представляет собой наименьшее положительное целое число r, удовлетворяющее <math>a^r = 1</math>. Время выполнения алгоритма Шора для поиска порядка составляет <math>O((log \; \bar{r})^3)</math>. Пусть <math>\epsilon > 0</math>. Алгоритм дискретного логарифмирования работает на трех регистрах, из которых первые два имеют длину по t кубитов, где <math>t := O(log \; r + log(1 / \epsilon))</math>, а третий регистр достаточно велик, чтобы хранить элемент G. Пусть U обозначает унитарное преобразование <math>U: |x \rangle |y \rangle |z \rangle \mapsto |x |rangle |y \rangle |z \bigoplus (b^x \; a^y) \rangle</math>, где <math>\bigoplus</math> обозначает побитовое исключающее ИЛИ. Если имеется доступ к обратимому оракулу для групповых операций в G, U может быть реализовано обратимо за время <math>O(t^3)</math> путем многократного возведения в квадрат.

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

Требуется: найти с постоянной вероятностью дискретный логарифм s от b по основанию a в 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</math> (sl mod r, l)

   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). Измерение первых двух регистров дает (sl mod r, l) для равномерно распределенного l, <math>0 \le l \le r - 1</math> на шаге 1(e). С помощью элементарной теории чисел можно показать, что если целые числа <math>l_1, l_2</math> равномерно и независимо выбраны в интервале между 0 и l-1, то они будут совпадать с постоянной вероятностью. В этом случае найдутся целые числа <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]). Оказывается, что нахождение дискретного логарифма b по основанию a в G сводится к задаче поиска скрытой подгруппы в группе <math>\mathbb{Z}_r \times \mathbb{Z}_r</math>, где r – порядок ''a'' в G. Помимо задачи дискретного логарифмирования, другие криптографически важные функции, такие как факторизация целых чисел, нахождение порядка перестановок, а также нахождение эквивалентных относительно сдвига многочленов над конечными полями, могут быть сведены к случаям нахождения скрытой подгруппы в абелевых группах.

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