arXiv:1509.08843v2 [] 4 Oct 2016

ALGORITHMS FOR COMMUTATIVE ALGEBRAS OVER THE RATIONAL
NUMBERS
H. W. LENSTRA, JR. AND A. SILVERBERG
Abstract. The algebras considered in this paper are commutative rings of which the additive
group is a finite-dimensional vector space over the field of rational numbers. We present deterministic polynomial-time algorithms that, given such an algebra, determine its nilradical, all of
its prime ideals, as well as the corresponding localizations and residue class fields, its largest separable subalgebra, and its primitive idempotents. We also solve the discrete logarithm problem
in the multiplicative group of the algebra. While deterministic polynomial-time algorithms were
known earlier, our approach is different from previous ones. One of our tools is a primitive element algorithm; it decides whether the algebra has a primitive element and, if so, finds one, all in
polynomial time. A methodological novelty is the use of derivations to replace a Hensel-Newton
iteration. It leads to an explicit formula for lifting idempotents against nilpotents that is valid in
any commutative ring.

1. Introduction
In the present paper, we mean by a Q-algebra a commutative ring E of which the additive
group is a finite-dimensional vector space over the field Q of rational numbers. We give deterministic polynomial-time algorithms for several basic computational questions one may ask about
Q-algebras, taking an approach that differs from previous ones. The reader wishing to implement
our algorithms is warned that we have attempted to optimize the efficiency of our proofs rather than
of our algorithms.
In algorithms, we specify a Q-algebra E by listing a system of “structure constants” aijk ∈ Q,
for i, j, k ∈ {1, 2, . . . , n}, where n = dimQ (E). ThesePdetermine the multiplication, in the sense that
n
for some Q-basis e1 , e2 , . . . , en of E one has ei ej = k=1 aijk ek for all i, j. Elements of E are then
represented by their vector of coordinates on that basis, Q-algebra homomorphisms are represented
by matrices, and ideals and subalgebras of E by Q-bases for them, expressed in e1 , e2 , . . . , en .
The Jordan-Chevalley decomposition. Let E be a Q-algebra. We call α ∈ E nilpotent if there
r
is a√
positive
√ integer r with α = 0. The set of nilpotent elements of E is the nilradical of E, denoted
by 0 or 0E . We call a polynomial f ∈ Q[X] separable if f is coprime to its derivative f ′ , and
α ∈ E is called separable (over Q) if there exists a separable polynomial f ∈ Q[X] with f (α) = 0.
We write Esep for the set of separable elements of E.
The following result is well known.
√
Theorem 1.1. Let E be a Q-algebra as defined above. Then the nilradical 0 is an ideal of E, and
Esep is a sub-Q-algebra of E. Also, one has
√
E = Esep ⊕ 0
√
in the sense that the map Esep ⊕ 0 → E, (u, v) 7→ u + v is an isomorphism of Q-vector spaces.
2010 Mathematics Subject Classification. Primary: 13E10, Secondary: 13P99, 68W30.
Key words and phrases. finite-dimensional commutative algebras, algorithms, Jordan-Chevalley decomposition,
lifting idempotents.
Support for the research was provided by the Alfred P. Sloan Foundation.
1

2

H. W. LENSTRA, JR. AND A. SILVERBERG

Writing an element of E as the sum of a separable element and a nilpotent element may be viewed
as its Jordan-Chevalley decomposition or Dunford decomposition. We give a proof of Theorem 1.1
in section 2, using a Hensel-Newton iteration.
In section 5 we exhibit a polynomial-time algorithm for achieving the Jordan-Chevalley decomposition (Algorithm 5.1). Interestingly, it gives rise to a method for determining the nilradical that
differs from the traditional way of doing this, which depends on the trace function (see section 4.4
of [3]). And more interestingly, we compute the subalgebra Esep at the same time. Altogether, we
obtain the following result, which will be used in several later algorithms.
Theorem 1.2. There is a deterministic polynomial-time
algorithm that, given a Q-algebra E,
√
computes
a
Q-basis
for
E
and
a
Q-basis
for
0,
as
well
as the matrix describing the √
map
sep
√
Esep ⊕ 0 → E from Theorem 1.1 and its inverse (which describes the inverse map E → Esep ⊕ 0).
An algorithm as in Theorem 1.2 can also be found in the Appendix to [1]. It is a Hensel iteration,
carefully formulated so as to avoid coefficient blow-up. Our own proof of Theorem 1.2, which is
given in section 5, uses no iteration at all. It depends on the following result, in which h′ denotes
the formal derivative of h ∈ Q[X].
Theorem 1.3. Let g ∈ Q[X] be non-zero, and let E be the Q-algebra Q[X]/(g). Then there is a
well-defined surjective Q-linear map
δ : Q[X]/(g) → Q[X]/(g, g ′ )
sending h + (g) to h′ + (g, g ′ ), and its kernel equals Esep .
For the proof, see section 4.
One may wonder whether the method for determining Esep that is described in Theorem 1.3
applies directly to any Q-algebra. That is, if E is a Q-algebra, with module of Kähler differentials
ΩE/Q and universal derivation d : E → ΩE/Q , is ker(d) necessarily equal to Esep ? (See [2] for the
unexplained terms.) We are grateful to Maarten Derickx for having provided a counterexample:
if I ⊂ Q[X, Y ] denotes the ideal (5X 4 + Y 3 , 3XY 2 + 4Y 3 , Y 5 ) then f = X 5 + XY 3 + Y 4 + I ∈
Q[X, Y ]/I = E satisfies f ∈ ker(d) while f ∈
/ Esep = Q · 1.
Lifting idempotents against nilpotents. As an example, we
√discuss the algebra E = Q[X]/(g),
where g = X m (1 − X)n with m, n ∈ Z>0 . The nilradical 0 of E is the ideal generated by
X(1 − X) + (g), and by Theorem 1.1 the natural map
√ ∼
→ Q[X]/(X(1 − X))
Esep → E/ 0 −
is an isomorphism of Q-algebras. It follows that there is a unique element y ∈ Esep that maps to
X + (X(1 − X)), and that this element satisfies y(1 − y) = 0 and Esep = Q · 1 ⊕ Q · y. By Theorem
1.3, we have y = f + (g), where f ∈ Q[X] is characterized by
deg(f ) < n + m,

f ≡ X mod X(1 − X),

f ′ ≡ 0 mod (g, g ′ ),

where (g, g ′ ) = X m−1 (1 − X)n−1 . Note that from y(1 − y) = 0 it follows that X m (1 − X)n
divides f (1 − f ), and because the condition f ≡ X mod X(1 − X) implies gcd(1 − f, X) = 1 and
gcd(f, 1 − X) = 1, one obtains
f ≡ 0 mod X m ,

1 − f ≡ 0 mod (1 − X)n .

It turns out that in this case we can give explicit formulas for the polynomial f . These are contained
in the following result, which is in fact valid for any ring, commutative or not, and in which m = 0,
n = 0 are also allowed.

ALGORITHMS FOR COMMUTATIVE ALGEBRAS OVER THE RATIONAL NUMBERS

3

Theorem 1.4. Let R be a ring, and m, n ∈ Z≥0 . Then there is a unique polynomial f ∈ R[X]
satisfying
deg(f ) < m + n,

f ∈ R[X] · X m ,

f ∈ 1 + R[X] · (1 − X)n ,

and it is given by



