arXiv:1509.02612v4 [] 11 Mar 2016

ROOTS OF UNITY IN ORDERS
H. W. LENSTRA, JR. AND A. SILVERBERG
Communicated by John Cremona
Abstract. We give deterministic polynomial-time algorithms that, given an order, compute the
primitive idempotents and determine a set of generators for the group of roots of unity in the
order. Also, we show that the discrete logarithm problem in the group of roots of unity can be
solved in polynomial time. As an auxiliary result, we solve the discrete logarithm problem for
certain unit groups in finite rings. Our techniques, which are taken from commutative algebra,
may have further potential in the context of cryptology and computer algebra.

1. Introduction
An order is a commutative ring whose additive group is isomorphic to Zn for some non-negative
integer n. The present paper contains algorithms for computing the idempotents and the roots of
unity of a given order.
In algorithms, we specify an order A by listing a system of “structure constants” aijk ∈ Z with
i, j, k ∈ {1, 2, . . . , n}; these determine the multiplicationPin A in the sense that for some Z-basis
e1 , e2 , . . . , en of the additive group of A, one has ei ej = nk=1 aijk ek for all i, j. The elements of A
are then represented by their coordinates with respect to that basis.
An idempotent of a commutative ring R is an element e ∈ R with e2 = e, and we denote by id(R)
the set of idempotents. An idempotent e ∈ id(R) is called primitive if e 6= 0 and for all e′ ∈ id(R)
one has ee′ ∈ {0, e}; let prid(R) denote the set of primitive idempotents of R.
Orders A have only finitely many idempotents, but they may have more than can be listed
by a polynomial-time algorithm; however, if one knows prid(A), then one implicitly knows id(A),
since there
P is a bijection from the set of subsets of prid(A) to id(A) that sends W ⊂ prid(A) to
eW = e∈W e ∈ id(A). For prid(A) we have the following result.

Theorem 1.1. There is a deterministic polynomial-time algorithm (Algorithm 6.1) that, given an
order A, lists all primitive idempotents of A.

A root of unity in a commutative ring R is an element of finite order of the group R∗ of invertible
elements of R; we write µ(R) for the set of roots of unity in R, which is a subgroup of R∗ .
As with idempotents, orders A have only finitely many roots of unity, but possibly more than can
be listed by a polynomial-time algorithm, and to control µ(A) we shall use generators and relations.
If S is a finite system of generators for an abelian group G, then by a set of defining relations for
S we mean Q
a system of generators for the kernel of the surjective group homomorphism ZS → G,
(ms )s∈S 7→ s∈S sms .
2010 Mathematics Subject Classification. 16H15 (primary), 11R54, 13A99 (secondary).
Key words and phrases. orders; algorithms; roots of unity; idempotents.
This material is based on research sponsored by DARPA under agreement number FA8750-13-2-0054 and by the
Alfred P. Sloan Foundation. The U.S. Government is authorized to reproduce and distribute reprints for Governmental
purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of
the authors and should not be interpreted as necessarily representing the official policies or endorsements, either
expressed or implied, of DARPA or the U.S. Government.
1

2

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

Theorem 1.2. There is a deterministic polynomial-time algorithm (Algorithm 13.2) that, given an
order A, produces a set S of generators of µ(A), as well as a set of defining relations for S.
Theorem 1.2, which provides a key ingredient in an algorithm for lattices with symmetry that
was recently developed by the authors [6, 7], is our main result, and its proof occupies most of the
paper. It makes use of several techniques from commutative algebra that so far have found little
employment in an algorithmic context. A sketch appeared in Proposition 4.7 of [6].
We shall also obtain a solution to the discrete logarithm problem in µ(A) and all its subgroups,
and more generally in all subgroups of the group µ(A ⊗Z Q), which is still finite. Note that A ⊗Z Q
is a ring containing A as a subring, and that a Z-basis for A is a Q-basis for the additive group of
A ⊗Z Q. If one replaces µ(A) by µ(A ⊗Z Q) in Theorem 1.2, then it remains true, and in fact it
becomes much easier to prove (Proposition 3.5). Our solution to the discrete logarithm problem in
µ(A ⊗Z Q) and all of its subgroups, in particular in µ(A), reads as follows.
Theorem 1.3. There is a deterministic polynomial-time algorithm that, given an order A, a finite
system T of elements of µ(A ⊗Z Q), and an element ζ ∈ A ⊗Z Q, decides whetherQζ belongs to the
subgroup hT i ⊂ µ(A ⊗Z Q) generated by T , and if so finds (mt )t∈T ∈ ZT with ζ = t∈T tmt .

We shall prove Theorem 1.3 in section 7, as a consequence of the results on µ(A ⊗Z Q) in section 3
and a number of formal properties of “efficient presentations” of abelian groups that are developed
in section 7.
A far-reaching generalization of Theorem 1.3, in which µ(A ⊗Z Q) is replaced by the full unit
group (A ⊗Z Q)∗ , is proven in [8].
Of the many auxiliary results that we shall use, there are two that have independent interest.
The first concerns the discrete logarithm problem in certain unit groups of finite rings, and it reads
as follows.
Theorem 1.4. There is a deterministic polynomial-time algorithm that, given a finite commutative
ring R and a nilpotent ideal I ⊂ R, produces a set S of generators of the subgroup 1 + I ⊂ R∗ , as
well as a set of defining relations for S. Also, there is a deterministic polynomial-time algorithm
that, given R and I as before, as well as a finite system T of elements of 1 + I and an element
ζ ∈Q
R, decides whether ζ belongs to the subgroup hT i ⊂ 1 + I, and if so finds (mt )t∈T ∈ ZT with
ζ = t∈T tmt .

The proof of this theorem is given in section 11. It depends on the resemblance of 1 + I to the
additive group I, in which the discrete logarithm problem is easy.
The second result that we single out for special mention is of a purely theoretical nature. Let R
be a commutative ring. For the purposes of this paper, commutative rings have an identity element
1 (which is 0 if and only if the ring is the 0 ring). We call R connected if #id(R) = 2 or, equivalently,
if id(R) = {0, 1} and R 6= {0}. A polynomial f ∈ R[X] is called separable (over R) if f and its
formal derivative f ′ generate the unit ideal in R[X]. For example, f = X 2 − X is separable because
(f ′ )2 − 4f = 1.

Theorem 1.5. Let R be a connected commutative ring, and let f ∈ R[X] be separable. Then f 6= 0
and #{r ∈ R : f (r) = 0} ≤ deg(f ).

For the elementary proof, see section 8.
While, technically, one must admit that Theorem 1.5 plays only a modest role in the paper, it
does convey an important message, namely that zeroes of polynomials that are separable are easier
to control than zeroes of other polynomials. Thus, X 2 − X is separable over any R, while X m − 1
(for m ∈ Z>0 ) is separable if and only if m · 1 ∈ R∗ , a condition that for a non-zero order and m > 1
is never satisfied; accordingly, Theorem 1.1 is much easier to prove than Theorem 1.2.
We next provide an overview of the algorithms that underlie Theorems 1.1 and 1.2. In both cases,
one starts by reducing the problem, in a fairly routine manner, to the special case in which each

ROOTS OF UNITY IN ORDERS

3

element of A is a zero of some separable polynomial in Q[X]; for the rest of the introduction we
assume that the latter condition is satisfied. Then the Q-algebra E = A ⊗Z Q can be written as the
product of finitely many algebraic number fields E/m, with m ranging over the finite set Spec(E)
of prime ideals of E; hence prid(E) is in bijection with Spec(E). The image of A ⊂ E under the
map E → E/m may
Q be identified with the ring A/(m ∩ A), so that A becomes a subring of the
product ring B = m∈Spec(E) A/(m ∩ A); this is also an order, and it is “close” to A in the sense
that the abelian group B/A is finite. The ring B has many idempotents, in the sense that id(B)
equals all of id(E), and #prid(B) = #Spec(E). To determine which subsets W ⊂ prid(B) give rise
to idempotents that lie in A, we define a certain graph Γ(A) with vertex set Spec(E) such that the
connected components of Γ(A) correspond exactly to the primitive idempotents of A. This leads to
Theorem 1.1.
To prove Theorem 1.2, one likewise starts from B, generators for µ(B) being easily found by
standard algorithms from algebraic number theory. However, there is no standard way of computing
µ(A) = µ(B) ∩ A, which is the intersection of a multiplicative group and an additive group, and
we must proceed in an indirect way. For a prime number p, denote by µ(A)p the group of roots of
unity in A that are of p-power order, and likewise µ(B)p . Then µ(A) is generated by its subgroups
µ(A)p = µ(B)p ∩ A, with p ranging over the set of primes dividing #µ(B); all these p are “small”.
It will now suffice to fix p and determine generators for µ(A)p . To this end, we introduce the
intermediate order A ⊂ C ⊂ B defined by C = A[1/p] ∩ B. The finite abelian group B/C is of order
coprime to p, and it turns out that this makes it relatively easy to determine µ(C)p = µ(B)p ∩ C;
in fact, one of the results (Proposition 8.1(b)) leading up to Theorem 1.5 stated above shows that
this can be done by exploiting the graph Γ(C) that we encountered in the context of idempotents.
The passage to µ(A)p = µ(C)p ∩ A is of an entirely different nature, as C/A is of order a power of
p. It is here that we have to invoke Theorem 1.4 for certain finite rings R that are of p-power order.
It is important to realize that the only reason that an intersection such as µ(A) = µ(B)∩A is hard
to compute is that µ(B), though finite, may be large—testing each element of µ(B) for membership
in A will not lead to a polynomial-time algorithm. By contrast, the exponent of each group µ(B)p
is small (Lemma 3.3(iv)), so results stating that certain subgroups of µ(B)p are cyclic—of which
there are several in the paper—are valuable in obtaining a polynomial bound for the runtime of our
algorithm.
2. Definitions and examples
From now on, when we say commutative Q-algebra we will mean a commutative Q-algebra that
is finite-dimensional as a Q-vector space. See [1, 3] for background on commutative rings and linear
algebra.
Definition 2.1. If A is an order whose additive group is isomorphic to Zn , we call n the rank of
A.
If the number of idempotents in R is finite, then each idempotent is the sum of a unique subset
of prid(R), and one has #id(R) = 2#prid(R) .
Definition 2.2. A commutative ring R is called connected if #{x ∈ R : x2 = x} = 2.

