Материал: Лекция 5 Квантовые вычисления и оценка стойкости криптоалгоритмов
Измерение состояния регистра Y 
Например, фиксированному состоянию Последовательность значений x
y
= 8 соответствует
|
|
1 |
( |
|
|
|
|
|
11 +...) |
|
|
|
|
1 |
|
A |
|
|
|
|
|
φ2 = |
|
|
3 + |
|
7 + |
|
|
8 |
= |
|
|
∑j=0 |
|
r j +l |
|
|
8 |
||||
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||
|
А+1 |
|
|
|
|
A+1 |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
где А наибольшее целое меньшее, |
чем ( N −l ) / r, |
A ≈ N / r. |
|||||||||||||||||||
41
Вычисление периода
Из этого состояния мы хотим выделить информацию о периоде r. Временно сделаем предположение, что l при разных испытаниях принимает
одно и тоже значение. Пусть мы провели 3 испытания и получили три копии ϕ2
x1 = j1r +l, |
x2 = j2r +l, x3 = j3r +l, |
Далее находим |
x1 − x2 =( j1 − j2 )r, x1 − x3 =( j1 − j3 )r |
Поскольку j равновероятны, то с высокой вероятностью gcd(j1 − j2 , j1 − j3 ) =1
Поэтому период легко вычисляется так как
gcd(x1 − x2 ,x1 − x3 ) = gcd((j1 − j2 )r,( j1 − j3 )r) = r
Пример: x1 = 27, x2 =15, x3 = 7,
gcd(x1 − x2 ,x1 − x3 ) = gcd(( 27 −15 ),( 27 −7 )) gcd(12,20 ) = 4
К сожалению, l изменяется случайно (определяется случайным измерением регистра Y 
, поэтому принципиально необходимо применение квантового преобразования Фурье, устраняющего этот недостаток.
42
ДискретноепреобразованиеФурье для
функции f ( x ) = 2x mod 15
yk = |
1 |
N −1 |
2πi |
jk |
|
||||
|
∑ x j e |
|
N |
N j=0
43
Рассмотрим сначала частный случай, когда r делит N нацело. Тогда A = N / q −1
Запишем состояние регистра |
|
x в следующем виде |
||||
|
||||||
где |
|
|
|
|
|
|
f (x) = r / N , если x−l кратно r, |
||||||
|
||||||
|
f (x) = 0, если x−l не кратно r |
|||||
ϕl 
= N∑−1 f (x) x
x=0
Это λ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
N / r −1 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
r |
|
|
||||||||
Тогда состояние регистра можно переписать так |
|
ϕl |
= |
|
|
∑ |
|
jr +l |
|
|||||||||||||||||||||||||||||||||||
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||
|
|
N |
|
|||||||||||||||||||||||||||||||||||||||||
f(x) |
|
l |
|
|
|
|
|
|
|
r |
|
|
|
r |
|
|
|
|
|
r |
|
|
|
амплитуда |
|
|
j=0 |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
r / N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
КвантовоепреобразованиеФурье |
|
||||||||||||||||||||||||||||||||||||||||||
|
|
Выполняя ДПФ для состояния |
|
ϕl |
|
, получаем |
|
|
DFT |
|
ϕl = ∑ f ( c ) |
|
c |
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||
|
|
где амплитуда |
f ( c ) DFT от f (x) |
N/r |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c |
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
N / r −1 |
2πi( jr |
+l )c |
|
|
|
|
N / r −1 |
|
|
jc |
|
|
|
|
lc |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
r |
|
|
|
r |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
f (c) = |
|
|
|
|
|
∑ exp( |
|
|
|
|
) = |
|
|
|
|
∑ exp( |
2πi |
|
|
|
) exp( 2πi |
|
|
|
) |
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
N |
|
|
|
N |
|
N |
|
|
N / |
r |
|
|
N |
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
j=0 |
|
|
|
|
|
|
j=0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Используя свойство комплексной функции в показательной форме, |
|
|||||||||||||||||||||||||||||||||||||||||||
T |
|
|
jn |
|
|
|
T ,n = 0 mod T , |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
∑exp 2πi |
= |
|
|
|
|
можно записать, что в последнем выражении |
|
|||||||||||||||||||||||||||||||||||||
T |
0,n ≠ 0 mod T |
44 |
||||||||||||||||||||||||||||||||||||||||||
j |
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||
член в квадратных скобках равен нулю за исключением с кратных N / r, поэтому
|
|
|
|
|
N |
|
lc |
|
1 |
|
|
lc |
|
N |
|
||
|
r |
exp( 2πi |
) = |
|
exp( 2πi |
), если c кратно |
, |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
N r |
N |
|
|
|
|
N |
r |
||||||||||
f (c) = |
|
|
|
|
r |
|
|
|
|
||||||||
|
|
|
|
|
|
|
0, в |
противномслучае. |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|||||||||
f ( c ) |
N/r |
N/r |
|
N/r |
N/r |
|
амплитуда |
||
|
|
|
|
|
|
|
|
|
r |
0 |
|
|
|
|
|
|
r-1 |
c |
|
Полагая, c = j |
N |
запишем |
|
|
|
|
|
|
|
|
|
r |
|
|
|
|
|
|
|
|
|
|
|
|
r −1 |
|
jl ) j |
N |
|
|
|
|
DFT ϕl |
= |
1 ∑exp( 2πi |
|
|||
|
|
|
|
|
r j=0 |
|
r |
r |
|
Измерение состояния с меткой c будет давать множитель λ = jl , имеющий случайное распределение от 0 до r-1, в силу случайности l.
Однако начальный сдвиг l |
в этом случае не влияет, поскольку |
можно рассматривать λ |
как новый множитель, который принимает |
значения от 0 до r-1 в каком то порядке, когда j принимает значения в |
|
порядке 0,1,2,…, r-1. |
45 |
|