Efficient Algorithms for Finite Z-Algebras

For a finite Z-algebra R, i. e. , for a Z-algebra which is a finitely generated Z-module, we assume that R is explicitly given by a system of Z-module generators G, its relation module 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 Kx₁, , xₙ/I with K=Q or K=Fₚ. The task of finding the associated primes of a finite 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 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\"obner basis of an ideal I such that R = Zx₁, , xₙ/I.