General Factorization Algorithm of Buchman-Lenstra

We finally give an algorithm to factor $p\O_K$ in general. This is a summary of the algorithm described in more detail in [Coh93, §6.2].

Algorithm 4.3.7 (Factoring a Finite Separable Algebra)   Let $A$ be a finite separable algebra over $\mathbf{F}_p$. This algorithm either shows that $A$ is a field or finds a nontrivial idempotent in $A$, i.e., an $\varepsilon \in A$ such that $\varepsilon ^2 = \varepsilon$ with $\varepsilon \neq 0$ and $\varepsilon \neq 1$.

1. The dimension of the kernel $V$ of the map $x\mapsto x^p - x$ is equal to $k$. This is because abstractly we have that $A\approx A_1\times \cdots \times A_k$, with each $A_i$ a finite field extension of $\mathbf{F}_p$.
2. If $k=1$ we are done. Terminate.
3. Otherwise, choose $\alpha \in V$ with $\alpha \not\in \mathbf{F}_p$. (Think of $\mathbf{F}_p$ as the diagonal embedding of $\mathbf{F}_p$ in $A_1\times \cdots \times A_k$). Compute powers of $\alpha$ and find the minimal polynomial $m(X)$ of $\alpha$.
4. Since $V\approx \mathbf{F}_p \times \cdots \times F_p$ ($k$ factors), the polynomial $m(X)$ is a square-free product of linear factors, that has degree $>1$ since $\alpha \not\in \mathbf{F}_p$. Thus we can compute a splitting $m(X) = m_1(X) \cdot m_2(X)$, where both $m_i(X)$ have positive degree.
5. Use the Euclidean algorithm in $\mathbf{F}_p[X]$ to find $U_1(X)$ and $U_2(X)$ such that
   $$U_1 m_1 + U_2 m_2 = 1.$$

6. Let $\varepsilon = (U_1 m_1)(\alpha)$. Then we have
   $$U_1 m_1 U_1 m_1 + U_2 m_2 U_1 m_1 = U_1 m_1,$$
   so since $(m_1 m_2)(\alpha) = m(\alpha)=01$, we have $\varepsilon ^2 = \varepsilon$. Also, since $\gcd(U_1, m_2) = \gcd(U_2, m_1) = 1$, we have $\varepsilon \neq 0$ and $\varepsilon \neq 1$.

Given Algorithm 4.3.7, we compute an idempotent $\varepsilon \in A$, and observe that

$$A \cong \Ker (1 - \varepsilon ) \oplus \Ker (\varepsilon ).$$

Since $(1 - \varepsilon ) + \varepsilon = 1$, we see that $(1 - \varepsilon )v + \varepsilon v = v$, so that the sume of the two kernels equals $A$. Also, if $v$ is in the intersection of the two kernels, then $\varepsilon (v) = 0$ and $(1-\varepsilon )(v) =0$, so $0 = (1-\varepsilon )(v) = v - \varepsilon (v) = v$, so the sum is direct.

Remark 4.3.8   The beginning of [Coh93, §6.2.4] suggests that one can just randomly find an $\alpha \in A$ such that $A\cong \mathbf{F}_p[x]/(m(x))$ where $m$ is the minimal polynomial of $\alpha$. This is usually the case, but is wrong in general, since there need not be an $\alpha \in A$ such that $A \cong \mathbf{F}_p[\alpha]$. For example, let $p=2$ and $K$ be as in Example 4.3.2. Then $A\cong \mathbf{F}_2 \times \mathbf{F}_2 \times \mathbf{F}_2$, which as a ring is not generated by a single element, since there are only 2 distinct linear polynomials over $\mathbf{F}_2[x]$.

Algorithm 4.3.9 (Factoring a General Prime Ideal)   Let $K=\mathbf{Q}(a)$ be a number field given by an algebraic integer $a$ as a root of its minimal monic polynomial $f$ of degree $n$. We assume that an order $\O$ has been given by a basis $w_1,\ldots,w_n$ and that $\O$ that contains $\mathbf{Z}[a]$. For any prime $p\in\mathbf{Z}$, the following algorithm computes the set of maximal ideals of $\O$ that contain $p$.

1. [Check if easy] If $p\nmid \disc (\mathbf{Z}[a]) / \disc (\O)$ (so $p\nmid [\O:\mathbf{Z}[a]]$), then using Theorem 4.2.3 we factor $p\O$.
2. [Compute radical] Let $I$ be the radical of $p\O$, which is the ideal of elements $x\in\O$ such that $x^m\in p\O$ for some positive integer $m$. Note that $p\O\subset I$, i.e., $I\mid p\O$; also $I$ is the product of the primes that divide $p$, without multiplicity. Using linear algebra over the finite field $\mathbf{F}_p$, we compute a basis for $I/p\O$ by computing the abelian subgroup of $\O/p\O$ of all nilpotent elements. This computes $I$, since $p\O\subset I$.
3. [Compute quotient by radical] Compute an $\mathbf{F}_p$ basis for
   $$A = \O/I = (\O/p\O)/(I/p\O).$$
   The second equality comes from the fact that $p\O\subset I$. Note that $\O/p\O$ is obtained by simply reducing the basis $w_1,\ldots,w_n$ modulo $p$. Thus this step entirely involves linear algebra modulo $p$.

4. [Decompose quotient] The ring $A$ is isomorphic to the quotient of $\O$ by a radical ideal, so it decomposes as a product $A \cong A_1 \times \cdots \times A_k$ of finite fields. We find such a decomposition explicitly using Algorithm 4.3.7.

5. [Compute the maximal ideals over $p$] Each maximal ideal $\mathfrak{p}_i$ lying over $p$ is the kernel of one of the compositions
   $$\O\to A \approx A_1 \times \cdots \times A_k \to A_i.$$

Algorithm 4.3.9 finds all primes of $\O$ that contain the radical $I$ of $p\O$. Every such prime clearly contains $p$, so to see that the algorithm is correct, we prove that the primes $\mathfrak{p}$ of $\O$ that contain $p$ also contain $I$. If $\mathfrak{p}$ is a prime of $\O$ that contains $p$, then $p\O\subset \mathfrak{p}$. If $x\in I$ then $x^m\in p\O$ for some $m$, so $x^m\in \mathfrak{p}$ which implies that $x\in \mathfrak{p}$ by primality of $\mathfrak{p}$. Thus $\mathfrak{p}$ contains $I$, as required. Note that we do not find the powers of primes that divide $p$ in Algorithm 4.3.9; that's left to another algorithm that we will not discuss in this book.

Algorithm 4.3.9 was invented by J. Buchmann and H.W. Lenstra, though their paper seems to have never been published; however, the algorithm is described in detail in [Coh93, §6.2.5]. Incidentally, this chapter is based on Chapters 4 and 6 of [Coh93], which is highly recommended, and goes into much more detail about these algorithms.