 |
Tutorial
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
|
