We use cookies to give you a better experience. Carry on browsing if you're happy with this, or read our cookies policy for more information.

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. Why is this a big deal? Factoring seems simple, if you think about small numbers. It’s easy to see that 6 = 3 x 2. You can probably find the factors of a two-digit number easily, you really only need to think about numbers up to about 10 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 that is 257 x 977? Or consider the nine-digit number 106978891.
If I give you a ten-digit number instead, there are about ten times as many possible factors, and it would take you about three times as long to find the factors. You only have to check values up to the square root of the number. If I gave you an eleven-digit number, it would take you about ten times as long to check as that nine-digit number. In fact, every time we add two digits to the number, the problem will get ten times as hard. If I give you a fifteen-digit number, it will be about a thousand times as hard as that nine-digit number.
Of course, a computer is faster than a human but for a classical computer, solving this problem is faster but no “easier” than it is for a human. That is, a human and a computer both have the same computational complexity behavior as we discussed earlier this week. We can say that, using this simple approach, factoring is O(√10^n) for an n-digit number. That is order of √(10^n). Faster algorithms exist, this is just an example of how to think about the problem. The largest ordinary number factored is 768 bits or 232 decimal digits long using a technique known as the “general number field sieve.” We don’t need to worry about its actual computational complexity but it is said to be subexponential but superpolynomial.
So why do we care? Other than being of interest to number aficionados and mathematicians, why does it matter that factoring large numbers might suddenly become easier with a quantum computer? Right now, you are probably watching this video over an encrypted connection on the World Wide Web. That encryption helps keep your communication secret from prying eyes.
Encrypted communication consists of several phases: First, authentication that you are really talking to the person or web server that you think you are. Second, key exchange to create a special secret key, and third bulk data encryption where special mathematical functions are applied to your data to make its contents difficult to read before sending it across the network. Two of those three phases are mathematically related to factoring. Authentication is often performed using public key cryptography, the most famous form of which is RSA, created by Rivest, Shamir and Adelman. Key exchange is often performed using Diffie-Hellman key exchange.
An efficient means of factoring could allow someone to eavesdrop on your web surfing and other internet-based communication, even with your bank or other financial institutions. It could also impact digital signatures which also depend on public-key cryptography. In 1994, Peter Shor announced to the world that he had figured out how to factor efficiently on a quantum computer. Prior to this announcement, quantum computing was a quiet field and something of an intellectual curiosity. Shor’s algorithm showed that quantum computers can potentially solve problems of economic and social interest. It’s not too much to say that this is the algorithm that got everyone excited, resulting in a big influx of both people and research dollars into the field.
Using Shor’s algorithm, a quantum computer can solve the problem of factoring more “easily” as the numbers get bigger. It can factor in polynomial time, or specifically O(n^3) for an n-digit number. This is much faster than the O(√10^n) we saw above using a classical computer and indeed, it’s much faster than any known classical algorithm. The discovery of Shor’s algorithm attracted new researchers in both theory and experiment and resulted in a huge influx of funding from governments in the mid-1990s.
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

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education