Семинары: В. И. Яшин, Лекция 13. Квантовые алгоритмы для задач теории чисел

СЕМИНАРЫ


Квантовые вычисления 8 мая 2024 г. 13:10, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom

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