Roots of unity in orders

Other algebras and orders, and their zeta and (L)-functions (11R54) Number-theoretic algorithms; complexity (11Y16) General commutative ring theory (13A99) Commutative orders (16H15)

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.

Review text

This paper provides efficient deterministic algorithms relative to the idempotents and the roots of the unit in an order \(A\)\, (a commutative ring with additive group isomorphic to \(\mathbb{Z}^n\)). In particular, the paper gives an algorithm with polynomial complexity which computes the set of the primitive idempotents of \(A\) (Theorem 1.1 and Algorithm 6.1) and a polynomial algorithm finding generators and relations for the group \(\mu(A)\)\, of the roots of unity of \(A\) (Theorem 1.2 and Algorithm 13.2). The paper also proves that the discrete logarithm on \(\mu(A)\)\, can be solved in polynomial time (Theorem 1.3). Therefore this group is not suitable for cryptographic purposes. Section 1 gives an summary of the proof of Theorems 1.1 and 1.2. ``It makes use of several techniques from commutative algebra that so far have found little employment in an algorithmic context. Algorithm 6.1 is given in Section 6 and Section 7 provides the proof of Theorem 1.3. The rest of the paper deals with the tools and the intermediate necessary steps and algorithms underlying Theorem 1.1. Algorithm 13.1 is given in Section 13.

Recommendations

Cites work

Cited in

(10)

Describes a project that uses

Uses Software

Algorithm 447

This page was built for publication: Roots of unity in orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2362292)