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

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