Efficient Algorithms for Finite $\mathbb{Z}$-Algebras

Abstract

For a finite $\mathbb{Z}$-algebra $R$, i.e., for a $\mathbb{Z}$-algebra which is a finitely generated $\mathbb{Z}$-module, we assume that $R$ is explicitly given by a system of $\mathbb{Z}$-module generators $G$, its relation module $\mathrm{Syz}(G)$, and the structure constants of the multiplication in $R$. In this setting we develop and analyze efficient algorithms for computing essential information about $R$. First we provide polynomial time algorithms for solving linear systems of equations over $R$ and for basic ideal-theoretic operations in $R$. Then we develop ZPP (zero-error probabilitic polynomial time) algorithms to compute the nilradical and the maximal ideals of 0-dimensional affine algebras $K[x_1,\dots ,x_n]/I$ with $K=\mathbb{Q}$ or $K={\mathbb{F}}_p$. The task of finding the associated primes of a finite $\mathbb{Z}$-algebra $R$ is reduced to these cases and solved in ZPPIF (ZPP plus one integer factorization). With the same complexity, we calculate the connected components of the set of minimal associated primes $\mathrm{minPrimes}(R)$ and then the primitive idempotents of $R$. Finally, we prove that knowing an explicit representation of $R$ is polynomial time equivalent to knowing a strong Gröbner basis of an ideal $I$ such that $R=\mathbb{Z}[x_1,\dots ,x_n]/I$.

Published in journal of Groups, Complexity, Cryptology