We finally give an algorithm to factor
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

be a finite separable algebra over

. This
algorithm either shows that

is a field or finds
a nontrivial idempotent in

, i.e., an

such that

with

and

.
- The dimension of the kernel
of the map
is
equal to
. This is because abstractly we have that
, with each
a finite field
extension of
.
- If
we are done. Terminate.
- Otherwise, choose
with
.
(Think of
as the diagonal embedding of
in
).
Compute powers of
and find the minimal polynomial
of
.
- Since
(
factors),
the polynomial
is a square-free product of linear factors, that
has degree
since
. Thus we can compute
a splitting
, where both
have
positive degree.
- Use the Euclidean algorithm in
to find
and
such that
- Let
. Then we have
so since
, we have
.
Also, since
,
we have
and
.
Given Algorithm 4.3.7, we compute an idempotent
, and observe that
Since
, we see that
, so that the sume
of the two kernels equals
.
Also, if
is in the intersection of the two kernels,
then
and
, so
, so the sum is direct.
Remark 4.3.8
The beginning of [
Coh93, §6.2.4] suggests that one
can just randomly find an

such that
![$ A\cong
\mathbf{F}_p[x]/(m(x))$](img761.png)
where

is the minimal polynomial of

.
This is usually the case, but is
wrong in general, since there
need
not be an

such that
![$ A \cong
\mathbf{F}_p[\alpha]$](img762.png)
. For example, let

and

be as in
Example
4.3.2. Then

, which as a ring is not generated by a single element, since
there are only 2 distinct linear polynomials over
![$ \mathbf{F}_2[x]$](img694.png)
.
Algorithm 4.3.9 finds all primes of
that contain the radical
of
. Every such prime clearly contains
, so to see that the
algorithm is correct, we prove that the primes
of
that
contain
also contain
. If
is a prime of
that
contains
, then
. If
then
for some
, so
which implies that
by primality
of
. Thus
contains
, as required. Note that we do not find the powers of
primes that divide
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.
William Stein
2012-09-24