A Method for Factoring Primes that Often Works

Suppose $ a\in\O_K$ is such that $ K=\mathbf{Q}(a)$, and let $ f(x) \in \mathbf{Z}[x]$ be the minimal polynomial of $ a$. Then $ \mathbf{Z}[a]\subset \O_K$, and we have a diagram of schemes

$\displaystyle \xymatrix{
{{\displaystyle \bigcup}\Spec (\O _K/\mathfrak{p}_i^{e...
{\Spec (\mathbf{F}_p) }\ar@{^(->}[r]&{\Spec (\mathbf{Z})}

where $ \overline{f} = \prod_i \overline{f}_i^{e_i}$ is the factorization of the image of $ f$ in $ \mathbf{F}_p[x]$, and $ p\O_K = \prod \mathfrak{p}_i^{e_i}$ is the factorization of $ p\O_K$ in terms of prime ideals of $ \O_K$. On the level of rings, the bottom horizontal map is the quotient map $ \mathbf{Z}\to\mathbf{Z}/p\mathbf{Z}\cong \mathbf{F}_p$. The middle horizontal map is induced by

$\displaystyle \mathbf{Z}[x] \to \bigoplus_i \mathbf{F}_p[x]/(\overline{f}_i^{e_i}),

and the top horizontal map is induced by

$\displaystyle \O_K \to \O_K/p\O_K \cong \bigoplus \O_K/\mathfrak{p}_i^{e_i},

where the isomorphism is by the Chinese Remainder Theorem, which we will prove in Chapter 5. The left vertical maps come from the inclusions

$\displaystyle \mathbf{F}_p \hookrightarrow \mathbf{F}_p[x]/(\overline{f}_i^{e_i}) \hookrightarrow \O_K/\mathfrak{p}_i^{e_i},

and the right from the inclusions $ \mathbf{Z}\hookrightarrow \mathbf{Z}[a]\hookrightarrow \O_K$.

The cover $ \pi:\Spec (\mathbf{Z}[a])\rightarrow \Spec (\mathbf{Z})$ is easy to understand because it is defined by the single equation $ f(x)$, in the sense that $ \mathbf{Z}[a]\cong \mathbf{Z}[x]/(f(x))$. To give a maximal ideal  $ \mathfrak{p}$ of $ \mathbf{Z}[a]$ such that $ \pi(\mathfrak{p}) = p\mathbf{Z}$ is the same as giving a homomorphism $ \varphi :\mathbf{Z}[x]/(f) \rightarrow \overline{\mathbf{F}}_p$ up to automorphisms of the image, which is in turn the same as giving a root of $ f$ in $ \overline{\mathbf{F}}_p$ up to automorphism, which is the same as giving an irreducible factor of the reduction of $ f$ modulo $ p$.

Lemma 4.2.1   Suppose the index of $ \mathbf{Z}[a]$ in $ \O_K$ is coprime to $ p$. Then the primes  $ \mathfrak{p}_i$ in the factorization of $ p\mathbf{Z}[a]$ do not decompose further going from $ \mathbf{Z}[a]$ to $ \O_K$, so finding the prime ideals of $ \mathbf{Z}[a]$ that contain $ p$ yields the primes that appear in the factorization of $ p\O_K$.

Proof. Fix a basis for $ \O_K$ and for $ \mathbf{Z}[a]$ as $ \mathbf {Z}$-modules. Form the matrix $ A$ whose columns express each basis element of $ \mathbf{Z}[a]$ as a $ \mathbf {Z}$-linear combination of the basis for $ \O_K$. Then

$\displaystyle \det(A) = \pm [\O_K:\mathbf{Z}[a]]

is coprime to $ p$, by hypothesis. Thus the reduction of $ A$ modulo $ p$ is invertible, so it defines an isomorphism $ \mathbf{Z}[a]/p\mathbf{Z}[a] \cong \O_K/p\O_K$.

Let $ \overline{\mathbf{F}}_p$ denote a fixed algebraic closure of $ \mathbf{F}_p$; thus $ \overline{\mathbf{F}}_p$ is an algebraically closed field of characteristic $ p$, over which all polynomials in $ \mathbf{F}_p[x]$ factor into linear factors. Any homomorphism $ \O_K\to \overline{\mathbf{F}}_p$ sends $ p$ to 0, so is the composition of a homomorphism $ \O_K \to \O_K/p\O_K$ with a homomorphism $ \O_K/p\O_K \to \overline{\mathbf{F}}_p$. Since $ \O_K/p\O_K \cong
\mathbf{Z}[a]/p\mathbf{Z}[a]$, the homomorphisms $ \O_K\to \overline{\mathbf{F}}_p$ are in bijection with the homomorphisms $ \mathbf{Z}[a]\to \overline{\mathbf{F}}_p$. The homomorphisms $ \mathbf{Z}[a]\to \overline{\mathbf{F}}_p$ are in bijection with the roots of the reduction modulo $ p$ of the minimal polynomial of $ a$ in $ \overline{\mathbf{F}}_p$. $ \qedsymbol$

Remark 4.2.2   Here is a ``high-brow'' proof of Lemma 4.2.1. By hypothesis we have an exact sequence of abelian groups

$\displaystyle 0 \to \mathbf{Z}[a]\to \O_K \to H \to 0,$

where $ H$ is a finite abelian group of order coprime to $ p$. Tensor product is right exact, and there is an exact sequence

$\displaystyle \Tor _1(H,\mathbf{F}_p) \to \mathbf{Z}[a]\otimes \mathbf{F}_p \to \O_K\otimes \mathbf{F}_p \to H\otimes \mathbf{F}_p \to 0,

and $ \Tor _1(H,\mathbf{F}_p) = 0$ (since $ H$ has no $ p$-torsion), so $ \mathbf{Z}[a]\otimes \mathbf{F}_p\cong \O_K\otimes \mathbf{F}_p$.

As suggested in the proof of the lemma, we find all homomorphisms $ \O_K\to \overline{\mathbf{F}}_p$ by finding all homomorphism $ \mathbf{Z}[a]\to \overline{\mathbf{F}}_p$. In terms of ideals, if $ \mathfrak{p}=(f(a),p)\mathbf{Z}[a]$ is a maximal ideal of $ \mathbf{Z}[a]$, then the ideal $ \mathfrak{p}'=(f(a),p)\O_K$ of $ \O_K$ is also maximal, since

$\displaystyle \O_K/\mathfrak{p}'\cong (\O_K/p\O_K)/(f(\tilde{a}))
\cong (\mathbf{Z}[a]/p\mathbf{Z}[a]) / (f(\tilde{a})) \subset \overline{\mathbf{F}}_p,$

where $ \tilde{a}$ denotes the image of $ a$ in $ \O_K/p\O_K$.

We formalize the above discussion in the following theorem (note: we will not prove that the powers are $ e_i$ here):

Theorem 4.2.3   Let $ f\in\mathbf{Z}[x]$ be the minimal polynomial of $ a$ over  $ \mathbf {Z}$. Suppose that  $ p\nmid [\O_K:\mathbf{Z}[a]]$ is a prime. Let

$\displaystyle \overline{f} = \prod_{i=1}^t \overline{f}_i^{e_i} \in \mathbf{F}_p[x]

where the $ \overline{f}_i$ are distinct monic irreducible polynomials. Let $ \mathfrak{p}_i = (p,f_i(a))
$ where $ f_i\in\mathbf{Z}[x]$ is a lift of $ \overline{f}_i$ in $ \mathbf{F}_p[x]$. Then

$\displaystyle p\O_K = \prod_{i=1}^t \mathfrak{p}_i^{e_i}.

We return to the example from above, in which $ K=\mathbf{Q}(a)$, where $ a$ is a root of $ f = x^5+7x^4+3x^2-x+1$. According to SAGE, the ring of integers $ \O_K$ has discriminant $ 2945785 = 5\cdot 353\cdot 1669$:

sage: K.<a> = NumberField(x^5 + 7*x^4 + 3*x^2 - x + 1)
sage: D = K.discriminant(); D
sage: factor(D)
5 * 353 * 1669
The order $ \mathbf{Z}[a]$ has the same discriminant as $ f(x)$, which is the same as the discriminant of $ \O_K$, so $ \mathbf{Z}[a]=\O_K$ and we can apply the above theorem. (Here we use that the index of $ \mathbf{Z}[a]$ in $ \O_K$ is the square of the quotient of their discriminants, a fact we will prove later in Section 6.2.)
sage: R.<x> = QQ[]
sage: discriminant(x^5 + 7*x^4 + 3*x^2 - x + 1)
We have

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

which yields the factorization of $ 5\O_K$ given before the theorem.

If we replace $ a$ by $ b=7a$, then the index of $ \mathbf{Z}[b]$ in $ \O_K$ will be a power of $ 7$, which is coprime to $ 5$, so the above method will still work.

sage: K.<a> = NumberField(x^5 + 7*x^4 + 3*x^2 - x + 1)
sage: f = (7*a).minpoly('x')
sage: f
x^5 + 49*x^4 + 1029*x^2 - 2401*x + 16807
sage: f.disc()
sage: factor(f.disc() / K.disc())
sage: f.factor_mod(5)
(x + 4) * (x + 1)^2 * (x^2 + 3*x + 3)
Thus $ 5$ factors in $ \O_K$ as

$\displaystyle 5\O_K = (5, 7a+1)^2 \cdot (5, 7a+4) \cdot (5, (7a)^2 + 3(7a) + 3).

If we replace $ a$ by $ b=5a$ and try the above algorithm with $ \mathbf{Z}[b]$, then the method fails because the index of $ \mathbf{Z}[b]$ in $ \O_K$ is divisible by $ 5$.
sage: K.<a> = NumberField(x^5 + 7*x^4 + 3*x^2 - x + 1)
sage: f = (5*a).minpoly('x')
sage: f
x^5 + 35*x^4 + 375*x^2 - 625*x + 3125
sage: f.factor_mod(5)

William Stein 2012-09-24