Roots of unity in orders (Q2362292): Difference between revisions

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.