Лекция 12. Алгоритм нахождения периода и факторизация больших чисел

На этой Лекции мы обсудили, как при помощи квантовых схем решается задача нахождения периода функции целого аргумента. Для её решения используется техника, аналогичная алгоритму Саймона, и свойства цепных дробей. Этот алгоритм позволяет решать задачу о скрытой подгруппе в любой конечно порождённой абелевой группе, в том числе задачу нахождения порядка одного числа по модулю другого. Благодаря этому удаётся эффективно находить нетривиальные делители больших чисел.