Definition 2.3. If R is a commutative ring, let Spec(R) denote the set of prime ideals of R.
Although we do not use it, we point out that a commutative ring R is connected if and only if
R 6= 0 and R cannot be written as a product of 2 non-zero rings. The definition is motivated by
the fact that a commutative ring R is connected if and only if Spec(R) is connected. (A topological
space is connected if and only if it has exactly 2 open and closed subsets.)
Notation 2.4. If G is a group and p is a prime number, define
r

Gp = {g ∈ G : g p = 1 for some r ∈ Z≥0 }.

4

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

Definition 2.5. Suppose R is a commutative ring. A polynomial f ∈ R[X] is separable over R if
where if f =

R[X]f + R[X]f ′ = R[X],
P
t
i−1
i
′
.
i=1 iai X
i=0 ai X then f =

Pt

One can show that if f is a monic polynomial over a commutative ring R, then f is separable
over R if and only if its discriminant is a unit in R.
Definition 2.6. Suppose E is a commutative Q-algebra. If α ∈ E, then α is separable over Q if
there exists a separable polynomial f ∈ Q[X] such that f (α) = 0. Let Esep denote the set of y ∈ E
that are separable over Q. We say E is separable over Q if Esep = E.
We note that Esep is a commutative Q-algebra (see for example Theorem 1.1 of [8]).
Definition 2.7. Suppose R is a commutative ring. An element x ∈ R is called nilpotent if there
exists n ∈ Z>0 such that xn = 0. An ideal I of R is called nilpotent if there exists n ∈ Z>0 such
that I n = 0, where I n is the product of I with
√ itself
√ n times. The set of nilpotent elements of R is
an ideal, called the nilradical and denoted 0 or 0R .
Examples 2.8. The polynomial X 2 − X is separable over every ring. A linear polynomial aX + b
is separable over R if and only if the R-ideal generated by a and b is R. If m ∈ Z≥0 , then the
polynomial X m − 1 is separable over R if and only if m · 1 is a unit in R.
Example 2.9. Suppose f (X) ∈ Z[X] is a monic polynomial of degree n. Then the ring Z[X]/(f ) is
an order of rank n. We remark that the map e 7→ gcd(e, f ) is a bijection from the set of idempotents
of Z[X]/(f ) to {g ∈ Z[X] : g is monic, g|f, and R(g, f /g) = ±1}, where R(g, f /g) is the resultant
of g and f /g.
Example 2.10. If G is a finite group of order 2n with a fixed element u of order 2, then ZhGi =
Z[G]/(u + 1) is a connected order of rank n, and µ(ZhGi) = G (see Remark 16.3 of [7]).
Example 2.11. If n ∈ Z>0 and A = {(ai )ni=1 ∈ Zn : ai ≡ aj mod 2 for all i, j} with componentwise
addition and multiplication, then A is a connected order, µ(A) = {(±1, . . . , ±1)}, and #µ(A) = 2n .
For large n, computing a set of generators for µ(A) is feasible, even when listing all elements of µ(A)
is not.
Example 2.12. Suppose A = Z[ζp ], where p is a prime and ζp is a primitive p-th root of unity in
C. Then A has rank p − 1. If p > 2, then µ(A) = hζp i × h−1i.
3. Finite Q-algebras
The following two results are from commutative algebra. These results and basic algorithms for
commutative Q-algebras are given in [8].
Proposition 3.1. If E is a commutative Q-algebra, then the map
√ ∼
Esep ⊕ 0 −
→ E, (x, y) 7→ x + y
is an isomorphism of Q-vector spaces, and the natural map E →
morphism of Q-algebras
Y
∼
E/m.
→
Esep −

Q

m∈Spec(E)

E/m induces an iso-

m∈Spec(E)

In algorithms, we specify a commutative Q-algebra E by listing a system of structure constants
aijk ∈ Q that determines the multiplication in E with respect to some Q-basis, just as we did for
orders in the introduction.

ROOTS OF UNITY IN ORDERS

5

Algorithm 3.2. There is a deterministic polynomial-time algorithm
that given a commutative
Q√
√
∼
→ Esep ⊕ 0 that is
algebra E, computes a Q-basis for Esep ⊂ E, a Q-basis for 0, the map E −
the inverse to the first isomorphism from Proposition 3.1, all m ∈ Spec(E), the fields E/m, and the
natural maps E → E/m.
Lemma 3.3. If E is a commutative Q-algebra, then:
∼ L
(i) µ(E) = µ(Esep ) −
→ m∈Spec(E) µ(E/m);
(ii) µ(E) is finite;
(iii) each µ(E/m) is a finite cyclic group;
(iv) if µ(E) has an element of order pk with p a prime, then ϕ(pk ) ≤ dimQ (E), where ϕ is
Euler’s ϕ-function.
Proof. Part (i) holds by Proposition 3.1 and the fact that X r − 1 is separable over Q for all r ∈ Z>0 .
If µ(E) has an element of prime power order pk , then Q(ζpk ) ⊂ E/m for some m, where ζpk is a
primitive pk -th root of unity. Thus ϕ(pk ) ≤ [E/m : Q] ≤ dimQ (E). Since each E/m is a number
field, µ(E/m) is cyclic.

Algorithm 3.4. The algorithm takes as input a commutative Q-algebra E and produces a set of
generators S of µ(E) as well as a set R of defining relations for S.
(i) For each n ∈ Spec(E), use the algorithm in [4] to find all zeroes of X r − 1 over E/n, for
r = 1, 2, . . . , 2[E/n : Q]2 , let ζn ∈ (E/n)∗ be an element of maximal order among the zeroes
found, and let k(n) be its order.
(ii) For each n ∈ Spec(E), use linear algebra to compute the unique element ηn ∈ Esep
that
Q under the second isomorphism from Proposition 3.1 maps to (1, . . . , 1, ζn , 1, . . . , 1) ∈
m µ(E/m) (with ζn in the n-th position). Output S = {ηn ∈ µ(E) : n ∈ Spec(E)} and
R = {(0, . . . , 0, k(n), 0, . . . , 0) ∈ ZSpec(E) : n ∈ Spec(E)}.
Proposition 3.5. Algorithm 3.4 produces correct output and runs in polynomial time.
Proof. If the number field E/n contains a primitive r-th root of unity, then it contains the r-th
cyclotomic field, which has degree ϕ(r) over Q; hence ϕ(r) ≤ [E/n : Q] and r ≤ 2ϕ(r)2 ≤ 2[E/n : Q]2 .
Together with Lemma 3.3(i), this implies that the algorithm is correct. It runs in polynomial time
by [4].

Algorithm 3.6. The algorithm takes as input a commutative Q-algebra E, an element γ ∈ E, and
a set S = {ηn ∈ µ(E) : n ∈ Spec(E)} of generators for µ(E) as computed
Q by Algorithm 3.4. It tests
whether γ ∈ µ(E), and if so, finds (an )n∈Spec(E) ∈ ZSpec(E) with γ = n∈Spec(E) ηnan .
(i) Use linear algebra to test if γ ∈ Esep . If not, terminate with “no” (that is, γ 6∈ µ(E)).
(ii) Otherwise, for each n ∈ Spec(E) compute the image γn of γ in E/n, and let ζn (as in
Algorithm 3.4) be the image of ηn in E/n. Try a = 0, 1, 2, . . . , #µ(E/n) − 1 until γn = ζna ,
and let an = a. If for some n no an exists, terminate with “no”.
(iii) Otherwise, output (an )n∈Spec(E) .
That Algorithm 3.6 produces correct output and runs in polynomial time follows from Lemma
3.3, since µ(E/n) = hζn i.
4. Orders
From now on, suppose that A is an order. Let
E = AQ = A ⊗Z Q,

