The Problem

Image spec
A diagram from [LL93].

``The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers.''
- Bill Gates, The Road Ahead, 1st ed., pg 265

Image gates

Bill Gates meant4.1 factoring products of two primes, which would break the RSA cryptosystem (see e.g. [Ste09, §3.2]). However, perhaps Gates is an algebraic number theorist, and he really meant what he said: then we might imagine that he meant factorization of primes of  $ \mathbf {Z}$ in rings of integers of number fields. For example, $ 2^{16}+1 = 65537$ is a ``large'' prime, and in $ \mathbf{Z}[i]$ we have

$\displaystyle (65537) = (65537, 2^8 + i) \cdot (65537, 2^8 - i).$


William Stein 2012-09-24