因数分解を行いたい正の整数を$N$とする。
この数を$N=mn$と、二つの1より大きい整数$m, n$の積でかけることを見つけたい。

まず$N$と互いに素である正の整数$x$を探す。$x$を見つけるには次のようにする。


  1. 適当な整数$x(x < N)$をとってくる。

  2. もとの数$N$と新しくとった$x$の最大公約数を計算する。
    (最大公約数を効率よく計算するユークリッドの互除法という名のアルゴリズムが存在するので、これはすばやく行える。)

  3. それが$1$なら目的の$x$である。(もし$1$でないなら、その公約数は$N$の因数であるので、因数分解ができたことになる。)


このように決めた$x$を用いて、
\begin{align}
x^r-1 \equiv 0 \bmod N \label{eq:xr}
\end{align}
となる整数$r$を探す。

この$r$を探す部分が、古典的には効率よく計算できず、量子計算によって
効率よく計算できる部分である。
これについては次の節で述べる。

$r$が計算できたとして、次にこの$r$について
以下の条件が満たされているかどうかをチェックする。


  1. $r$は偶数である。

  2. 1の条件のもとで、さらに次の二式が成立する。
    \begin{align}
    x^{\frac{r}{2}} \neq 1 \bmod N \label{eq:+1} \\
    x^{\frac{r}{2}} \neq -1 \bmod N \label{eq:-1}
    \end{align}


この条件が成り立つかどうかは、効率的に計算することができることが知られている。

この条件が満たされなかったときには、
別の整数$x$を探して、再び$r$を計算し、条件を満たす$x$が見つかるまで繰り返す。

ある$x$を選んだとき、条件を満たす確率は$1/2$以上であることが、
ある定理によって示されているので、この試行はすぐに終えることができる。

このようにして条件を満たす$x$を探し出したとすると、
式(\ref{eq:xr})は、$r$が偶数であることより
\begin{align}
& (x^{\frac{r}{2}}-1)(x^{\frac{r}{2}}+1) \equiv 0 \bmod N \\
& (x^{\frac{r}{2}}-1)(x^{\frac{r}{2}}+1) = kN \qquad (kは整数) \label{eq:kN}
\end{align}
と変形することができる。一方、上の(\ref{eq:+1})(\ref{eq:-1})から
\begin{align}
& (x^{\frac{r}{2}}-1) \neq k'N \label{eq:k'N} \\
& (x^{\frac{r}{2}}+1) \neq K''N \label{eq:k''N}
\end{align}
となる。よって、$(x^{\frac{r}{2}}-1)=p,(x^{\frac{r}{2}}+1)=q$とおくと、
$p,q$は$N$の整数倍ではないことがわかる。

$(x^{\frac{r}{2}}-1)=p,(x^{\frac{r}{2}}+1)=q$を(\ref{eq:kN})に代入すると、
\begin{align}
pq=kN
\end{align}
これより、$p,q/k$、あるいは$p/k,q$が$N$の因数であることがわかる。

以上より、(\ref{eq:xr})を満たす$r$を効率よく見つけることができれば、
因数分解が行えることがわかった。

続いて、これが量子計算を用いて計算できることを示し、
さらにそれが効率よく行えることを示す。