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

$$\xymatrix{ {{\displaystyle \bigcup}\Spec (\O _K/\mathfrak{p}_i^{e... ...pec(\Z[x]/f(x))\\ {\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

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

and the top horizontal map is induced by

$$\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

$$\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

$$\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

$$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

$$\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

$$\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

$$\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

$$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
2945785
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)
2945785

We have

$$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()
235050861175510968365785
sage: factor(f.disc() / K.disc())
7^20
sage: f.factor_mod(5)
(x + 4) * (x + 1)^2 * (x^2 + 3*x + 3)

Thus $5$ factors in $\O_K$ as

$$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)
x^5