Пусть $M$ — число, которое требуется разложить на множители. Мы будем предполагать, что оно нечетно и что не является степенью простого числа.

Через $N$ обозначим размер основного регистра памяти, который мы будем использовать (не считая свалки). Ее битовый размер $n$ будет примерно в два раза больше, чем размер $M$. Более точно, выберем . И наконец, пусть — случайный параметр с $\gcd (t,M)=1$. Это условие может быть проверено классически за время, ограниченное полиномом от $n$.

Ниже мы опишем один проход алгоритма Шора, в котором $t$ (и, конечно, $M,N$ ) фиксировано. В общем случае требуется полиномиально большое число прогонов, в которых значение $t$ может оставаться тем же самым или быть выбрано заново. Это требуется для того, чтобы собрать статистику. Алгоритм Шора имеет вероятностный характер с двумя источниками случайности, которые следует ясно различать. Один из
них встроен в классическое вероятностное сведение разложения на множители к нахождению периода некоторой функции. Другой вытекает из необходимости наблюдения квантовой памяти, которое также дает случайные результаты.

Оценки, более точные, чем те, которые даны здесь, показывают, что квантовый компьютер, который может хранить около $3n$ кубит, может находить делитель $M$ за время порядка $n^3$ с вероятностью, близкой к 1 (см. [BCDP]). С другой стороны, есть широко распространенное убеждение, что никакая рекурсивная функция типа $M\mapsto$ собственный делитель $M$ не принадлежит $PF$. Именно поэтому наиболее популярные схемы шифрования с открытым ключом основываются на трудности задачи разложения на множители.