m+n−1
m+n−1
X
X m + n − 1
m+n−1
i−1
X i.
(−1)i−m
X i (1 − X)m+n−1−i =
f=
i
i
−
m
i
i=m
i=m
This polynomial satisfies f 2 ≡ f mod R[X] · X m (1 − X)n .
For the proof of Theorem 1.4 see section 4. For m = n = 2 one obtains f = 3X 2 − 2X 3 , a
polynomial that is well known in this context (cf. [1], section 3.2).
An idempotent of a commutative ring R is an element e ∈ R such that e2 = e. In addition to
providing an example illustrating Theorem 1.3, Theorem 1.4 gives an explicit formula for lifting
idempotents
in commutative rings; that√ is, if R is a commutative ring with
√ against nilpotents
√
√
nilradical 0, and α + 0 is an idempotent in the ring R/ 0, then there is a unique y ∈ α + 0
that is an idempotent in R, and the following result tells us how to write it down.
Theorem 1.5. Let R be a commutative ring, suppose m, n ∈ Z≥0 , and suppose α ∈ R satisfies
αm (1 − α)n = 0.
Then there is a unique y ∈ R satisfying
y − α is nilpotent,

y 2 = y,

and it is given by y = f (α), with f as in Theorem 1.4.
For the proof, see section 4.
In principle one can use Theorems 1.4 and 1.5 for algorithmic purposes, but we shall not do so
in the present paper.
Primitive elements. Let E be a Q-algebra. For α ∈ E, we denote by Q[α] the subalgebra of E
generated by α; it is the image of the ring homomorphism Q[X] → E sending f ∈ Q[X] to f (α) ∈ E.
We call α ∈ E a primitive element for E if Q[α] = E.
Theorem 1.6. For any Q-algebra E, the subalgebra Esep has a primitive element. In addition,
there is a deterministic polynomial-time algorithm (Algorithm 6.3 below) that, given a Q-algebra E,
produces α ∈ E with Esep = Q[α].
For the proof of Theorem 1.6, including the algorithm, see section 6. We will find Theorem 1.6
useful in determining Spec(E).
General Q-algebras do not need to have primitive elements (see Example 6.5).
Theorem 1.7. (i) For any Q-algebra E, the following four statements are equivalent:
(a) E has a primitive element;
√
√
(b) √
for each m ∈ Spec(E), the E/m-vector space 0/m 0 has dimension at most 1;
(c) 0 is a principal ideal of E;
(d) each ideal of E is a principal ideal.
(ii) There is a deterministic polynomial-time algorithm that, given a Q-algebra E, decides whether E
has a primitive element, and if so finds one.
For the proof of (i) see section 6. For (ii) and the algorithm see section 7.

4

H. W. LENSTRA, JR. AND A. SILVERBERG

The spectrum and idempotents. The spectrum Spec(R) of a commutative ring R is its set of
prime ideals. For m ∈ Spec(R), we write Rm for the localization of R at m. A primitive idempotent
of R is an idempotent e 6= 0 of R such that for all idempotents e′ ∈ R we have e′ e ∈ {0, e}.
The following result assembles basic structural information about Q-algebras.
Theorem 1.8. Let E be a Q-algebra. Then:
(i) for each m ∈ Spec(E), the local ring Em is a Q-algebra with a nilpotent maximal ideal, its
residue class field is E/m, and E/m is a field extension
of Q of finite degree;
Q
(ii) Spec(E) is finite, and the natural map E → m∈Spec(E) Em is an isomorphism of Qalgebras;
√
Q
(iii) the natural map E → m∈Spec(E) E/m is surjective, and its kernel equals the nilradical 0;
(iv) the restriction of the map in (iii) to Esep is a Q-algebra isomorphism
Y
∼
E/m.
→
Esep −
m∈Spec(E)

Theorem 1.8 is by no means new, but since it can be quickly obtained from Theorem 1.1, we
include a proof in section 3.
We next consider an algorithmic counterpart of Theorem 1.8. Part (iii) of Theorem 1.8 readily
implies that determining all m ∈ Spec(E), as well as their residue class fields E/m
√ and the maps
E → E/m, is equivalent to determining all primitive idempotents of the ring E/ 0, in a sense that
is not hard to make precise. Likewise, by part (ii) of Theorem 1.8, determining all localizations Em
as well as the maps E → Em is equivalent to determining all primitive idempotents of E itself.
We briefly discuss
√ the literature on these two problems. An algorithm for finding the primitive
idempotents of E/ 0 was proposed in section V of [6], but it does not run in polynomial time ([6],
section VI); a promised sequel to [6] never appeared, and no details are available on the method
for dealing with the issue that was suggested on p. 86 in section 4 of [9]. However, in section
√ 7.2
of [3] one does find a polynomial-time algorithm for finding the primitive idempotents of E/ 0. It
depends on a primitive element, as does our own method.
√
To find the primitive idempotents of E, it suffices to lift those of E/ 0. In section IV of [6],
a method for doing this is proposed, based on Hensel’s lemma. A proof that this method runs in
polynomial time can be found in section 3.2 of [1]; alternatively, one can√apply Theorem 1.5. Our
own procedure
√ is much simpler: from the primitive idempotents of E/ 0 and the isomorphism
∼
→ E/ 0 one immediately obtains the primitive idempotents of Esep , which coincide with
Esep −
those of E.
Altogether, we obtain a new proof of the following theorem.
Theorem 1.9. There is a deterministic polynomial-time algorithm that, given a Q-algebra, computes
its primitive idempotents.
For the proof and the algorithms, see section 7. All idempotents are obtained as sums of subsets
of the set of primitive idempotents, but there may be too many to list in polynomial time.
In terms of prime ideals, Theorem 1.9 reads as follows.
Theorem 1.10. There are deterministic polynomial-time algorithms that, given a Q-algebra E,
compute all m ∈ Spec(E), the Q-algebras Em and E/m for all m ∈ Spec(E), as well as the natural
maps
Y
Y
E/m,
Em , Esep →
E → Em , Em → E/m, E → E/m, E →
m∈Spec(E)

and the inverses of the latter two maps.
For the proof and the algorithms, see section 7.

m∈Spec(E)

ALGORITHMS FOR COMMUTATIVE ALGEBRAS OVER THE RATIONAL NUMBERS

5

Discrete logarithms. Theorem 1.10 contributes a useful ingredient in an algorithm for finding
roots of unity in orders that the authors recently developed; see [14, 12, 13]. We also proved that,
given a Q-algebra E, one can find, in polynomial time, generators for the group µ(E) of roots of
unity in E, and we presented a solution to the discrete logarithm problem in µ(E); see [14]. The
following result states that, in fact, the discrete logarithm problem in the full multiplicative group
E ∗ of E admits an efficient solution.
Theorem 1.11. (i) There is a deterministic polynomial-time algorithm that, given a Q-algebra E
and a finite system S of elements of E, decides whether all elements of S belong to E ∗ , and if
so determines a finite set of generators for the kernel of the group homomorphism
Y
ZS → E ∗ ,
(ms )s∈S 7→
sms .
s∈S

(ii) There is a deterministic polynomial-time algorithm that, given a Q-algebra E, a finite system S
∗
of elements of E ∗ and t ∈ E ∗ , decides whether
Q t belong to the subgroup hSi of E generated by
S, and if so produces (ms )s∈S ∈ ZS with t = s∈S sms .

