If you have heard of quantum computers before, you have probably heard that they can factor large numbers. Factoring seems simple, if you think about small numbers: it’s easy to see that (6 = 3 times 2). You can probably find the factors of a two-digit number easily; you really only need to try numbers up to about ten. But as numbers get bigger, it gets harder very quickly. What if I give you the number (251089)? How long will it take you to figure out that it is (257 times 977)?

大きな数の素因数分解

もし量子コンピュータについて聞いたことがあったなら、おそらく大きな数の素因数分解についても、聞いたことがあるのではないでしょうか？　 小さな数についての素因数分解であれば、簡単に考えることができると思います。例えば、(6 = 3 times 2)のように、簡単に素因数分解が可能です。おそらく２桁の数字に関しても、10までの数の掛け合わせですから、簡単に素因数分解ができることでしょう。しかし、桁が大きくなると、その計算は急速に難しくになっていきます。例えば、(251089)という数はどうでしょうか？(257 times 977)という素因数の組み合わせだとわかるまでにどれだけ時間がかかるでしょうか？