Why is Integer Factorization Important?
The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length.... Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.
—Karl Friedrich Gauss, Disquisitiones Arithmeticae (1801) (translation: A. A. Clarke)
Much of modern encryption is accomplished by a system known as public-key cryptography. In this system, a person has a public key and a private key. The public key is used for encryption and may be used by anyone: thus it can, even should, be made public. The private key is used for decryption and therefore must be kept a secret by the person who holds it. Public-key cryptography is designed so that private keys are "computationally infeasible" to obtain from the corresponding public keys. Many public-key cryptosystems are based on the fact that it is very difficult for classical computers to factor large integers: a problem which is theoretically quite simple for a quantum computer. The world of cryptology is very concerned with the feasibility of quantum computers for obvious reasons. Interestingly, while quantum mechanics poses such a threat to cryptography, it also provides a solution in the form of quantum cryptography.
Table of Contents