The case of Theorem 1.11 in which E is assumed to be a field is already quite complicated; it was
done by G. Ge [5]. We prove Theorem 1.11 in section 8 by a reduction to the case E is a field as
dealt with by Ge.
In [1] one finds a result that is in substance equivalent to Theorem 1.11, with a proof that proceeds
along the same lines.
Acknowledgment: We thank the referee for helpful comments, and especially for pointing out that
a number of results were known earlier, in [3, 6, 9, 1].
2. Separable Q-algebras
Let E be a Q-algebra and α ∈ E. Then the map Q[X] → E, f 7→ f (α) is a ring homomorphism,
and it is not injective because dimQ (E) < ∞. Hence the kernel of the map is equal to (g) = g · Q[X]
for a unique monic polynomial g ∈ Q[X], which is called the minimal polynomial of α (over Q); note
that the image Q[α] of the map is then isomorphic to Q[X]/(g) as a Q-algebra. Let Esep ⊂ E be as
defined in the introduction.
Lemma 2.1. Let E be a Q-algebra and α ∈ E. Let g ∈ Q[X] be the minimal polynomial of α. Then
the following are equivalent:
(i) α ∈ Esep ,
(ii) (g, g ′ ) = 1,
(iii) g is squarefree in Q[X].

Proof. That (ii) implies (i) follows from the definition of Esep , since g(α) = 0. For (i) ⇒ (ii), suppose
α ∈ Esep . Let f ∈ Q[X] be such that (f, f ′ ) = 1 and f (α) = 0. Then g divides f , so f, f ′ ∈ (g, g ′ )
and therefore (g, g ′ ) = 1. That (ii) and (iii) are equivalent is a direct consequence of the fact that Q
has characteristic zero.

Lemma 2.2. If E is a Q-algebra, then Esep is a sub-Q-algebra of E.
Proof. Let α, β ∈ Esep with minimal polynomials g, h, respectively. Then one has g = g1 g2 · · · gt ,
where g1 , g2 , . . . , gt ∈ Q[X] are distinct monic irreducible polynomials, by Lemma 2.1. By the
Chinese remainder theorem one now has
t
t
Y
Y
Ki ,
Q[X]/(gi ) =
Q[α] ∼
= Q[X]/(g) ∼
=
i=1

i=1

6

H. W. LENSTRA, JR. AND A. SILVERBERG

where each Ki is a field. The subalgebra Q[α, β] ⊂ E generated by α and β is the image of the map
Q[α][Y ] → E, f 7→ f (β), of which the kernel contains h(Y ). One has
Q[α][Y ]/(h(Y )) ∼
=

t
Y

Ki [Y ]/(h(Y )),

i=1

where each Ki [Y ]/(h(Y )) is a finite product of fields because (h, h′ ) = 1. Hence Q[α][Y ]/(h(Y )) is a
product of finitely many fields Lj . Each z ∈ Q[α][Y ]/(h(Y )), with components zj ∈ Lj , is a zero of a
separable polynomial in Q[X], namely the least common multiple of the minimal polynomials over Q
of the elements zj . Since there is a surjective Q-algebra homomorphism Q[α][Y ]/(h(Y )) → Q[α, β],
it follows that each element of Q[α, β] is separable over Q. In particular, one has α ± β, αβ ∈ Esep .
Since one also has Q · 1 ⊂ Esep (since 1 is separable), it follows that Esep is a sub-Q-algebra of E. 
Lemma 2.3. Suppose E is a Q-algebra, α ∈√E, and f ∈ Q[X] is a separable polynomial for which
f (α) is nilpotent. Then there exists y ∈ α + 0 such that f (y) = 0.

Proof. Since f ∈ Q[X] is separable, one has Q[X] · f m + Q[X] · f ′ = Q[X] for all m ∈ Z>0 . Let now
z ∈ E be such that f (z) is nilpotent. Then it follows that f ′ (z) ∈ E ∗ , so we can define
z ∗ = z − f (z)/f ′ (z) ∈ E.
√
√
Note that z ∗ ∈ z + 0 because f (z) ∈ 0. One has

f (X + Y ) ∈ f (X) + f ′ (X)Y + Q[X, Y ] · Y 2 ,

and substituting X = z, Y = −f (z)/f ′ (z) one finds f (z ∗ ) ∈ E · f (z)2 . Hence f (z ∗ ) is nilpotent as
well, so that one also has f ′ (z ∗ ) ∈ E ∗ . It follows, starting from z = α0 = α and iterating the map
z 7→ z ∗ , that there is a well-defined sequence α0 , α1 , α2 , . . . defined by αi+1 = α∗i . By the above
√
i
results, all αi belong to α + 0, and f (αi ) ∈ E · f (α)2 . Thus, for i large enough one has f (αi ) = 0,
and one can take y = αi .

Proof of Theorem 1.1. Since
√ E is commutative, the sum of any two nilpotent elements of E is
nilpotent, and it follows that 0 is an ideal of E; in particular, it is a Q-vector space. Lemma 2.2
shows that Esep is a sub-Q-algebra of E. We next prove that the map
√
Esep ⊕ 0 → E,
(u, v) 7→ u + v

is surjective. Let α ∈ E have minimal polynomial g, and let f be the product of the distinct monic
irreducible factors of g. Then f is separable√and f (α) is nilpotent, so Lemma 2.3 shows that we
can write α = u + v with f (u) = 0 and
√ v ∈ 0. Then u ∈ Esep√, and surjectivity follows. To prove
injectivity, it suffices to show Esep ∩ 0 = {0}. Let α ∈ Esep ∩ 0. Then the minimal polynomial g
of α divides both some separable polynomial and some polynomial of the form X m with m ∈ Z>0 ,
so it divides X, and therefore α = 0.

3. The structure of Q-algebras
In this section we prove Theorem 1.8. We begin with a lemma.

Lemma 3.1. If the assertions of Theorem 1.8 are valid for two Q-algebras E0 and E1 , then they
are valid for the product algebra E = E0 × E1 .
Proof. Since this proof is straightforward, we only indicate the main points. The two projection maps
E → Ei (i = 0, 1) induce maps Spec(Ei ) → Spec(E), and these allow us to identify Spec(E) with
the disjoint union of Spec(E0 ) and Spec(E1 ). If m = m0 × E1 ∈ Spec(E) comes from m0 ∈ Spec(E0 ),
∼
∼
→ (E0 )m0 . Also, one has Esep = (E0 )sep × (E1 )sep , and
then one has E/m −
→ E0 /m0 and Em −
likewise for the nilradicals. These facts readily imply the lemma.


ALGORITHMS FOR COMMUTATIVE ALGEBRAS OVER THE RATIONAL NUMBERS

7

Proof of Theorem 1.8. We use induction on dimQ (E). If dimQ (E) = 0 then Spec(E) = ∅ and
all assertions are clear. Next suppose dimQ (E) > 0.
Suppose first that each α ∈ Esep has a minimal polynomial that is irreducible;√then each Q[α] is
a field, so
0√= E it follows
sep ⊕
√ each non-zero
√ α ∈ Esep has an inverse, so Esep is a field. By E√
∼
that E/√ 0 = Esep , so 0 is a maximal ideal.
√
√ Each p ∈ Spec(E) contains 0, but √0 is maximal,
so p = 0. This proves that Spec(E) = { 0}. Hence E is local with maximal ideal 0, and 0 is
nilpotent because it is a finitely generated ideal consisting of nilpotents. All statements of Theorem
1.8 follow.
Next assume α ∈ Esep is such that its minimal polynomial g is reducible: g = g0 · g1 with
gi ∈ Q[X] r Q. Lemma 2.1 implies that g0 and g1 are coprime, so we have
Q[α] ∼
= Q[X]/(g) ∼
= Q[X]/(g0 ) × Q[X]/(g1 )
as Q-algebras, where both rings Q[X]/(gi ) are non-zero. Let e ∈ Q[α] ⊂ E map to (1, 0) ∈
Q[X]/(g0) × Q[X]/(g1). Then one has e2 = e and e ∈
/ {0, 1}. The ideals I = Ee and J = E(1 − e)
satisfy I + J = E (because 1 ∈ I + J) and therefore I ∩ J = IJ = Ee(1 − e) = {0}. The Chinese
remainder theorem now shows E = E/(I ∩ J) ∼
= E/I × E/J = E0 × E1 (say) as Q-algebras, where
dimQ (Ei ) < dimQ (E) because I and J are non-zero. The induction hypothesis shows that Theorem
1.8 is valid for each Ei , so by Lemma 3.1 it is also valid for E.

