Изменения

* Разложить число на множители за <tex>n^2</tex>. Постановка задачи разложения числа на множители выглядит следующим образом: на вход подается составное число <tex>N</tex> в двоичной записи, на выход должны быть выданы два числа <tex>p, q,</tex> такие что <tex>N = pq</tex>. Типичный размер <tex>N</tex> порядка <tex>2^{2000}</tex>. Мотивацией для решения данной задачи является отсутствие на данный момент полиномиального классического алгоритма. Решение этой задачи позволит, например, взломать систему RSA. Лучший из известных классических алгоритмов имеет <tex>O(2^{\sqrt[3]{n}})</tex> в качестве оценки времени работы. Уже сегодня существует квантовый алгоритм, который решает эту задачу за <tex>O(n^2)</tex> [Питер Шор, 1994].