A Method for Factoring that Often Works

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

$$\xymatrix{ {(??) }\ar@{^(->}[r]\ar[d] &{\Spec (\O _K)}\ar[d] \\... ...pec(\Z[x]/g(x))\\ {\Spec (\mathbf{F}_p) }\ar@{^(->}[r]&{\Spec (\mathbf{Z})} }$$

where $\overline{g} = \prod_i \overline{g}_i^{e_i}$ is the factorization of the image of $g$ in $\mathbf{F}_p[x]$.

The cover $\pi:\Spec (\mathbf{Z}[a])\rightarrow \Spec (\mathbf{Z})$ is easy to understand because it is defined by the single equation $g(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]/(g) \rightarrow \overline{\mathbf{F}}_p$ (up to automorphisms of the image), which is in turn the same as giving a root of $g$ in $\overline{\mathbf{F}}_p$ (up to automorphism), which is the same as giving an irreducible factor of the reduction of $g$ modulo $p$.

Lemma 8.1.2   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 factorization of $p\O _K$.

Proof. Hi-brow argument: 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)= H\otimes \mathbf{F}_p = 0$, so $\mathbf{Z}[a]\otimes \mathbf{F}_p\cong \O _K\otimes \mathbf{F}_p$.
Low-brow argument: The inclusion map $\mathbf{Z}[a]\hookrightarrow \O _K$ is defined by a matrix over $\mathbf{Z}$ that has determinant $\pm [\O _K:\mathbf{Z}[a]]$, which is coprime to $p$. The reduction of this matrix modulo $p$ is invertible, so it defines an isomorphism $\mathbf{Z}[a]\otimes \mathbf{F}_p \to \O _K\otimes \mathbf{F}_p$. Any homomorphism $\O _K\to \overline{\mathbf{F}}_p$ is the composition of a homomorphism $\O _K \to \O _K\otimes \mathbf{F}_p$ with a homomorphism $\O _K\otimes \mathbf{F}_p \to \overline{\mathbf{F}}_p$. Since $\O _K\otimes \mathbf{F}_p\cong \mathbf{Z}[a]\otimes \mathbf{F}_p$, the homomorphisms $\O _K\to \overline{\mathbf{F}}_p$ are in bijection with the homomorphisms $\mathbf{Z}[a]\to \overline{\mathbf{F}}_p$, which proves the lemma. $\qedsymbol$

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}=(g(a),p)\mathbf{Z}[a]$ is a maximal ideal of $\mathbf{Z}[a]$, then the ideal $\mathfrak{p}'=(g(a),p)\O _K$ of $\O _K$ is also maximal, since

$$\O _K/\mathfrak{p}'\cong (\O _K\otimes \mathbf{F}_p)/(g(\tilde{a}... ...bf{Z}[a]\otimes \mathbf{F}_p) / (g(\tilde{a})) \subset \overline{\mathbf{F}}_p.$$

We formalize the above discussion in the following theorem:

Theorem 8.1.3   Let $f(x)$ denote the minimal polynomial of $a$ over  $\mathbf{Q}$. 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 $x^5+7x^4+3x^2-x+1$. According to , the maximal order $\O _K$ has discriminant $2945785$:

   > Discriminant(MaximalOrder(K));
   2945785

The order $\mathbf{Z}[a]$ has the same discriminant as $\O _K$, so $\mathbf{Z}[a]=\O _K$ and we can apply the above theorem.

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

   > f:=MinimalPolynomial(7*a);
   > f;
   x^5 + 49*x^4 + 1029*x^2 - 2401*x + 16807
   > Discriminant(f);
   235050861175510968365785
   > Discriminant(f)/Discriminant(MaximalOrder(K));
   79792266297612001    // coprime to 5
   > S<t> := PolynomialRing(GF(5));
   > Factorization(S!f);
   [
       <t + 1, 2>,
       <t + 4, 1>,
       <t^2 + 3*t + 3, 1>
   ]

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

   > f:=MinimalPolynomial(5*a);
   > f;
   x^5 + 35*x^4 + 375*x^2 - 625*x + 3125
   > Discriminant(f) / Discriminant(MaximalOrder(K));
   95367431640625    // divisible by 5
   > Factorization(S!f);
   [
       <t, 5>
   ]