4. Derivations and idempotents
In this section we prove Theorems 1.3, 1.4, and 1.5.
Proof of Theorem 1.3. The map δ is well-defined since if g divides h1 − h2 then h′1 − h′2 ∈ (g, g ′ ).
It is Q-linear, and it is surjective because the map Q[X] → Q[X], h → h′ is surjective.
We prove Esep ⊂ ker(δ). Let α ∈ Esep , and let f ∈ Q[X] be a separable polynomial with f (α) = 0.
Then f ′ (α)δ(α) = δ(f (α)) = δ(0) = 0 and f (α)δ(α) = 0 · δ(α) = 0, and since (f, f ′ ) = 1 one obtains
δ(α) = 0.
To prove Esep = ker(δ) it will now suffice to prove that Esep and ker(δ) have the same dimension.
The prime ideals m of E are in bijective correspondence with the monic irreducible
factors h of g
∼ Q
→ m∈Spec(E) E/m from
in Q[X], by m = (h)/(g), and E/m ∼
= Q[X]/(h). The isomorphism Esep −
Q
P
Theorem 1.8(iv) now implies dimQ (Esep ) = h deg(h) = deg(ĝ), with ĝ = h h and h ranging over
the monic irreducible factors of g in Q[X]. If h occurs exactly m times in g, then it occurs exactly
m − 1 times in g ′ , so (g, g ′ ) = (g/ĝ). Hence
dimQ (ker(δ)) = deg(g) − deg(g/ĝ) = deg(ĝ) = dimQ (Esep )
as required. This proves Theorem 1.3.



Proof of Theorem 1.4. Theorem 1.4 is easy to check if n = 0, in which case f = 0, and also if
m = 0, n 6= 0, in which case f = 1. Assume now m > 0, n > 0. We first prove existence. Define
m−1
X m + n − 1
X i (1 − X)m+n−1−i ,
f0 =
i
i=0
f=

m+n−1
X 
i=m


m+n−1
X i (1 − X)m+n−1−i .
i

By the binomial theorem we have
f0 + f = (X + (1 − X))m+n−1 = 1.

Since one has also f ∈ R[X] · X m and 1 − f = f0 ∈ R[X] · (1 − X)n , this proves existence, and it
also proves the first formula for f .

8

H. W. LENSTRA, JR. AND A. SILVERBERG

To prove uniqueness, suppose that h ∈ R[X] also satisfies
deg(h) < m + n,

h ∈ R[X] · X m ,

h ∈ 1 + R[X] · (1 − X)n .

Then we have h − f ∈ R[X] · X m and h − f ∈ R[X] · (1 − X)n , so
h − f = (h − f ) · 1 = (h − f )f0 + (h − f )f

∈ R[X] · X m · R[X] · (1 − X)n + R[X] · (1 − X)n · R[X] · X m

= R[X] · X m · (1 − X)n ,

the last equality because X m and (1 − X)n are central in R[X]. Since deg(h − f ) < m + n, it follows
that h = f . This proves uniqueness.
It remains to prove the second expression for f . First assume that
R = Q. The derivative f ′ of
Pm+n−1
m−1
n−1
f is divisible both by X
and by (1 − X)
, so if we write f = i=m ci X i with ci ∈ Q, then
one has
m+n−1
X
ici X i−1 = qX m−1 (1 − X)n−1 ,
i=m

where q ∈ Q[X] is a certain
polynomial. Comparing degrees one finds q ∈ Q. The first formula for


f shows cm = m+n−1
, so comparing the terms of degree m − 1 one finds q = mcm = m m+n−1
.
m
m
Comparing the terms of degree i − 1 now yields





m+n−1
n−1
i−m
i−m n − 1
= (−1)
m
ici = q(−1)
i−m
m
i−m
from which it follows that
ci = (−1)i−m



m+n−1
i




i−1
.
i−m

This proves the last equality of Theorem 1.4 in Q[X]. It is then also valid in Z[X], and since there
is a unique ring homomorphism Z → R it is valid in R[X] as well.
The remainder of f 2 upon division by X m (1 − X)n has the same properties as f , so by uniqueness
is equal to f . Hence f 2 ≡ f mod R[X] · X m (1 − X)n .

Proof of Theorem 1.5. We first prove that y = f (α) has the properties stated. If n = 0 then y =
f (α) = 0, which does satisfy y 2 = y, and y − α = −α is nilpotent because αm = 0. If m = 0, n 6= 0
then y = f (α) = 1, which does satisfy y 2 = y, and y − α = 1 − α is nilpotent because (1 − α)n = 0.
For m 6= 0, n 6= 0, one has y − α = f (α) − α ∈ Rα and y − α = f (α) − 1 + (1 − α) ∈ R(1 − α), so
y − α = (y − α)((1 − α) + α) ∈ Rα(1 − α) + R(1 − α)α = Rα(1 − α).
From αm (1 − α)n = 0 and the commutativity of R it now follows that y − α is nilpotent. With f0
as in the proof of Theorem 1.4, we have
f (1 − f ) = f f0 ∈ R[X] · X m · (1 − X)n ,
so y − y 2 = f (α)(1 − f (α)) ∈ R · αm · (1 − α)n = {0}.
To prove uniqueness, suppose that z ∈ R is such that z − α is nilpotent and z 2 = z. Since R is
commutative, we have
(z − y)3 = z 3 − 3z 2 y + 3zy 2 − y 3 = z − 3zy + 3zy − y = z − y
t

and by induction it follows that z − y = (z − y)3 for all t ∈ Z≥0 . But since R is commutative, the
t
element z − y = (z − α) − (y − α) is nilpotent, and choosing t such that (z − y)3 = 0 one finds
z = y.


ALGORITHMS FOR COMMUTATIVE ALGEBRAS OVER THE RATIONAL NUMBERS

9

5. Splitting off the nilradical
In this section we prove Theorem 1.2. We begin with an algorithm that also determines minimal
polynomials.
Algorithm 5.1. Given a Q-algebra E and α ∈ √
E, this algorithm computes the minimal polynomial
of α, as well as the unique pair (u, v) ∈ Esep ⊕ 0 with α = u + v.
P
i
(i) Compute 1, α, α2 , . . . until the smallest k ∈ Z≥0 is found for which αk ∈
i<k Qα ; if
P
P
i
αk = i<k ci αi with ci ∈ Q, output g = Y k − i<k ci Y ∈ Q[Y ] as the minimal polynomial
of α.
(ii) Use the Euclidean algorithm to compute (g, g ′ ), and compute ĝ = g/(g, g ′).
(iii) Use linear algebra to compute the unique q ∈ Q[Y ] satisfying
deg(q) < deg((g, g ′ )),

q ′ ĝ + qĝ ′ ≡ 1 mod (g, g ′ ),