Asep = A ∩ Esep .

Since Esep /Asep ⊂ E/A = AQ /A is a torsion group, one has Esep = (Asep )Q .

6

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

Lemma 4.1. We have id(Esep ) = id(E), id(Asep ) = id(A), and µ(Asep ) = µ(A).
Proof. This holds because the polynomials X 2 − X and X r − 1 are separable over Q for all r ∈
Z>0 .

Algorithm 4.2. The algorithm takes as input an order A and it computes the Q-algebras E and
Esep ⊂ E, as well as the order Asep = A ∩ Esep , giving a Z-basis for Asep expressed both in the given
Z-basis of A and in the Q-basis for Esep .
(i) We use the given Z-basis for A as a √
Q-basis for E, with the same structure constants.
(ii) Let π1 : A → Esep and
√ π2 : A → 0 be the compositions of the inclusion A ⊂ E with
∼
0 from Algorithm 3.2 followed by the natural projections to Esep
the map
E
−
→
E
⊕
sep
√
and 0, respectively. Using Algorithm 3.2, compute a Q-basis for Esep and the rational
matrices describing π1 and π2 . Applying the kernel algorithm in §14 of [5] to an integer
multiple of the matrix for π2 , compute a Z-basis for Asep = ker(π2 ) expressed in the given
Z-basis for A. Applying π1 to this Z-basis, one obtains the same Z-basis expressed in the
Q-basis for Esep .
Algorithm 4.2 is clearly correct and polynomial time.
5. Graphs attached to rings
Lemma 5.1. Suppose thatTR is a commutative ring, S is a finite set ofQideals of R that are not
R itself, and suppose that a∈S a = {0}. Identify R with its image in a∈S R/a. Suppose that
Q
e = (ea )a∈S ∈ {0, 1}S ⊂ a∈S R/a. Then e ∈ R if and only if ea = eb in {0, 1} for all a, b ∈ S such
that a + b 6= R.
Proof. First suppose e ∈ R. Suppose a, b ∈ S and a + b 6= R. Choose e′a ∈ {0, 1} ⊂ R whose image
in R/a is ea = e + a, and choose e′b ∈ {0, 1} ⊂ R whose image in R/b is eb = e + b. Then e′a ≡ e
mod a and e′b ≡ e mod b, so e′a ≡ e ≡ e′b mod (a + b). Since a + b 6= R we have 1 6∈ a + b. Thus,
e′a = e′b in {0, 1}, as desired.
Conversely, suppose that ea = eb in {0, 1} for all a, b ∈ S with a+b 6= R. Let T = {a ∈ S : ea = 1}
and U = {b ∈ S : eb = 0}. Then S = T ⊔ U . Pick a ∈ T and b ∈ U . By our assumption, a + b = R.
Thus, there exist xa,b ∈ a and ya,b ∈ b suchQ
that 1 = xa,b + ya,b . It follows that ya,b ≡ 1 mod a and
ya,b ≡ 0 mod b. For all a ∈ Q
T , define za = b∈U ya,b ∈ R. Then za ≡ 1 mod a and za ≡ 0 modulo
each b ∈ U . Define e′ = 1 − a∈T (1 − za ) ∈ R. Then e′ ≡ 1 modulo each a ∈ T , and e′ ≡ 0 modulo
each b ∈ U . Thus, e′ ≡ ea mod a for each a ∈ S, so e′ = e.

We say that D is an order in a separable Q-algebra if D is an order and DQ = D ⊗Z Q is separable.
Definition 5.2. Suppose that D is an order in a separable Q-algebra DQ . For m, n ∈ Spec(DQ )
with m 6= n, let
n(D, m, n) = #(D/((m ∩ D) + (n ∩ D))),

and let Γ(D) denote the graph on Spec(DQ ) defined by connecting distinct vertices m, n ∈ Spec(DQ )
by an edge if and only if n(D, m, n) > 1.
Lemma 5.3. n(D, m, n) ∈ Z>0 .
Proof. Let R = D/((m ∩ D) + (n ∩ D)). Then n(D, m, n) = #R. Letting −Q = − ⊗Z Q, we have
RQ = DQ /((mQ ∩ DQ ) + (nQ ∩ DQ )) = DQ /(m + n) = 0
so R is torsion. Since R is finitely generated as an abelian group, it is finite, so n(D, m, n) ∈ Z>0 . 

ROOTS OF UNITY IN ORDERS

7

