Factoring of large numbers/大きな数の素因数分解

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.