and output v = q(α)ĝ(α), u = α − v.
Proposition 5.2. Algorithm 5.1 is correct and runs in polynomial time.
Proof. Step (i) is clearly correct, and it runs in polynomial time because k = dimQ (Q[α]) ≤ dimQ (E).
Step (ii) runs in polynomial time by Chapter 6 of [4]. Note that ĝ is, as in the proof of Theorem 1.3,
the product of the distinct monic irreducible factors of g in Q[Y ]. We prove the correctness of step
∼
(iii). Applying
we see that there exists a unique
p Theorem 1.1 to the Q-algebra Q[α] = Q[Y ]/(g), p
element v ∈ 0Q[α] with u = α − v ∈ Q[α]sep . Since we have 0Q[α] = Q[α]ĝ(α), and since by
Theorem 1.3 we have
Q[α]sep = {h(α) : h ∈ Q[Y ], h′ ∈ (g, g ′ )},
it is equivalent to say that there is a unique element v = q(α)ĝ(α) with
1 − q ′ ĝ − qĝ ′ ≡ 0 mod (g, g ′ );

here q ∈ Q[Y ] is uniquely determined modulo g/ĝ = (g, g ′ ). This implies the unique existence of q
as in step (iii) and the correctness of the output.

Example 5.3. Let E = Q[X]/(X 2 + 1)2 . For all h ∈ Q[X], let h̃ denote the image of h in E. We
apply Algorithm 5.1 with α = X̃. The minimal polynomial of X̃ is g = (Y 2 + 1)2 , and we have
ĝ = Y 2 + 1. By Theorem 1.3,
Esep = ker(δ) = {h̃ : deg(h) ≤ 3 and h′ ∈ Q · (X 2 + 1)} = Q + Q · (X̃ 3 + 3X̃).
Write q = a + bY , substitute into
q ′ ĝ + qĝ ′ ≡ 1 mod (Y 2 + 1),

and solve for a, b ∈ Q to obtain q = − 21 Y and

√
1
v = q(X̃)ĝ(X̃) = − X̃(X̃ 2 + 1) ∈ 0E .
2

Then u = X̃ − v = 12 (X̃ 3 + 3X̃) ∈ Esep .
Example 5.4. Let E = Q[X]/(X 2 + 1)3 and let h̃ denote the image in E of h ∈ Q[X]. Applying
Algorithm 5.1 with α = X̃, we have g = (Y 2 + 1)3 and ĝ = Y 2 + 1. Then
Esep = ker(δ) = Q · 1 + Q · (3X̃ 5 + 10X̃ 3 + 15X̃).
Solving for the 4 coefficients of q in
q ′ ĝ + qĝ ′ ≡ 1 mod (Y 4 + 2Y 2 + 1)

10

H. W. LENSTRA, JR. AND A. SILVERBERG

and letting u = X̃ − q(X̃)(X̃ 2 + 1), we compute that q = − 81 (3Y 3 + 7Y ) and

1
1
u = X̃ + (3X̃ 2 + 7)X̃(X̃ 2 + 1) = (3X̃ 5 + 10X̃ 3 + 15X̃) ∈ Esep .
8
8
Algorithm
5.5. Given a Q-algebra E, this algorithm computes
√
√ ∼ a Q-basis for Esep and a Q-basis
for 0, as well as the matrices describing the map Esep ⊕ 0 −
→ E, (u, v) 7→ u + v and its inverse.
(i) Applying Algorithm 5.1 to each of the basis
elements
e
1 , e2 , . . . , en of E, determine elements
√
u1 , u2 , . . . , un ∈ Esep and v1 , v2 , . . . , vn ∈ 0 such that ei = ui + vi for 1 ≤ i ≤ n.
(ii) Using linear algebra, determine a maximal subset I ⊂ {1, 2, . . . , n} for which (ui )i∈I is
linearly independent over Q, and express each uj (1 ≤ j ≤ n) as a Q-linear combination of
(ui )i∈I . Output (ui )i∈I as a Q-basis for Esep .
(iii) Using linear algebra, determine a maximal subset J ⊂ {1, 2, . . . , n} for which (vi )i∈J is
linearly independent over Q, and express√each vj (1 ≤ j ≤ n) as a Q-linear combination of
(vi )i∈J . Output (vi )i∈J as a Q-basis for√ 0.
(iv) The matrix describing the map Esep ⊕ 0 → E consists of the coordinates of the vectors
ui (i ∈ I) and vi (i ∈ J) when expressed on the basis e1√
, e2 , . . . , en , as computed in step
(i). The matrix describing the inverse map E → Esep ⊕ 0 consists of the coordinates of
u1 , u2 , . . . , un on (ui )i∈I as computed in step (ii) and of the coordinates of v1 , v2 , . . . , vn on
(vi )i∈J as computed in step (iii).
Proof of Theorem 1.2. It is a routine exercise to show that Algorithm 5.5 has the properties
claimed in the statement of Theorem 1.2.

deg(g)−1

deg((g,g′ ))−1

for Q[X]/(g) and {X i }i=0
Remark 5.6. If 0 6= g ∈ Q[X], and one uses the bases {X i }i=0
′
for Q[X]/(g, g ), then one will find that Esep has a basis consisting of 1 and one polynomial of degree
j for each j ∈ Z with deg((g, g ′ )) < j < deg(g).
6. Primitive elements
In this section we prove Theorems 1.6 and 1.7(i).
Suppose E is a Q-algebra. If α ∈ E, then α is integral over Z if there is exists a monic
polynomial
Q
f ∈ Z[X] such that f (α) = 0. If f ∈ Z[X] is monic and separable, then f = i (X − ai ) with
ai ∈ Z ⊂ C, where Z denotes the set of algebraic integers in C, and we define the discriminant of f
to be
Y
(ai − aj )2 ∈ Z r {0}.
∆(f ) =
i<j

Proposition 6.1. Suppose E is a Q-algebra, suppose α, β ∈ E are separable over Q and integral
over Z. Let f ∈ Z[X] denote the minimal polynomial of α and let d ∈ Z>0 be such that d2 ∤ ∆(f ).
Then Q[α, β] = Q[α + dβ].
Proof. Let Φ denote the set of ring homomorphisms from Q[α, β] to C. By Theorem 1.1 we have
Q[α, β] ⊂ Esep , so Q[α, β] = Q[α, β]sep is the product of finitely many number fields (Theorem
1.8(iv)). It follows from this that one has #Φ = dimQ (Q[α, β]).
We first show that if ϕ, ψ ∈ Φ and ϕ(α + dβ) = ψ(α + dβ), then ϕ = ψ. Suppose that ϕ, ψ ∈ Φ
and ϕ(α + dβ) = ψ(α + dβ). Then ϕ(α), ψ(α), ϕ(β), ψ(β) ∈ Z, so
Write f =

Q

i (X

ϕ(α) − ψ(α) = d(ψ(β) − ϕ(β)) ∈ dZ.

− ai ) with ai ∈ Z ⊂ C. Suppose ϕ(α) = ai and ψ(α) = aj . If i 6= j, then
∆(f ) ∈ Z(ϕ(α) − ψ(α))2 ⊂ Zd2 ,

so ∆(f )/d2 ∈ Z∩Q = Z, contradicting our assumption. Thus i = j, so ϕ(α) = ψ(α), so ϕ(β) = ψ(β),
so ϕ = ψ, proving the claim.

ALGORITHMS FOR COMMUTATIVE ALGEBRAS OVER THE RATIONAL NUMBERS

11

Let h denote the minimal polynomial of α + dβ. Then Q[α + dβ] ∼
= Q[X]/(h), the degree of h is
dimQ Q[α + dβ], and h(α + dβ) = 0, so h(ϕ(α + dβ)) = 0 for all ϕ ∈ Φ. Thus,
deg h ≥ #{z ∈ C : h(z) = 0} ≥ #{ϕ(α + dβ) : ϕ ∈ Φ} = #Φ

