RUS  ENG
Полная версия
СЕМИНАРЫ

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


Лекция 14. Алгоритм разложения чисел на множители, подведение итогов

В. И. Яшин


https://youtu.be/hpA-08hBmAg

Аннотация: На последней Лекции мы завершили разговор об алгоритме Шора факторизации больших чисел. Если дано составное число $N$, то можно найти нетривиальный делитель этого числа за время $\tilde{\mathcal{O}}((\log N)^2)$ при помощи алгоритма Шора. Классическая сложность этой задачи лежит в основании работы некоторых криптосистем. Алгоритм основан на сведении задачи факторизации к задаче поиска периода чисел. Также, на Лекции был дан краткий обзор пройденного на протяжении курса и комментарий о современной тематике исследований в области квантовых вычислений.


© МИАН, 2024