The Problem

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

Bill Gates meant^4.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

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