= dimQ Q[α, β] ≥ dimQ Q[α + dβ] = deg h,

so all are equal. It follows that Q[α, β] = Q[α + dβ].



It follows from Algorithm 6.3 below that finding a primitive element of E can be done in polynomial time.
Theorem 6.2. Suppose that E is a Q-algebra, and suppose Esep = Q[α1 , . . . , αt ] with each αi ∈ E
integral over Z. Let fi denote the minimal polynomial of αi , and for i ∈ {1, . . . , t − 1} let di be a
positive integer such that d2i ∤ ∆(fi ). Then
Esep = Q[α1 + d1 α2 + d1 d2 α3 + · · · + d1 d2 · · · dt−1 αt ].
Proof. Each fi is a monic separable polynomial in Z[X]. Applying Proposition 6.1 gives
Q[αt−1 , αt ] = Q[αt−1 + dt−1 αt ].
Proceeding inductively, we have
Esep = Q[α1 , . . . , αt−2 , αt−1 + dt−1 αt ] =
Q[α1 , . . . , αt−3 , αt−2 + dt−2 αt−1 + dt−2 dt−1 αt ] = · · ·
as required.

= Q[α1 + d1 α2 + d1 d2 α3 + · · · + d1 d2 · · · dt−1 αt ],


Theorem 6.2 yields the following deterministic polynomial-time algorithm that proves Theorem
1.6.
Algorithm 6.3. Given a Q-algebra E, this algorithm outputs α ∈ E such that Esep = Q[α].
(i) Applying Algorithms 5.5 and 5.1, find a Q-basis u1 , u2 , . . . , ut for Esep as well as the minimal
polynomial gi of each ui .
(ii) For i = 1, 2, . . . , t, find a non-zero integer ki for which ki gi ∈ Z[X], compute the minimal
deg(gi )
gi (X/ki ) of ki ui , as well as its discriminant ∆(fi ) and the least
polynomial fi = ki
positive integer di for which d2i ∤ ∆(fi ).
(iii) With αi = ki ui , output
α = α1 + d1 α2 + d1 d2 α3 + · · · + d1 d2 · · · dt−1 αt .
Proof of Theorem 1.6. The first assertion of Theorem 1.6 follows from Theorem 6.2; note that
each ∆(fi ) is non-zero, so that di exists. For the second assertion, we show that Algorithm 6.3 has
the required properties. Note that each fi is a monic polynomial in Z[X], so the elements xi = ki ui
(1 ≤ i ≤ t) form a Q-basis for Esep consisting of elements that are integral over Z. Thus the
correctness of the algorithm follows from Theorem 6.2. It follows from Corollary 11.19 of [4] that
the computation of ∆(fi ) can be done in polynomial time. We have di ≤ 21 log|∆(fi )| + o(1) for
|∆(fi )| → ∞, since
|∆(fi )| ≥ lcm(1, 2, . . . , di − 1)2 = exp(2di + o(1))
as di → ∞ (see Chapter XXII of [7]).

Lemma 6.4. Let E be a Q-algebra,
√and let α ∈ E be such
√ Esep
√ = Q[α]. Suppose that for
√ each
√
m ∈ Spec(E) there exists εm ∈ 0/m 0 with (E/m)εm = 0/m 0. Then there exists ε ∈ 0 with
E = Q[α + ε].

12

H. W. LENSTRA, JR. AND A. SILVERBERG

√
L
Proof. Since E/ 0 ∼
= m∈Spec(E) E/m as E-modules, we have
M√
M√
M
√
√
√ √ 2 √
0/ 0 = 0 ⊗E (E/ 0) ∼
0/m 0 =
( 0 ⊗E (E/m)) =
(E/m)εm
=
m

m

m

√
√ √ 2
√
√
L √
0/m 0. Since
for some εm ∈ 0/m 0. Pick ε̃ ∈ 0/ 0 mapping to (εm )m∈Spec(E) ∈
m
√
√
L √
Q
(εm )m∈Spec(E) generates m 0/m 0 as a module over m E/m ∼
= E/ 0, it follows that ε̃ generates
√ √ 2
√
√
0/ 0 as a module over E/ 0. We have E = Esep ⊕ 0 and Esep = Q[α] for some α ∈ E. Choose
√
√ 2
√
ε ∈ 0 mapping to ε̃, so E · ε + 0 = 0. Let f be the minimal polynomial of α. Then f
is separable. Since f (α) = 0 we have f (α + ε) ≡ 0 mod (ε), so there exists n ∈ Z>0 such that
f (α + ε)n = 0. Since f is separable, we have f ′ (α) ∈ E ∗ and f ′ (α + ε) ∈ E ∗ . Also,
√ 2
f (α + ε) ≡ f (α) + εf ′ (α) mod 0 ,
√ 2
√
so f (α + ε) ∈ E ∗ · ε + 0 . Thus, F = Q[α + ε] is a subring of E mapping onto E/ 0 = Q[α] where
√
√ √ 2
√
√
√
√
α = α + 0 = α + ε + 0, and 0F = F ∩ 0 maps onto 0/ 0 . It follows that E = F + 0 and
√
√
√
2
0 = 0F E + 0 .
Copying the proof of Lemma 7.4 in Chapter II of [8], we have
√
√ 2 √
√ 3 √
√ 3
√
√ √
√
0 = 0F E + 0 = 0F E + 0F 0 + 0 = 0F E + 0 = . . . = 0F E
√
since 0 is nilpotent. Now
√
√
√
√
√ 2
E = F + 0 = F + 0F E = F + 0F (F + 0F E) = F + 0F E = · · · = F = Q[α + ε],
as desired.



Proof of Theorem 1.7(i). We first show (a) ⇒ (d). If E = Q[α], then E ∼
= Q[X]/(g) for some
g ∈ Q[X], and since Q[X] is a principal ideal domain, each ideal of E is principal.
The direction (d) ⇒ (c) is obvious.
√
√
0
is
a
principal
E-ideal,
then
the
E/m-vector
space
0 ⊗E E/m =
We
now
show
(c)
⇒
(b).
If
√
√
0/m 0 is generated by a single element, so it has dimension at most√1. √
Finally, we show (b) ⇒ (a). Let εm generate the E/m-vector space 0/m 0, let α be a primitive
element for Esep (Theorem 1.6), and apply Lemma 6.4.

Example 6.5. We give an example of a Q-algebra E that does not have a primitive element. Let
E = Q[X, Y ]/(X 2 , XY, Y 2 ). Then E = Q · 1√⊕ Q · x ⊕ Q · y where x and y are the images in E of√X
and Y , respectively. Then Esep = Q · 1 and 0 = Q · x ⊕ Q · y. The unique maximal ideal is m = 0.
√
√
√ √ 2
√
√
√
√ 2
We have 0 = 0. Thus, 0/m 0 = 0/ 0 = 0 and dimE/m ( 0/m 0) = 2. If z ∈ E, then
z = a + bx + cy for some a, b, c ∈ Q. Then (z − a)2 = 0, so dimQ Q[z] ≤ 2 < 3 = dimQ E.
7. Decomposing Q-algebras
In this section we give the algorithms for Theorems 1.10, 1.9, and 1.7(ii). The next result (along
with Theorems 1.1 and 1.2) shows that to compute Spec(E), it suffices to compute Spec(Esep ).
Lemma 7.1. If E is a Q-algebra, then the map
is bijective.

i∗ : Spec(E) → Spec(Esep ),

m 7→ m ∩ Esep

