Factoring Primes

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, pg. 265

Let $K=\mathbf{Q}(\alpha)$ be a number field, and let $\O _K$ be the ring of integers of $K$. To employ our geometric intuition, as the Lenstras did on the cover of [LL93], it is helpful to view $\O _K$ as a one-dimensional scheme

$$X = \Spec (\O _K) = \{$$ all prime ideals of $O_K$ $$\}$$

over

$$Y=\Spec (\mathbf{Z}) = \{ (0) \} \cup \{ p\mathbf{Z}: p \in\mathbf{Z}$$ is prime $$\}.$$

There is a natural map $\pi :X\rightarrow Y$ that sends a prime ideal $\mathfrak{p}\in X$ to $\mathfrak{p}\cap \mathbf{Z}\in Y$. For much more on this point of view, see [EH00, Ch. 2].

Ideals were originally introduced by Kummer because, as we proved last Tuesday, in rings of integers of number fields ideals factor uniquely as products of primes ideals, which is something that is not true for general algebraic integers. (The failure of unique factorization for algebraic integers was used by Liouville to destroy Lamé's purported 1847 ``proof'' of Fermat's Last Theorem.)

If $p\in\mathbf{Z}$ is a prime number, then the ideal $p\O _K$ of $\O _K$ factors uniquely as a product $\prod \mathfrak{p}_i^{e_i}$, where the $\mathfrak{p}_i$ are maximal ideals of $\O _K$. We may imagine the decomposition of $p\O _K$ into prime ideals geometrically as the fiber $\pi^{-1}(p\mathbf{Z})$ (with multiplicities).

How can we compute $\pi^{-1}(p\mathbf{Z})$ in practice?

Example 8.1.1   The following session shows the commands needed to compute the factorization of $p\O _K$ in for $K$ the number field defined by a root of $x^5+7x^4+3x^2-x+1$.

   > R<x> := PolynomialRing(RationalField());
   > K<a> := NumberField(x^5 + 7*x^4 + 3*x^2 - x + 1);
   > OK := MaximalOrder(K);
   > I := 2*OK;
   > Factorization(I);
   [
   <Principal Prime Ideal of OK
   Generator:
   [2, 0, 0, 0, 0], 1>
   ]
   > J := 5*OK;
   > Factorization(J);
   [
   <Prime Ideal of OK
   Two element generators:
   [5, 0, 0, 0, 0]
   [2, 1, 0, 0, 0], 1>,
   <Prime Ideal of OK
   Two element generators:
   [5, 0, 0, 0, 0]
   [3, 1, 0, 0, 0], 2>,
   <Prime Ideal of OK
   Two element generators:
   [5, 0, 0, 0, 0]
   [2, 4, 1, 0, 0], 1>
   ]
   > [K!OK.i : i in [1..5]];
   [ 1, a, a^2, a^3, a^4 ]

Thus $2\O _K$ is already a prime ideal, and

$$5\O _K = (5,2+a)\cdot(5,3+a)^2\cdot(5,2+4a+a^2).$$

Notice that in this example $\O _K=\mathbf{Z}[a]$. (Warning: There are examples of $\O _K$ such that $\O _K\neq \mathbf{Z}[a]$ for any $a\in\O _K$, as Example 8.1.6 below illustrates.) When $\O _K=\mathbf{Z}[a]$ it is very easy to factor $p\O _K$, as we will see below. The following factorization gives a hint as to why:

$$x^5+7x^4+3x^2-x+1 \equiv (x+2)\cdot (x+3)^2 \cdot (x^2+4x+2)\pmod{5}.$$

The exponent $2$ of $(5,3+a)^2$ in the factorization of $5\O _K$ above suggests ``ramification'', in the sense that the cover $X\rightarrow Y$ has less points (counting their ``size'', i.e., their residue class degree) in its fiber over $5$ than it has generically. Here's a suggestive picture:

Diagram of $\Spec (\O _K) \rightarrow \Spec (\mathbf{Z})$