Example 5.4. Let r ∈ Z[X] be monic. Then D = Z[X]/(f ) is an order in a separable Q-algebra
if and only if f is squarefree. Suppose f is squarefree. Then DQ = Q[X]/(f ), and Spec(DQ )
is in bijection with the set of monic irreducible factors g of f in Z[X], each g corresponding to
m = (g)/(f ). If g, h correspond to m, n, respectively, then n(D, m, n) = |R(g, h)|, with R denoting
the resultant.
Suppose
D is an order in a separable Q-algebra. It is natural to ask whether the decomposition
∼ Q
→ m∈Spec(DQ ) DQ /m (Proposition 3.1) gives rise to a decomposition of the order D. This
DQ −
depends on the idempotents that are present in D. The graph Γ(D) tells us which idempotents
occur in D (see Lemma 5.1 and Proposition 5.7).
Notation 5.5. Suppose that D is an order in a separable Q-algebra. If W ⊂ Spec(DQ ), define
Y
DQ /m) = {0, 1}Spec(DQ )
eW = (em )m∈Spec(DQ ) ∈ id(
m∈Spec(DQ )

by em = 1 if m ∈ W and em = 0 if m 6∈ W .
Algorithm 5.6. The algorithm takes an order D in a separable Q-algebra and computes the graph
Γ(D), its connected components, and its weights n(D, m, n) for all m, n ∈ Spec(DQ ).
(i) Use Algorithm 3.2 to compute Spec(DQ ) and the maps DQ → DQ /m for m ∈ Spec(DQ ).
(ii) For each m ∈ Spec(DQ ) compute m∩D = ker(D → DQ /m) by applying the kernel algorithm
in §14 of [5].
(iii) For all m 6= n ∈ Spec(DQ ), apply the image algorithm in §14 of [5] to compute a Z-basis of
image((m ∩ D) ⊕ (n ∩ D) → D) = (m ∩ D) + (n ∩ D)

expressed in a Z-basis of D, and compute n(D, m, n) as the absolute value of the determinant
of the matrix whose columns are those basis vectors.
(iv) Use the numbers n(D, m, n) to obtain the graph Γ(D) and its connected components.
The algorithm runs in polynomial time by well-known graph algorithms (see for example [2]).
Proposition 5.7. Suppose that D is an order in a separable Q-algebra.
Q
(i) Suppose e = (em )m∈Spec(DQ ) ∈ id( m DQ /m) = {0, 1}Spec(DQ ) . Then the following are
equivalent:
(a) e ∈ D,
(b) em = en whenever m and n are connected in Γ(D),
(c) em = en whenever m and n are in the same connected component of Γ(D).
(ii) Let Ω denote the set of connected components of the graph Γ(D) and recall eW from Definition 5.5. Then W 7→ eW gives a bijection
Y
∼
DQ /m.
Ω−
→ prid(D) ⊂ D ⊂
m∈Spec(DQ )

T
Proof. Apply Lemma 5.1 with R = D and S = {m ∩ D : m ∈ Spec(DQ )}. We have a∈S a =
T
Q
Q
S
m (m ∩ D) = {0} since D injects into
mD
QQ /m. Identifying id( DQ /m) with {0, 1} , Lemma
5.1 implies that if e = (em )m∈Spec(DQ ) ∈ id( DQ /m), then e ∈ D if and only if em = en for all
m, n ∈ Spec(DQ ) that are connected in Γ(D). It follows that for each e = (em )m ∈ id(D) the
components em are constant (0 or 1) on each connected component of Γ(D). Part (i) now follows.
It also follows that there is a bijection
P

{subsets of Ω} → id(D)

defined by T 7→ W ∈T eW with inverse e = (em )m 7→ {W ∈ Ω : em = 1 for all m ∈ W }. Under this
bijection, prid(D) corresponds to Ω, and this gives the bijection in (ii).


8

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

Remark 5.8. In particular, by Proposition 5.7(ii) an order D is connected if and only if Γ(D) is
connected.
6. Finding idempotents
The set of idempotents of an order may be too large to compute, but the set of primitive idempotents is something that we are able to efficiently compute.
Algorithm 6.1. Given an order A, the algorithm outputs the set of primitive idempotents of A.
(i) Use Algorithm 4.2 to compute Asep .
(ii) Use Algorithm 5.6 to compute the graph Γ(Asep ) and its connected components.
Q
(iii) For each connected component W of Γ(Asep ), with eW ∈ {0, 1}Spec(E) ⊂ m∈Spec(E) E/m
as in Notation 5.5, use
the inverse of the square matrix with Q-coefficients that gives the
∼ Q
→ m∈Spec(E) E/m of Proposition 3.1 to lift eW to Esep . Output these
natural map Esep −
lifts.
If follows from Proposition 5.7(ii) that the lift eW to Esep is in Asep , and that Algorithm 6.1 gives
the desired output prid(A). It is clear that it runs in polynomial time.
7. Discrete logarithms
In this section, we suppose that G is a multiplicatively written abelian group with elements
represented by finite bitstrings. All algorithms in the present section have G as part of their input.
Thus, saying that they are polynomial-time means that their runtime is bounded by a polynomial
function of the length of the parameters specifying G plus the length of the rest of the input. We
suppose that polynomial-time algorithms for the group operations and for equality testing in G are
available.
Definition 7.1. We say hS|Ri is an efficient presentation for G if S is a finite set, and we have
a map f = fS : S → G satisfying:
Q
(a) f (S) generates G, i.e., the map gS : ZS → G, (bs )s∈S 7→ s∈S f (s)bs is surjective,
(b) R ⊂ ZS is a finite set of generators for ker(gS ),
(c) we have a polynomial-time algorithm
input γ ∈ G finds an element of gS−1 (γ) (i.e.,
Q that on
cs
S
finds (cs )s∈S ∈ Z such that γ = s∈S f (s) ).
Notation 7.2. Suppose hS|Ri is an efficient presentation for G. Define
X
ρ : ZR → ZS , ρ((mr )r∈R ) =
mr r.
r∈R

Suppose T is a finite set and we have a map fT : T → G. By abuse of notation we usually suppress
the maps fS and fT and write s for fS (s) and fT (s) and write hT i for hfT (T )i. Define
Y
gT : ZT → hT i, (bt )t∈T 7→
tbt .
t∈T

Q
Define h = hT : ZT → ZS by using (c) to write each t ∈ T as t = s∈S scs,t and defining
X
h((bt )t∈T ) = (
bt cs,t )s∈S ∈ ZS
t∈T

so that gT = gS ◦ h.

For the remainder of this section we suppose that an efficient presentation hS|Ri for an abelian
group G is given.
Algorithm 7.3. The algorithm takes as input G, an efficient presentation hS|Ri for G, and a finite
set T with a map T → G, and outputs a finite set U = UT of generators for ker(gT ).

ROOTS OF UNITY IN ORDERS

9

(i) Define h − ρ : ZT × ZR → ZS by (h − ρ)(x, y) = h(x) − ρ(y). Use the kernel algorithm in
§14 of [5] to compute a finite set V of generators for ker(h − ρ).
(ii) Compute the image U of V under the projection map ZT × ZR ։ ZT , (x, y) 7→ x.
Theorem 7.4. Algorithm 7.3 produces correct output and runs in polynomial time.
Proof. We have:
x ∈ ker(gT ) ⇐⇒ h(x) ∈ ker(gS ) = im(ρ)

⇐⇒ ∃y ∈ ZR such that h(x) = ρ(y)

⇐⇒ ∃y ∈ ZR such that (h − ρ)(x, y) = 0
⇐⇒ ∃y ∈ ZR such that (x, y) ∈ hV i

⇐⇒ x ∈ proj(hV i) = hproj(V )i = hU i.

Algorithm 7.5. The algorithm takes as input G, an efficient presentation hS|Ri for G, a finite set
T with a map T → G, and an element γ ∈ G, and decidesQ
whether γ ∈ hT i, and if it is, produces an
element of gT−1 (γ) (i.e., finds (ct )t∈T ∈ ZT such that γ = t∈T tct ).
(i) Apply Algorithm 7.3 with T ∪ {γ} in place of T to find a finite set of generators UT ∪{γ} ⊂
ZT ∪{γ} for ker(gT ∪{γ} ), where
gT ∪{γ} : ZT ∪{γ} = ZT × Z{γ} → G,

(x, n) 7→ gT (x)γ n .

(ii) Map the elements u ∈ UT ∪{γ} ⊂ ZT ∪{γ} = ZT ×Z{γ} to their Z{γ} -components u(γ) ∈ Z. If
P
P
UT ∪{γ}
u∈UT ∪{γ} nu u(γ) with (nu )u∈UT ∪{γ} ∈ Z
u∈UT ∪{γ} u(γ)Z 6= Z then γ 6∈ hT i; if 1 =
P
T ∪{γ}
T
{γ}
T
= Z ×Z
is in
then γ ∈ hT i and the Z -component of − u∈UT ∪{γ} nu u ∈ Z
gT−1 (γ).

Algorithm 7.6. The algorithm takes as input G, an efficient presentation hS|Ri for G, and a finite
set T with a map T → G, and outputs an efficient presentation hT |UT i for hT i.
(i) Apply Algorithm 7.3 to obtain a set UT of relations.
(ii) Output the presentation hT |UT i.
Theorem 7.7. Algorithms 7.5 and 7.6 produce correct output and run in polynomial time. In
particular, if one has an efficient presentation for G, and T is a finite set with a map T → G, then
hT |UT i is an efficient presentation for hT i.
Proof. We have:
γ ∈ hT i ⇐⇒ ∃x ∈ ZT such that γ = gT (x)

⇐⇒ ∃x ∈ ZT such that (−x, 1) ∈ ker(gT ∪{γ} : ZT × Z → G) = hUT ∪{γ} i

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

where proj is projection onto the second component.



Algorithm 7.8. The algorithm takes as input G, an efficient presentation hS|Ri for G, finite sets
T and T ′ , and maps fT : T → G and fT ′ : T ′ → G, and outputs a finite set of generators for the
kernel of the composition ZT → G → G/hT ′ i, where ZT → G is the map gT .

10

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

(i) Apply Algorithm 7.3 to the finite set T ⊔ T ′ and the map T ⊔ T ′ → G obtained from fT
and fT ′ , to obtain generators for the kernel of the map
′

′

ZT × ZT = ZT ⊔T → G,

(x, y) 7→ gT (x) − gT ′ (y).

(ii) Project these generators to their ZT -component.

Theorem 7.9. Algorithm 7.8 produces correct output and runs in polynomial time.
Proof. We have:
x ∈ ker(ZT → G/hT ′ i) ⇐⇒ gT (x) ∈ hT ′ i = im(gT ′ )
′

⇐⇒ ∃y ∈ ZT such that gT (x) = gT ′ (y)
′

′

⇐⇒ ∃y ∈ ZT such that (x, y) ∈ ker(ZT × ZT → G)
′

⇐⇒ x ∈ proj(ker(ZT × ZT → G) → ZT )

where proj denotes projection onto the ZT -component.



Proof of Theorem 1.3. One starts by computing E = A ⊗Z Q, using the same structure constants
as for A. Algorithm 3.4 produces a presentation for µ(E), and by Algorithm 3.6 this is an efficient
presentation. Given T and ζ as in Theorem 1.3, one can test whether ζ ∈ E by Algorithm 3.6. Now
Theorem 1.3 is obtained from Algorithm 7.5, with G = µ(E) and γ = ζ.
8. Separable polynomials over connected rings
Proposition 8.1(b) will be used to prove Proposition 10.5 below.
Proposition 8.1. Suppose R is a connected commutative ring, f ∈ R[X], and R[X]f + R[X]f ′ =
R[X]. Then:
(a) if r, s ∈ R and f (r) = f (s) = 0, then r − s ∈ {0} ∪ R∗ ;
(b) if S is a non-zero ring and ϕ : R → S is a ring homomorphism, then the restriction of ϕ
to {r ∈ R : f (r) = 0} is injective;
(c) f 6= 0 and #{r ∈ R : f (r) = 0} ≤ deg(f ).

Proof. Suppose f (r) = f (s) = 0. Write f = (X − r)g and 1 = hf + kf ′ with g, h, k ∈ R[X]. Then
g(r) = f ′ (r) ∈ R∗ . Since g(s) ≡ g(r) mod (r − s)R we can write g(s) = g(r) + (r − s)t with t ∈ R.
Thus, 0 = f (s) = (s − r)g(s) = (s − r)(g(r) + (r − s)t), so
(8.1)

(s − r)g(r) = t(s − r)2 .

Thus, t · (s − r) · g(r)−1 = (t · (s − r) · g(r)−1 )2 , an idempotent. If t · (s − r) · g(r)−1 = 0, then by
(8.1) we have (s − r)g(r) = 0, and thus r − s = 0 since g(r) ∈ R∗ . If t · (s − r) · g(r)−1 = 1, then
r − s ∈ R∗ . This gives (a).
For (b), suppose r, s ∈ R, r 6= s, and f (r) = f (s) = 0. By (a) we have r − s ∈ R∗ . Since
ϕ(1) = 1 6= 0, we have ϕ(r − s) 6= 0.
For (c), let m be a maximal ideal of R. Then R → R/m induces a map
{r ∈ R : f (r) = 0} → {u ∈ R/m : (f mod m)(u) = 0}

that is injective by (b). Since R/m is a field and f mod m ∈ (R/m)[X] is non-zero, we have
#{r ∈ R : f (r) = 0} ≤ deg(f mod m) ≤ deg(f ).


Corollary 8.2. Suppose R is a connected commutative ring, m ∈ Z>0 , and m · 1 ∈ R∗ . Then
{ζ ∈ R : ζ m = 1} is a cyclic subgroup of R∗ whose order divides m.

ROOTS OF UNITY IN ORDERS

11

Proof. Applying Proposition 8.1 with f = X m − 1 gives that the subgroup has order dividing m.
Applying Proposition 8.1 with f = X d − 1 for each divisor d of m gives that this abelian subgroup
has at most d elements of order dividing d, and thus is cyclic.

9. From µ(E) to µ(B)
Fix an order A. Recall that E = AQ = A ⊗Z Q and Asep = A ∩ Esep . For m ∈ Spec(E), the image
of Asep in E/m may be identified with Asep /(m ∩ Asep ); it is a ring of which the additive group is a
finitely generated subgroup of the Q-vector space E/m, so it is an order. We now write
Y
Asep /(m ∩ Asep ).
(9.1)
B=
m∈Spec(E)

This is an order in

Q

m∈Spec(E)

E/m. We identify Asep with its image in B under the map
Y
∼
E/m
→
Esep −
m∈Spec(E)

and identify B with a subring of Esep using the same map. One has
Asep ⊂ B ⊂ Esep .

Since the abelian group B/Asep is both torsion and finitely generated, it is finite, and one has
BQ = Esep . The graph Γ(B) consists of the vertices m ∈ Spec(E) and no edges.
Proposition 9.1. There is a deterministic polynomial-time algorithm that, given an order A, computes a Z-basis for Asep /(m ∩ Asep ) in E/m for every m ∈ Spec(E), a Z-basis for B in Esep , and
the index (B : Asep ).
Proof. One simply computes a Z-basis for Asep as in Algorithm 4.2, and a Z-basis for the image
of the map Asep ⊂ Esep → E/m using the image algorithm in §14 of [5], for each m ∈ Spec(E).
Combining these bases for all m and applying the inverse of the second isomorphism in Proposition
3.1 one finds a Z-basis for B in Esep . The index (B : Asep ) is the absolute value of the determinant
of any matrix expressing a Z-basis for Asep in a Z-basis for B.

Proposition 9.2. For each order A and each m ∈ Spec(E) the group µ(Asep /(m ∩ Asep )) is finite
cyclic. Also, there is a deterministic polynomial-time algorithm that, given A and m, computes a
generator θm of µ(Asep /(m ∩ Asep )), its order, the complete prime factorization of its order, and, for
each prime number p a generator θm,p for µ(Asep /(m ∩ Asep ))p .
Proof. The first statement follows from Lemma 3.3(iii). For θm one can take the first power of the
generator ζm of µ(E/m) found in Algorithm 3.4 that belongs to Asep /(m ∩ Asep ), i.e., for which all
coordinates on a Z-basis of Asep /(m ∩ Asep ) (which is a Q-basis of E/m) are integers. The order
of θm is then easy to write down, and since the prime numbers dividing that order are, by Lemma
3.3(iv), bounded by 1 + rankZ (A), it is also easy to factor into primes. If pk is a prime power exactly
order(θm )/pk

dividing order(θm ), one can take θm,p = θm

.



Proposition 9.3. There is a deterministic polynomial-time algorithm that, given an order A, determines all prime factors p of #µ(B), with B as in (9.1), as well as an efficient presentation for
µ(B) and, for each p, an efficient presentation for µ(B)p .
Proof. This follows directly from Proposition 9.2 and the isomorphisms
Y
Y
µ(Asep /(m ∩ Asep ))p
µ(Asep /(m ∩ Asep )) and µ(B)p ∼
µ(B) ∼
=
=
m∈Spec(E)

in the same way as for µ(E) in section 3.

m∈Spec(E)



12

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

10. From µ(B)p to µ(C)p
Let A, E, Asep , and B be as in the previous section, and fix a prime number p. Let
C = Asep [1/p] ∩ B.

(10.1)
We have
so C is an order with CQ = Esep , and

Asep ⊂ C ⊂ B ⊂ Esep

C = {x ∈ B : pi x ∈ Asep for some i ∈ Z≥0 }.

The group C/Asep is finite of p-power order, and the group B/C is finite of order prime to p.
These orders can be quickly computed from the order of B/Asep computed in Proposition 9.1. We
emphasize that C depends on p.
Let t = (B : C). Then C/Asep = t(B/Asep ), so C = tB + Asep , which is the image of the map
B ⊕ Asep → B, (x, y) 7→ tx + y. Thus one can find a Z-basis for C from the image algorithm in §14
of [5].
Proposition 10.1. Suppose that A is an order and p is a prime. Suppose m, n ∈ Spec(E) with
m 6= n. Then:
(i) C/((m ∩ C) + (n ∩ C)) is the non-p-component of Asep /((m ∩ Asep ) + (n ∩ Asep ));
(ii) m and n are connected in Γ(C) if and only if n(Asep , m, n) 6∈ pZ≥0 .
Proof. For Z = Asep , B, and C, write Z̃ for the finite abelian group Z/((m∩Z)+(n∩Z)) (cf. Lemma
5.3). Let pr = (C : Asep ) and t = (B : C). Then gcd(pr , t) = 1. Since Γ(B) has no edges, we have
1 /
1 /
C̃ o
B̃ = 0 where a map
(m ∩ B) + (n ∩ B) = B, so B̃ = 0. Consider the maps Ã o
sep

pr

t

d

/ Z̃2 is the map induced by multiplication by d on Z1 . (The maps are well-defined since
Z̃1
Asep ⊂ C ⊂ B and pr C ⊂ Asep and tC ⊂ B.)
1 /
t /
Since B̃ = 0, taking the composition C̃
B̃
C̃ shows that tC̃ = 0. If x ∈ C̃ and
pr x = 0, then since gcd(pr , t) = 1 we have x = 0. Thus, the composition C̃

pr

/ Ãsep

injection, and thus an automorphism α of the finite abelian group C̃. It follows that Ãsep
surjective and C̃

pr

1

/ C̃ is an
1

/ C̃ is

/ Ãsep is injective. Further, letting Ãsep [pr ] denote the kernel of multiplication

by pr in Ãsep , we have
1

ker( Ãsep

/ C̃ ) = ker( Ãsep

1

pr

/ C̃

/ Ãsep ) = Ãsep [pr ] .

This gives a split short exact sequence
0

/ Ãsep [pr ]

/ Ãsep o

1
p α−1

/ C̃

/0

r

with C̃ killed by t. Thus C̃ is the non-p-component of Ãsep , proving (i).
We have n(Asep , m, n) 6∈ pZ≥0 if and only if Ãsep is not a p-group, i.e., if and only if C̃ 6= 0 (by
(i)). But C̃ 6= 0 if and only if m and n are connected in Γ(C). This gives (ii).

One could compute Γ(C) by applying Algorithm 5.6 with D = C. Thanks to Proposition 10.1
we can compute Γ(C) without actually computing C, as follows.
Algorithm 10.2. The algorithm takes an order A and the numbers n(Asep , m, n), and computes
the graph Γ(C) and its connected components.

ROOTS OF UNITY IN ORDERS

13

(i) Connect two vertices m and n if and only if n(Asep , m, n) 6∈ pZ≥0 .
(ii) Output the associated graph and the connected components.
Definition 10.3. If W ⊂ Spec(E), let CW denote the image of C in the quotient
Y
Asep /(m ∩ Asep )
m∈W

of B.

Lemma 10.4.QLet Ω denote the set of connected components of the graph Γ(C). Then the natural
map F : C → W ∈Ω CW is an isomorphism.
Proof. The map F is injective, since

C⊂B=

Y Y

W ∈Ω m∈W

Asep /(m ∩ Asep ).

If fW : C ։ CW is the natural map, eQ
Notation 5.5 with D = C, and x =
W is as defined in P
(fW (cW ))W ∈Ω is an arbitrary element of W ∈Ω CW , then F ( W ∈Ω cW eW ) = x, so F is surjective.
The result now follows from Proposition 5.7(ii).

Proposition 10.5. Suppose A is an order and p is a prime number. Recall C as defined in (10.1).
Fix a subset W ⊂ Spec(E) for which the induced subgraph of Γ(C) is connected. Then:
(i) the ring CW is connected,
(ii) the natural map µ(CW )p → µ(C{m} )p is injective for all m ∈ W ,
(iii) the group µ(CW )p is cyclic,
(iv) if W ′ is a non-empty subset of W , then the natural map µ(CW )p → µ(CW ′ )p is injective.
Proof. Part (i)Qfollows from Lemma 5.1.
Let BW = m∈W Asep /(m ∩ Asep ). We have
id(CW [1/p]) ⊂ id

Y

m∈W

E/m

!

= id(BW ).

Recall B from (9.1). Since (B : C) is coprime to p, so is (BW : CW ). Suppose e ∈ id(CW [1/p]).
Then e ∈ id(BW ) and there exists m ∈ Z − pZ such that me ∈ CW (e.g., m = (BW : CW )). Further,
there exists k ∈ Z≥0 such that pk e ∈ CW . Since m and pk are coprime, we have e ∈ CW . Thus,
id(CW [1/p]) = id(CW ) = {0, 1}, so CW [1/p] is connected. Now by Corollary 8.2 with R = CW [1/p]
and m = #µ(CW [1/p])p , the group µ(CW [1/p])p is cyclic, so its subgroup µ(CW )p is cyclic as
well, which is (iii). Also, by Proposition 8.1(b) with R = CW [1/p] and f = X m − 1, the map
µ(CW [1/p])p → µ(CW ′ [1/p])p is injective for each non-empty W ′ ⊂ W . This implies (iv). With
W ′ = {m} one obtains (ii).

Remark 10.6. If A is a connected order in a separable Q-algebra and p is a prime number that
does not divide #(B/A), then µ(A)p is cyclic. This follows from Proposition 10.5(iii); C = A since
E = Esep and p ∤ #(B/A), and one can take C = CW since A is connected.
By Proposition 10.5(ii,iii), if W is a connected component of Γ(C), then the natural map
µ(CW )p → µ(A/(m ∩ A))p

is injective for all m ∈ W , and µ(CW )p is cyclic. This gives an efficient algorithm for computing
µ(CW )p , and thus a set of generators for µ(C)p , as follows.
Algorithm 10.7. Given an order A and a prime p, the algorithm finds an efficient presentation for
µ(C)p .

14

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

(i) Apply Algorithm 9.2 to compute a generator of the cyclic group µ(Asep /(m ∩ Asep ))p for
each m ∈ Spec(E).
(ii) Apply Algorithm 10.2 to compute Γ(C) and its connected components W .
(iii) For each W , do the following:
(a) Apply the image algorithm in §14 of [5] to compute a basis for the order
Y
CW = image(C →
E/m).
m∈W

(b) Pick m1 ∈ W with #µ(Asep /(m1 ∩ Asep ))p minimal.
(c) Choose
W1 = {m1 } ⊂ W2 = {m1 , m2 } ⊂ . . . ⊂ W
such that #Wi = i for all i ≥ 1, and Wi = Wi−1 ∪ {mi } for all i ≥ 2, and each mi is
connected in Γ(C) to some mj with j < i.
(d) For i = 1, 2, . . . compute each µ(CWi )p , and a generator for it, in succession by using
that µ(CW1 )p = µ(Asep /(m1 ∩ Asep ))p is given, and for i > 1 listing all ordered pairs
in µ(CWi−1 )p × µ(Asep /(mi ∩ Asep ))p and testing whether they are in CWi , and using
that
µ(CWi )p = CWi ∩ (µ(CWi−1 )p × µ(Asep /(mi ∩ Asep ))p ).

This gives a generatorQof µ(CW )p for each W in the set Ω of connected components
of Γ(C). Let ζW ∈ V ∈Ω µ(CV )p be the element with this generator as its W -th
component, and all other components 1.
Q
(iv) View the set S = {ζW : W ∈ Ω} in µ(C)p via the isomorphism µ(C)p ∼
= W ∈Ω µ(CW )p of
Lemma 10.4, let R = {order(ζW )(W -th basis vector)}, and output hS|Ri.
Proposition 10.8. Algorithm 10.7 gives correct output and runs in polynomial time.
∼ L
∼ Q
→ W µ(CW )p so the output of the
Proof. By Lemma 10.4 we have C −
→ W CW . Thus, µ(C)p −
algorithm is a set of generators for µ(C)p . We have
CWi ⊂ CWi−1 × C{mi } ,

C{mi } = Asep /(mi ∩ Asep ).

Thus,
µ(CWi )p ⊂ µ(CWi−1 )p × µ(Asep /(mi ∩ Asep ))p .
By Proposition 10.5, the group µ(CWi )p injects into each factor, and each factor is cyclic of prime
power order. Each factor has size polynomial in the size of the algorithm’s inputs (given an order of
rank n and an element of order pk , we have ϕ(pk ) ≤ n by Lemma 3.3, so pk ≤ 2n). By Proposition
10.5(ii) the natural map µ(CWi )p → µ(Asep /(m1 ∩ Asep ))p is injective, for all i. As i gets larger, the
groups µ(CWi )p get smaller or stay the same. Thus one can list all ordered pairs, and then efficiently
test whether they are in CWi . It follows from the above that the algorithm runs in polynomial time.
The presentation hS|Ri is efficient by Algorithm 7.6 and Proposition 9.3, since µ(C)p ⊂ µ(B)p . 
Remark 10.9. A more intelligent algorithm for step (iii)(d) is to use that each µ(CWi )p is cyclic
(by Proposition 10.5(iii)), and that µ(CWi )p ⊂ µ(CWi−1 )p , as follows. Starting with i = 1 and
incrementing i, proceed as follows in place of step (d). If µ(CWi−1 )p is trivial, stop. Otherwise, take
an element a1 ∈ µ(CWi−1 )p of order p and for each of the p − 1 elements b1 ∈ µ(Asep /(mi ∩ Asep ))p
of order p test whether (a1 , b1 ) ∈ CWi . If there are none, stop (the group is trivial for that Wi ). If
there is such a pair (a1 , b1 ) ∈ µ(CWi ), if #µ(CWi )p = p then stop with (a1 , b1 ) as generator, and
otherwise take each a2 ∈ µ(CWi−1 )p that is a p-th root of a1 and for each of the p possible choices of
elements b2 ∈ µ(Asep /(mi ∩ Asep ))p that are a p-th root of b1 , test whether (a2 , b2 ) ∈ CWi . As soon
as such is found, if #µ(CWi )p = p2 then stop with (a2 , b2 ) as generator, and otherwise continue this
process. Injecting into each component implies one only needs to check ordered pairs with the same

ROOTS OF UNITY IN ORDERS

15

order in each component. Since #µ(CWi )p divides #µ(CWi−1 )p , one only needs to go up to elements
of order #µ(CWi−1 )p . The number of trials is < plogp (#µ(CWi−1 )p ), since there are p choices each
time, and there are logp (#µ(CWi−1 )p ) steps. The final (aj , bj ) found is a generator for µ(CWi )p .
11. Nilpotent ideals in finite rings
Suppose R is a finite commutative ring and I is a nilpotent ideal of R. Algorithm 11.3 below
solves the discrete logarithm problem in the multiplicative group 1 + I, using the finite filtration:
1 + I ⊃ 1 + I 2 ⊃ 1 + I 4 ⊃ · · · ⊃ 1,

i

i+1

the fact that the map x 7→ 1 + x is an isomorphism from the additive group I 2 /I 2
to the
2i
2i+1
multiplicative group (1 + I )/(1 + I
), and the fact that the discrete logarithm problem is easy
in these additive groups.
We specify a finite commutative ring by giving a presentation for its additive group, i.e., a finite set
of generators and a finite set of relations, and for every pair of generators their product is expressed
as a Z-linear combination of the generators.
The following result can be shown using standard methods.
Proposition 11.1. There is a deterministic polynomial-time algorithm that, given a finite commutative ring R and 2 ideals I1 and I2 of R such that I2 ⊂ I1 , computes an efficient presentation of
the finite abelian group I1 /I2 .
√
Lemma 11.2. Suppose R is a finite commutative ring, I is an ideal of R such that I ⊂ 0R , and
i
i+1
i
for each S
i ∈ Z≥0 the set Bi is a subset of I 2 such that Bi ∪ I 2
generates the additive group I 2 .
Let B = i≥0 Bi . Then 1 + I = h1 + b : b ∈ Bi (as a multiplicative group).
i

Proof. Since I is nilpotent, 1 + I 2 is a multiplicative group for all i ∈ Z≥0 . We have
i

i+1

I 2 /I 2
i+1

∼

i

i+1

−
→ (1 + I 2 )/(1 + I 2

)

i

i+1

via x 7→ 1 + x. Since Bi ∪ I 2
generates the additive group I 2 , we have that Bi + I 2
generates
k
k
2i
2i+1
2k+1
I /I
. If I
= 0, then Bk generates I 2 and 1 + Bk generates the multiplicative group 1 + I 2 .
It now follows that 1 + B generates 1 + I.

√
Algorithm 11.3. Given a finite commutative ring R, an ideal I of R such that I ⊂ 0, for each
i
i+1
i
i ∈ Z≥0 a subset Bi of I 2 such that Bi ∪ I 2
generates the additive group I 2Q, with all but finitely
B
manySBi = ∅, and x ∈ I, the algorithm computes (mb )b∈B ∈ Z with 1 + x = b∈B (1 + b)mb , where
B = i≥0 Bi , as follows.
(i) Let x0 = x. For i = 0, 1, . . . use Proposition 11.1 to find (mb )b∈Bi ∈ ZBi such that
X
i+1
i
i+1
mb b mod I 2
(in I 2 /I 2 ).
xi ≡
b∈Bi

i+1

Define xi+1 ∈ I 2

by
1 + xi+1 = (1 + xi )

Y

(1 + b)−mb .

b∈Bi

As soon as xi+1 = 0, terminate, setting mb = 0 for all b ∈ Bj with j > i and outputting
(mb )b∈B ∈ ZB .
Proposition 11.4. Algorithm 11.3 is a deterministic algorithm that produces correct outputs in
polynomial time.

16

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

Proof. Since I is a nilpotent ideal, there exists j ∈ Z≥0 such that I 2 = 0. Then xj = 0 and the
algorithm gives
Y
Y
(1 + b)mb =
(1 + b)mb
1 + x = 1 + x0 =
b∈

S

i<j

Bi

b∈B

as desired.



Lemma 11.5. There is a deterministic polynomial-time
algorithm that, given a finite commutative
√
i
ring R, an ideal I of R such that I ⊂ 0, and for each i ∈ Z≥0 a subset Bi of I 2 such that
i+1
i
Bi ∪ I 2
generates
the additive groupSI 2 , computes a Z-basis for the kernel of the map ZB → 1 + I,
Q
mb
(mb )b∈B 7→ b (1 + b) , where B = i≥0 Bi .
Proof. Let Cj =

S

k≥j

j

Bj . We proceed by induction on decreasing j. We have h1 + Cj i = 1 + I 2
j

(applying Lemma 11.2 with I 2 in place of I). Assume we already have defining relations for 1 + Cj ,
Q
j
i.e., we have generators for the kernel of ZCj → 1 + I 2 , (mb )b∈Cj 7→ b∈Cj (1 + b)mb , and would like
to find defining relations for 1 + Cj−1 . Proposition 11.1 gives an algorithm for finding a basis for the
Q
j−1
j
j
kernel of ZBj−1 → I 2 /I 2 , (nb )b∈Bj−1 7→ b∈Bj−1 nb b + I 2 in polynomial time. For each defining
Q
P
j
j
relation (nb )b∈Bj−1 for Bj−1 + I 2 we have b∈Bj−1 nb b ≡ 0 mod I 2 so b∈Bj−1 (1 + b)nb ≡ 1 mod
j

(1 + I 2 ). Algorithm 11.3 gives a polynomial-time algorithm to find (mb′ )b′ ∈Cj ∈ ZCj such that
Q
Q
j
nb
= b′ ∈Cj (1 + b′ )mb′ ∈ 1 + I 2 . Then ((nb )b∈Bj−1 , (−mb′ )b′ ∈Cj ) is in the kernel of
b∈Bj−1 (1 + b)
j−1

the map ZCj−1 → 1 + I 2 , and these relations along with the defining relations for 1 + Cj form a
set of defining relations for 1 + Cj−1 .


Theorem 11.6. There is a deterministic
√ polynomial-time algorithm that, given a finite commutative
ring and an ideal I of R such that I ⊂ 0, produces an efficient presentation h1 + B|Ri for 1 + I.
i

Proof. Apply the algorithm in Proposition 11.1 to obtain for each i ∈ Z≥0 a set Bi ⊂ I 2 such that
i+1
i
Bi ∪ I 2
generates the additive group I 2 . S
Since I is nilpotent, we can take Bi = ∅ for all but
finitely many i. By Lemma 11.2 the set B = i≥0 Bi has the property that 1 + B generates 1 + I.
Defining relations R are given by Lemma 11.5, and part (c) of Definition 7.1 holds by Proposition
11.4.

Theorem 1.4 now follows from Theorem 11.6 and Algorithm 7.6.
Remark 11.7. Suppose R is a finite commutative ring, I ⊂ R is a nilpotent ideal, and R′ is a
subring of R. Let I ′ = I ∩ R′ . The algorithm in Theorem 11.6 gives efficient presentations for the
multiplicative groups 1 + I and 1 + I ′ . We can apply Algorithm 7.8 with G = 1 + I ⊂ R∗ , and T ′ a
set of generators for 1 + I ′ , and T a set of generators for some subgroup of 1 + I. In the next section
we will apply this to our setting.
√
Example 11.8. Let R = Z/p2 Z and I = 0R = pZ/p2 Z. Then I 2 = 0, and 1 + I is the order
∼
→ Z/pZ, 1 + x 7→ x/p is a group
p subgroup of (Z/p2 Z)∗ ∼
= Z/pZ × Z/(p − 1)Z. The map 1 + I −
isomorphism, so the discrete logarithm problem is easy in 1 + I.
√
∼
Example 11.9. Let R = Z/p4 Z and I = 0R = pZ/p4 Z. Then I 4 = 0. Here, the map 1 + I −
→
Z/p3 Z, 1 + x 7→ x/p is not a group homomorphism. The discrete logarithm problem is easy in 1 + I
not because it is (isomorphic to) an additive group, but because there is a filtration of additive
groups, namely, (1 + I)/(1 + I 2 ) ∼
= I/I 2 and (1 + I 2 )/(1 + I 4 ) ∼
= I 2 /I 4 = I 2 .

ROOTS OF UNITY IN ORDERS

17

12. From µ(C)p to µ(A)p
Let A be an order and let p be a prime. Recall C from Definition 10.1 and let
f = {x ∈ C : xC ⊂ Asep },
which is the largest ideal of C that is contained in A. We shall see that C/f is a finite ring, and it
has Asep /f as a subring. Suppose we are given a set M ⊂ C ∗ such that µ(C)p = hM i. Let
X
I=
(ζ − 1)(C/f),
I ′ = I ∩ (Asep /f).
ζ∈M

Define
g1 : ZM ։ µ(C)p ,

(aζ )ζ∈M 7→

Y

ζ aζ ,

ζ∈M

let g2 : µ(C)p → 1 + I be the natural map ζ 7→ ζ + f, let ĝ : µ(C)p → (1 + I)/(1 + I ′ ) denote the
composition of g2 with the quotient map, define g : ZM → 1 + I by g = g2 ◦ g1 , and define
(12.1)

ψ : ZM → (1 + I)/(1 + I ′ )

by

ψ = ĝ ◦ g1 .

Proposition 12.1. With notation as above,
p
(i) I is a nilpotent ideal of C/f, i.e., I ⊂ 0C/f;
(ii) I ′ is a nilpotent ideal of Asep /f;
(iii) C/f is a finite ring of p-power order,
(iv) µ(A)p is the kernel of the map ĝ;
(v) µ(A)p is the image of ker(ψ) under the map g1 .
p
Proof. Since C/A is killed by pr for some r ∈ Z≥0 , we have pr ∈ f, so p ∈ 0C/f , so p is in every
prime ideal of C/f. Suppose ζ ∈ µ(C)p . Then the image p
of ζ in every field of characteristic p is
1. Thus, ζ − 1 is in every prime ideal of C/f, so ζ − 1 ∈ 0C/f . By the definition of I we have
p
I ⊂ 0C/f , and (i) and (ii) follow.
Since pr ∈ f we have pr C ⊂ f, so C/f is a quotient of C/pr C, which is a finite ring of p-power
order. This gives (iii).
Part (iv) follows directly from the definitions, and then (v) follows from (iv).

Algorithm 12.2. The algorithm takes as input an order A, a prime p, and a finite set of generators
M for µ(C)p , and computes a finite set of generators for µ(A)p .
(i) Compute the finite abelian group C/Asep and
Hom(C, C/Asep ) ∼
= (C/Asep ) ⊕ (C/Asep ) ⊕ · · · ⊕ (C/Asep )

(ii)
(iii)
(iv)
(v)

(with rankZ (C) summands C/Asep ), and compute f as the kernel of the group homomorphism Asep → Hom(C, C/Asep ) sending x ∈ Asep to the map y 7→ xy + Asep . Next compute
the finite rings Asep /f ⊂ C/f. This entire step can be done using standard algorithms for
finitely generated abelian groups.
Apply the algorithm in Theorem 11.6 with R = C/f and the I of this section to obtain an
efficient presentation for 1 + I.
Apply the algorithm in Theorem 11.6 with R = Asep /f and I ′ in place of I to obtain a finite
set T ′ of generators for 1 + I ′ .
Apply Algorithm 7.8 with G = 1 + I, the efficient presentation from step (ii), T = M , and
T ′ from step (iii) to obtain a finite set of generators S ′ for ker(ZT → G/hT ′ i).
Take the image of S ′ under the map g1 : ZM → µ(C)p .

Theorem 12.3. Algorithm 12.2 produces correct output and runs in polynomial time.

18

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

Proof. Since C/f and Asep /f are finite commutative rings, and I and I ′ are nilpotent, Theorem 11.6
is applicable in steps (ii) and (iii). The map ZM = ZT → G/hT ′ i = (1 + I)/(1 + I ′ ) in step (iv) is
our map ψ from (12.1). By Proposition 12.1(v), step (v) produces generators for µ(A)p .

13. Finding roots of unity
Algorithm 13.1. Given an order A, the algorithm outputs a finite set of generators for µ(A).
(i) Use Algorithm 3.2 to compute Esep , all m ∈ Spec(E), the fields E/m, and the natural maps
E → E/m.
(ii) Apply Algorithm 4.2 to compute Asep = A ∩ Esep .
(iii) Apply Algorithm 9.1 to compute for each m ∈ Spec(E) the subring Asep /(m ∩ Asep ) of
Esep /m.
(iv) Apply the algorithm in Proposition 9.2 to compute, for each m ∈ Spec(E), a generator θm
for µ(Asep /(m ∩ Asep )), its order, the prime factorization of its order, and for each prime p
dividing its order a generator θm,p of µ(Asep /(m ∩ Asep ))p .
(v) For each prime p dividing the order of at least one of the groups µ(Asep /(m ∩ Asep )), do the
following:
(a) Use the image algorithm in §14 of [5] to compute a Z-basis for C = Asep [1/p] ∩ B (as
discussed in §10 above, just before Proposition 10.1).
(b) Apply Algorithm 10.7 to compute an efficient presentation for µ(C)p .
(c) Apply Algorithm 12.2 to compute generators for µ(A)p .
(vi) Generators for these groups µ(A)p form a set of generators for µ(A).
That Algorithm 13.1 produces correct output and runs in polynomial time follows immediately.
We can now obtain a deterministic polynomial-time algorithm that, given an order A, determines
an efficient presentation for µ(A).
Algorithm 13.2. The algorithm takes an order A and produces an efficient presentation for µ(A).
(i) Apply the algorithm in Proposition 9.3 to obtain an efficient presentation hS|Ri for µ(B).
(ii) Apply Algorithm 13.1 to obtain a finite set of generators for µ(A).
(iii) Apply Algorithm 7.6 with G = µ(B) to obtain an efficient presentation for µ(A).
Example 13.3. Let A = Z[X]/(X 4 − 1). Then with p = 2:

B = C = Z[X]/(X − 1) × Z[X]/(X + 1) × Z[X]/(X 2 + 1) ∼
= Z × Z × Z[i],

and (C : A) = 8. We identify X with (1, −1, i) ∈ Z × Z × Z[i]. Then

µ(A)2 = µ(A) ⊂ µ(B) = µ(C)2 = h(−1, 1, 1), (1, −1, 1), (1, 1, i)i.

We have
of index 64 in C, and

f = 4Z × 4Z × 2Z[i]
C/f = Z/4Z × Z/4Z × Z[i]/2Z[i] = Z/4Z × Z/4Z × F2 [ε]

with ε = 1 + i. The index 8 subring of C/f generated by (1, −1, 1 + ε) is A/f. Alternatively,
A/f = (Z/4Z)[Y ]/(2Y, Y 2 )

where Y = X − 1 = (0, 2, ε) ∈ A/f. With M = {(−1, 1, 1), (1, −1, 1), (1, 1, i)} we have
p
I = (2Z/4Z) × (2Z/4Z) × (εF2 [ε]) = 0C/f ,

I 2 = 0, and

I ′ = I ∩ (A/f) =

p
0A/f = {0, 2, Y, Y + 2}.

ROOTS OF UNITY IN ORDERS

19

With ψ as in (12.1), we have ψ(a, b, c) = a + b + c + 2Z ∈ Z/2Z and
ker(ψ) = {(a, b, c) ∈ ZM : a + b + c is even} = Z · (2, 0, 0) + Z · (1, 1, 0) + Z · (1, 0, 1).
Algorithm 13.1 outputs
µ(A) = µ(A)2 = h−X 2 i × h−X 3 i = hX, −1i ∼
= Z/2Z × Z/4Z.
Example 13.4. Let A = Z[X]/(X 12 − 1). Then

E = Q[X]/(X 12 − 1) ∼
= Q × Q × Q(ζ3 ) × Q(i) × Q(ζ3 ) × Q(ζ12 )

and
B = Z[X]/(X − 1) × Z[X]/(X + 1) × Z[X]/(X 2 + X + 1)

× Z[X]/(X 2 + 1) × Z[X]/(X 2 − X + 1) × Z[X]/(X 4 − X 2 + 1) ֒→ E.

We have for the discriminants of the orders:
|∆B | = 1 · 1 · 3 · 4 · 3 · 122 ,

|∆A | = 1212 ,

so
#(B/A) =

p
|∆A |/|∆B | = 29 · 34 .

Thus if p = 2 then (C : A) = 29 , while if p = 3 then (C : A) = 34 . The graph Γ(B) consists of 6
vertices with no edges. With the numbers n(A, m, n) on the edges, the graph Γ(A) is:
(X + 1)
♠♠

2 ♠♠♠♠

(X − 1)

♠♠♠
♠♠♠

2

◗◗◗
◗◗◗ 2
◗◗◗
◗◗◗
(X 2 + 1)

3
9
(X 2 − X + 1)
◗◗◗
♠♠
♠
◗
♠
◗
4♠♠
◗◗4 ◗
◗◗◗
♠♠♠
◗
♠♠♠
(X 2 + X + 1)
(X 4 − X 2 + 1)
3

4

Suppose p = 2. Then the graph Γ(C) is:
•
•

•
•

•
Q

•

We have µ(C)2 =
µ(CW )2 with the product running over the 3 connected components W .
The left 2 W ’s give µ(CW )2 = {±1}, while the remaining one gives µ(CW )2 = h−X 3 i. This gives
−X 3 , −1 ∈ µ(A)2 .

20

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

Suppose p = 3. Then the graph Γ(C) is:

•

Q

•

•
⑧ ❅❅❅
⑧
❅❅
⑧
❅❅
⑧⑧
⑧⑧

•
⑧ ❅❅❅
⑧
❅❅
⑧
❅❅
⑧⑧
⑧⑧

•

•

We have µ(C)3 = µ(CW )3 with the product running over the 2 connected components W . The
top W has µ(CW )3 = {1}, while for the bottom W one has that µ(CW )3 is generated by the image
of X 4 , and this gives X 4 ∈ µ(A)3 .
Continuing the algorithm by hand is more complicated than in the previous example. However,
we note that here A is the order ZhGi defined in [7] with G = h−1i × hXi ∼
= Z/2Z × Z/12Z, and it
follows from Remark 16.3 of [7] that µ(A) = G = h−1i × hXi.
References
[1] M. F. Atiyah and I. G. Macdonald, Introduction to commutative algebra, Addison-Wesley Publishing Co., Reading, MA, 1969.
[2] J. Hopcroft and R. Tarjan, Algorithm 447: efficient algorithms for graph manipulation, Communications of the
ACM, 16, no. 6 (1973) 372–378.
[3] S. Lang, Algebra, Third edition, Graduate Texts in Mathematics 211, Springer-Verlag, New York, 2002.
[4] A. K. Lenstra, Factoring polynomials over algebraic number fields, in Computer algebra (London, 1983), Lect.
Notes in Comp. Sci. 162, Springer, Berlin, 1983, 245–254.
[5] 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.
[6] 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.
[7] H. W. Lenstra, Jr. and A. Silverberg, Lattices with symmetry, to appear in Journal of Cryptology,
https://eprint.iacr.org/2014/1026.
[8] H. W. Lenstra, Jr. and A. Silverberg, Algorithms for commutative algebras over the rational numbers,
http://arxiv.org/abs/1509.08843.
Mathematisch Instituut, Universiteit Leiden, The Netherlands
E-mail address: hwl@math.leidenuniv.nl
Department of Mathematics, University of California, Irvine, CA 92697
E-mail address: asilverb@math.uci.edu