√
Proof. Let i : Esep → E and√π : E → E/ 0 be the inclusion and projection maps, respectively. The
√
induced map π ∗ : Spec(E/ 0) → √
Spec(E) is bijective, since every prime ideal
√ of E contains 0.
The composition π ◦ i : Esep → E/ 0 is an isomorphism, since E = Esep ⊕ 0 as in Theorem 1.1.
Thus i∗ ◦ π ∗ is bijective. It follows that i∗ is bijective.


ALGORITHMS FOR COMMUTATIVE ALGEBRAS OVER THE RATIONAL NUMBERS

13

Algorithm 7.2. Given a Q-algebra E, the algorithm finds all m ∈ Spec(E), the fields E/m, the
Q-algebras Em , the primitive idempotents of E, the natural maps
Y
Y
Em ,
E/m, E →
E → E/m, E → Em , Em → E/m, Esep →
m∈Spec(E)

m∈Spec(E)

and the
(i)
(ii)
(iii)
(iv)
(v)

inverses of the latter two maps.
Apply Algorithm 6.3 to produce α ∈ E such
√ that Esep = Q[α].
Apply Algorithm 5.5 to obtain a basis for 0.
Apply Algorithm 5.1 to compute the minimal polynomial f ∈ Q[Y ] of α.
Use the LLL algorithm [10] to factor f into monic irreducible factors in Q[Y ].
deg(f /g)−1
, along with the
For each monic irreducible factor g of f in Q[Y ], output {αi g(α)}i=0
basis obtained in step (ii), as a basis for a prime ideal m ∈ Spec(E), with the elements
expressed on the given basis for E.
deg(g)−1
as a basis for E/m,
(vi) For each m ∈ Spec(E) obtained in step (v), output {αi mod m}i=0
and use linear algebra to compute
a
matrix
describing
the
map
E
→
E/m.
Then compute
Q
the composition Esep → E → m∈Spec(E) E/m and invert the matrix for this map to
Q
produce the inverse map m∈Spec(E) E/m → Esep . For each m ∈ Spec(E), compute the
image em ∈ Esep under the latter map of the element that has 1 in the m-th coordinate
and 0 everywhere else. Output {em }m∈Spec(E) as the set of primitive idempotents of E, and
output em E as the localization Em . The map E → Em = em E is multiplication by em , and
this gives the map
Y
Y
em E.
Em =
E→
m∈Spec(E)

Its inverse is (ym )m∈Spec(E) 7→

P

m

m∈Spec(E)

ym . The map Em → E/m is em E ⊂ E → E/m.

Proof of Theorems 1.10 and 1.9. The map g 7→ (g(α)) is a bijection from the set of monic
deg(f /g)−1
in step (v) is a basis for
irreducible factors of f in Q[Y ] to Spec(Esep ). The set {αi g(α)}i=0
√
the prime ideal g(α)Esep ∈ Spec(Esep ). This basis, along with a basis for 0, gives a basis for the
prime ideal
√
m = g(α)Esep + 0 = (i∗ )−1 (g(α)Esep )
of E, where i∗ is the bijection of Lemma 7.1. Step (v) produces all m ∈ Spec(E) by Lemma 7.1.
Since Y 2 − Y is a separable polynomial, the idempotents of E are the same as the idempotents of
Esep . That Em and em E are isomorphic as Q-algebras is seen as in the proof of Theorem 1.8 in
section 3 if one realizes that em E and E/(1 − em )E are isomorphic as Q-algebras. The correctness
of the algorithm now follows, and it runs in polynomial time since the constituent pieces do.

Proof of Theorem 1.7(ii). We next give the algorithm for Theorem 1.7(ii).
Algorithm 7.3. Given a Q-algebra E, the algorithm decides whether E has a primitive element,
and produces one if it does.
√
(i) Apply Algorithms 7.2 and 5.5 to compute Spec(E) and 0, respectively.
√
√
(ii) For each m ∈ Spec(E), use linear algebra to compute cm = dimQ ( 0/m 0) and dm =
dimQ (E/m).
(iii) If for some m ∈ Spec(E) we have cm > dm , terminate with “no”.
√
√
0/m 0.
(iv) For each m, if √
cm = 0 let εm = 0 and otherwise
let ε√
m be any non-zero element of
L √
(v) Compute ε ∈ 0 mapping to (εm )m ∈ m ( 0/m 0), by inverting the matrix giving the
natural isomorphism
M
√
√ √ 2 ∼
√
( 0/m 0),
→
0/ 0 −
m∈Spec(E)

14

H. W. LENSTRA, JR. AND A. SILVERBERG

using linear algebra.
(vi) Apply Algorithm 6.3 to produce α ∈ Esep such that Esep = Q[α]. Output α + ε, a primitive
element for E.
Note that

√
√
√
√
cm
dimQ ( 0/m 0)
.
=
dimE/m ( 0/m 0) =
dimQ (E/m)
dm
Hence (a) ⇔ (b) of Theorem 1.7(i) and the construction of ε in Lemma 6.4 prove that Algorithm
7.3 is correct. It clearly runs in polynomial time. This proves Theorem 1.7(ii).
8. Discrete logarithm algorithm in Q-algebras
In this section we prove Theorem 1.11.
√
Let E be a Q-algebra. We denote√the composition of the map E → Esep ⊕ 0 from Theorem 1.2
with the natural projection Esep ⊕ 0 → Esep by π : E → Esep ; in other words, π(α) is, for α ∈ E,
the unique element of Esep for which α − π(α) is Q
nilpotent. Equivalently, π may be described as
the composition of the ring homomorphism E → m∈Spec(E) E/m from Theorem 1.8(iii) with the
Q
inverse of the isomorphism Esep → m∈Spec(E) E/m from Theorem 1.8(iv). The map π is a ring
√
homomorphism that is the identity on Esep and that has kernel 0. Each of Theorem 1.2 and
Theorem 1.10 shows that there is a polynomial-time algorithm that, given E, produces the matrix
describing π.
Proposition 8.1. Let E be a Q-algebra and let π be as just defined. Then there is a group isomorphism of multiplicative groups
Y
√
(E/m)∗ , α →
7 (α/π(α), (α + m)m∈Spec(E) ),
E ∗ → (1 + 0) ×
m∈Spec(E)

and there is a group isomorphism
log : 1 +

√
√
0 → 0,

1 − v 7→ −

m−1
X

v i /i

i=1

√ m
from a multiplicative group to an additive group, where m ∈ Z≥0 is such that 0 = 0.
√
√
Pm
Proof. For each v ∈ 0, one has (1 − v)−1 = i=0 v i for m sufficiently large, so 1 + 0 ⊂ E ∗ ; it is
∗
a subgroup of E ∗ since it is the kernel of the group homomorphism E ∗ → Esep
induced by π. The
∗
∗
inclusion map Esep ⊂ E provides a splitting of the short exact sequence
√
∗
1 → 1 + 0 → E ∗ → Esep
→ 1,
√
∼
∗
, α 7→ (α/π(α), π(α)). The isomorphism
so one has E ∗ −
→ (1 + 0) × Esep
Y
∼
E/m
→
Esep −
m∈Spec(E)

from Theorem 1.8(iv) induces an isomorphism
∼

∗
−
→
Esep

Y

(E/m)∗

m∈Spec(E)

of multiplicative
groups. The first isomorphism in Proposition 8.1 follows.
√
Since 0 is a finitely generated ideal consisting of nilpotents, it is nilpotent itself, so m as in the
proposition exists. One now proves in a P
routine manner that the map log is a group isomorphism,
m−1
the inverse exp being given by exp(y) = i=0 y i /i!.


