Skip main navigation

Factoring of large numbers

In this video, Rodney Van Meter discusses the importance and difficulty of factoring large numbers as a motivation for quantum computing.

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)のように、簡単に素因数分解が可能です。おそらく2桁の数字に関しても、10までの数の掛け合わせですから、簡単に素因数分解ができることでしょう。しかし、桁が大きくなると、その計算は急速に難しくになっていきます。例えば、(251089)という数はどうでしょうか?(257 times 977)という素因数の組み合わせだとわかるまでにどれだけ時間がかかるでしょうか?

This article is from the free online

Understanding Quantum Computers

Created by
FutureLearn - Learning For Life

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now