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

Перейти к навигации Перейти к поиску
м
Строка 74: Строка 74:
   Применить <math>QFT_{\mathbb{Z}_r}</math> к первым двум регистрам;
   Применить <math>QFT_{\mathbb{Z}_r}</math> к первым двум регистрам;
    
    
   (e) <math> \mapsto</math> (sl mod r, l)
   (e) <math> \mapsto (sl \; mod \; r, l)</math>
    
    
   Измерить первые два регистра;
   Измерить первые два регистра;
Строка 89: Строка 89:




Применение <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, повторив его постоянное число раз.
Применение <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, повторив его постоянное число раз.




Строка 97: Строка 97:
   
   


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


== Применение ==
== Применение ==
4431

правка

Навигация