ALGORITHMS FOR COMMUTATIVE ALGEBRAS OVER THE RATIONAL NUMBERS

15

Proposition 8.2. There is a deterministic polynomial-time algorithm that, given a Q-algebra E
that is a field and a finite system S of elements of E ∗ , determines a Z-basis for the kernel of the
group homomorphism
Y
ZS → E ∗ ,
(ms )s∈S 7→
sms .
s∈S

Proof. See [5], both for the algorithm and the proof.



Algorithm 8.3. This algorithm takes as input a Q-algebra E and a finite system S of elements of
E. It decides whether one has S ⊂ E ∗ , and if so computes a finite set of generators for the kernel
of the group homomorphism
Y
ZS → E ∗ ,
(ms )s∈S 7→
sms .
s∈S

(i) Compute all m ∈ Spec(E) and all maps E → E/m (Theorem 1.10), and compute s + m ∈
E/m for all s ∈ S and m ∈ Spec(E). If at least one of the elements s + m is zero, answer
“no” (i.e., S 6⊂ E ∗ ) and terminate.
(ii) For each m ∈ Spec(E), determine (using the algorithm in Proposition 8.2) a Z-basis for the
kernel Hm of the group homomorphism
Y
ZS → (E/m)∗ ,
(ms )s∈S 7→
(s + m)ms .
s∈S

√

m

(iii) Find the smallest m ∈ Z>0 with 0 = 0, and for each s ∈ S, compute log(s/π(s)) ∈
using a matrix for π and the formula for log in Proposition 8.1.
(iv) Compute a basis for the kernel H of the group homomorphism
X
√
ZS → 0,
(ms )s∈S 7→
ms log(s/π(s)),

√
0,

s∈S

by applying the kernel algorithm in §14 of [11] to an integer multiple of the rational matrix
describing the map.
T
(v) Compute a basis B for H ∩ m∈Spec(E) Hm ⊂ ZS by applying the kernel algorithm in §14
of [11] to the group homomorphism
M
M
ZS , (h, (hm )m∈Spec(E) ) 7→ (h − hm )m∈Spec(E) .
Hm →
H⊕
m∈Spec(E)

m∈Spec(E)

(vi) Output the image of B under the projection from H ⊕

L

m∈Spec(E)

Hm to its H-component.

Algorithm 8.4. The algorithm takes a Q-algebra E, a finite system S of elements of E ∗ and
t ∈ E ∗ , and decides whether
to the subgroup hSi of E ∗ generated by S, and if so produces
Q t belong
ms
S
(ms )s∈S ∈ Z with t = s∈S s .
(i) Apply Algorithm 8.3 with T = {t} ∪ S in place of S to obtain a finite set of generators UT
for the kernel of the group homomorphism
Y
gT : Z{t} × ZS = ZT → E ∗ ,
(mt , (ms )s∈S ) 7→ tmt
sms .
s∈S

{t}

S

{t}

P
(ii) Map the elements u ∈ UT ⊂ Z ×Z to their Z -components u(t) ∈ Z. If u∈UT u(t)Z 6=
P
Z then t 6∈ hSi; if 1 =
n u(t) with (nu )u∈UT ∈ ZUT then t ∈ hSi and the ZS Q
Pu∈UT u
component (ms )s∈S of − u∈UT nu u ∈ ZT = Z{t} × ZS satisfies t = s∈S sms .

16

H. W. LENSTRA, JR. AND A. SILVERBERG

Proof of Theorem 1.11(i). We show that Algorithm 8.3 is correct and runs in polynomial time.
In step (i), one has S ⊂ E ∗ if and only if each s + m 6= 0, because in any commutative ring the unit
group is the
√ complement of the union of all prime ideals. As we saw in the proof of Proposition 8.1,
the ideal 0 is nilpotent. With m as in (iii), one has
√
√ 2
√ m−1 √ m
E ⊃ 0 ) 0 ) ··· ) 0
) 0 = (0),

so m ≤ dimQ (E). Thus, step (iii) runs in polynomial time. From theTisomorphism in Proposition
8.1 it follows that the kernel of ZS → E ∗ equals the intersection H ∩ m∈Spec(E) Hm considered in
step (v). It follows that the algorithm gives the correct output.

Proof of Theorem 1.11(ii). Algorithm 8.4 is correct and runs in polynomial time since
t ∈ hSi ⇐⇒ ∃x ∈ ZS such that (1, −x) ∈ ker(gT ) = hUT i

⇐⇒ 1 ∈ im(proj : hUT i ⊂ Z × ZS → Z)
X
⇐⇒ ∃(nu )u∈UT , ∃x ∈ ZS such that
nu u = (1, −x) ∈ Z{t} × ZS
u∈UT

where proj denotes projection onto the first component.



References
[1] L. Babai, R. Beals, J-y. Cai, G. Ivanyos, and E. M. Luks, Multiplicative equations over commuting matrices, in
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA, 1996), ACM,
New York, 1996, 498–507.
[2] D. Eisenbud, Commutative algebra with a view toward algebraic geometry, Graduate Texts in Mathematics 150,
Springer-Verlag, New York, 1995.
[3] K. Friedl and L. Rónyai, Polynomial time solutions of some problems of computational algebra, in Proceedings
of the seventeenth annual ACM symposium on Theory of computing, ACM, 1985, 153–162.
[4] J. von zur Gathen and J. Gerhard, Modern computer algebra. Third edition. Cambridge University Press, Cambridge, 2013.
[5] Guoqiang Ge, Algorithms related to multiplicative representations of algebraic numbers, PhD thesis, U.C. Berkeley, 1993.
[6] P. Gianni, V. Miller, and B. Trager, Decomposition of algebras, in Symbolic and algebraic computation (Rome,
1988), Lect. Notes in Comp. Sci. 358, Springer, Berlin, 1989, 300–308.
[7] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers. Fifth edition. The Clarendon Press,
Oxford University Press, New York, 1979.
[8] R. Hartshorne, Algebraic geometry. Graduate Texts in Mathematics No. 52, Springer-Verlag, New YorkHeidelberg, 1977.
[9] G. Ivanyos, L. Rónyai, and A. Szántó, Decomposition of algebras over Fq (X1 , . . . , Xm ), Appl. Algebra Engrg.
Comm. Comput. 5, 1994, 71–90.
[10] A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann.
261 (1982), 515–534.
[11] H. W. Lenstra, Jr., Lattices, in Algorithmic number theory:
lattices, number fields, curves and
cryptography, Math. Sci. Res. Inst. Publ. 44, Cambridge Univ. Press, Cambridge, 2008, 127–181,
http://library.msri.org/books/Book44/files/06hwl.pdf.
[12] H. W. Lenstra, Jr. and A. Silverberg, Revisiting the Gentry-Szydlo Algorithm, in Advances in Cryptology—
CRYPTO 2014, Lect. Notes in Comp. Sci. 8616, Springer, Berlin, 2014, 280–296.
[13] H. W. Lenstra, Jr. and A. Silverberg, Lattices with symmetry, Journal of Cryptology (2016),
http://doi.org/10.1007/s00145-016-9235-7 .
[14] H. W. Lenstra, Jr. and A. Silverberg, Roots of unity in orders, Foundations of Computational Mathematics
(2016), http://doi.org/10.1007/s10208-016-9304-1 .
Mathematisch Instituut, Universiteit Leiden, The Netherlands
E-mail address: hwl@math.leidenuniv.nl
Department of Mathematics, University of California, Irvine, CA 92697, USA
E-mail address: asilverb@math.uci.edu

