Лекция 13. Квантовые алгоритмы для задач теории чисел

На этой Лекции мы поговорили об эффективных квантовых алгоритмах для двух важных задач теории чисел: задачи нахождения дискретного логарифма и задачи нахождения периода. Нахождение дискретного логарифма в циклической группе порядка $N$ сводится к вычислению скрытой подгруппы в группе $\mathbb{Z}_N\times\mathbb{Z}_N$ и возможности эффективно проводить возведение в степень по модулю $N$. Умение находить дискретные логарифмы позволяет взломать плотокол Диффи-Хеллмана генерации секретного ключа между двумя агентами. Задачу о нахождении периода $r$ некоторой для периодической функции $f$ можно сформулировать как задачу о скрытой подгруппе в $\mathbb{Z}$. Выбрав достаточно большое число $N > r^2$, можно проделать стандартную процедуру для вычисления скрытой подгруппы, и воспользоваться аналитическими свойствами цепных дробей.