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

Перейти к навигации Перейти к поиску
Строка 43: Строка 43:




Заметим, что <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> над полем комплексных чисел.
Заметим, что <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 (Дискретное логарифмирование)'''
'''Алгоритм 1 (дискретное логарифмирование)'''


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


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


Время выполнения: суммарно <math>O(t^3)</math> базовых вентильных операций, включая четыре вызова <math>QFT_{\mathbb{Z}_r}</math> и один вызов U.
Время выполнения: суммарно <math>O(t^3)</math> базовых вентильных операций, включая четыре вызова <math>QFT_{\mathbb{Z}_r}</math> и один вызов U.
Строка 70: Строка 70:
   Применить U
   Применить U
    
    
   (d) <math> \mapsto r^{-1/2} \sum_{l = 0}^{r - 1} |sl mod r \rangle |l \rangle |\hat{l} \rangle</math>
   (d) <math> \mapsto r^{-1/2} \sum_{l = 0}^{r - 1} |sl \; mod \; r \rangle |l \rangle |\hat{l} \rangle</math>
    
    
   Применить <math>QFT_{\mathbb{Z}_r}</math> к первым двум регистрам;
   Применить <math>QFT_{\mathbb{Z}_r}</math> к первым двум регистрам;
Строка 80: Строка 80:
   2. Если <math>l_1</math> не совпадает с <math>l_2</math>, прервать вычисление.
   2. Если <math>l_1</math> не совпадает с <math>l_2</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>.
   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>.




Источник — http://pco.iis.nsk.su/wega/index.php/Квантовый_алгоритм_для_решения_задачи_дискретного_логарифмирования