Рассмотренный квантовый алгоритм факторизации имеет слож-
ность
O
(
n
3
)
. В то же время, лучший классический алгоритм фак-
торизации — алгоритм решета числового поля [4] — имеет сложность
O
(exp(
c
(log
n
)
1
/
3
(log log
n
)
1
/
3
))
, где
c
=
3
q
64
9
.
Криптостойкость системы Эль-Гамаля.
Система Эль-Гамаля
основана на трудности вычисления дискретного логарифма, т.е., если
g
— образующий элемент конечной группы
G
, то зная
a
2
G
, надо
найти
r
2
G
такой, что
a
=
g
r
. Наиболее часто эта схема применяется
для группы
Z
p
и для группы точек эллиптической кривой.
Существует квантовый алгоритм Шора для вычисления дискрет-
ного логарифма. Приведем здесь его оригинальную версию, которая
предназначена для группы
Z
p
(где
p
— простое).
Сначала найдем
q
— степень двойки, чтобы
p < q <
2
p
. Приведем
квантовый регистр в состояние
1
p
−
1
p
−
2
X
a
=0
p
−
2
X
b
=0
a, b, g
a
x
−
b
(mod
p
)
.
(2)
Применим теперь преобразование Фурье к первой и второй частям
регистра, в результате чего регистр перейдет в состояние
1
q
(
p
−
1)
q
−
1
X
c
=0
q
−
1
X
d
=0
e
2
πi
q
(
ac
+
bd
)
c, d, g
a
x
−
b
(mod
p
)
.
(3)
Теперь измеряем состояние квантового регистра. В результате из-
мерения с вероятностью не менее
1
480
мы получим
c
и
d
такие, что
−
1
2
q
6
d
q
+
r
c
(
p
−
1)
− {
c
(
p
−
1)
}
q
(
p
−
1)
q
6
1
2
q
(mod1)
,
(4)
где
{
x
}
q
— число, удовлетворяющее соотношениям
{
x
}
q
≡
x
(mod
q
)
и
−
q
2
<
{
x
}
q
6
q
2
.
Для того чтобы получить кандидата на
r
, надо округлить
d
q
до бли-
жайшего числа, кратного
1
p
−
1
, затем разделить по модулю
p
−
1
на
(
p
−
1)
c
− {
(
p
−
1)
c
}
q
q
. В работе .[6] сложность этого алгоритма оцени-
вается как
O
(
n
3
)
. В то же время, лучший классический алгоритм для
дискретного логарифма имеет сверхполиномиальную сложность.
Несмотря на то, что долгое время считалось, что алгоритм Шора не
подходит для вычисления дискретного логарифма в группе точек эл-
липтической кривой, в работе [5] приводится вариант алгоритма Шора
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2007. № 2
119
