古典計算機で大きな整数を因数分解しようとすると、
効率よく解くことができない。

効率よく解けないということは、整数$N$が大きくなると、
計算に時間がかかって、事実上解けなくなることを意味する。

簡単な例としては、$N$の因数を発見するために小さい数からはじめて
$N$が割り切れるかどうか調べて、ちょうど真ん中の
$\sqrt{N}$まで調べればよいことが知られていて、$\sqrt{N}$回程度の計算を要する。

現在まで知られている一番速いアルゴリズムでも、
$\exp \left[ c \log N \left( \frac{\log \log N}{\log N} \right) ^\frac{2}{3} \right]$ステップ程度かかり、
指数時間よりは速いが多項式時間よりは遅い。

このことを逆手に取ったものが素数を鍵に用いる公開鍵方式の暗号システムである。

量子計算機を用いれば、因数分解を圧倒的に速く実行できることをショアが示した。
以下でその概要を説明する。