Материал: Лекция 5 Квантовые вычисления и оценка стойкости криптоалгоритмов

•В алгоритме Шора задача факторизации M=pq сводитсяк задаче нахождения

периода r функции ax mod M .Наименьшее значениех, при котором ax mod M =1 называетсяпоказателемa по модулю М.

36

Реализация алгоритма Шора на двух квантовых регистрах

Обозначения:

M = p q

M < N < M 2 , N = 2n

37

Этапы алгоритма Шора

0.Подготовительный этап. Установка регистров в нулевое состояние.

1.Перевод регистров в равновесное состояние.

2.Вычисление степеней а^x в регистре Y, измерение состояния регистра.

3.Предвычисление периода с помощью квантового преобразования Фурье7

4.Вычисление периода на основе подходящих дробей

(на обычном компьютере)

38

Рис. 5. Инициализация регистров

ψ2 = (H n 0) 0

Рис. 6. Применение преобразования Адамара к регистру |x>

39