# 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 be a number field, and let be the ring of integers of . To employ our geometric intuition, as the Lenstras did on the cover of [LL93], it is helpful to view as a one-dimensional scheme

all prime ideals of $O_K$

over

is prime

There is a natural map that sends a prime ideal to . 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 is a prime number, then the ideal of factors uniquely as a product , where the are maximal ideals of . We may imagine the decomposition of into prime ideals geometrically as the fiber (with multiplicities).

How can we compute in practice?

Example 8.1.1   The following session shows the commands needed to compute the factorization of in for  the number field defined by a root of .
   > 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 is already a prime ideal, and

Notice that in this example . (Warning: There are examples of such that for any , as Example 8.1.6 below illustrates.) When it is very easy to factor , as we will see below. The following factorization gives a hint as to why:

The exponent  of in the factorization of above suggests ramification'', in the sense that the cover has less points (counting their size'', i.e., their residue class degree) in its fiber over  than it has generically. Here's a suggestive picture:

Diagram of

Subsections
William Stein 2004-05-06