Polynomial-Time Algorithms for Black-Box Distributive Expanded Groups

Let $Ω$ be a finite set of finitary operation symbols. An $Ω$-expanded group is a group (written additively and called the additive group of the $Ω$-expanded group) with an $Ω$-algebra structure. We use the black-box model of computation in $Ω$-expanded groups. In this model, elements of a finite $Ω$-expanded group H are represented (not necessarily uniquely) by bit strings of the same length, say, n. Given representations of elements of H, equality testing and the fundamental operations of H are performed by an oracle. Assume that H is distributive, i.e., all its fundamental operations associated with nonnullary operation symbols in $Ω$ are distributive over addition. Suppose s=(s₁,,sₘ) is a generating system of H. In this paper, we present probabilistic polynomial-time black-box $Ω$-expanded group algorithms for the following problems: (i) given (1ⁿ,s), construct a generating system of the additive group of H, (ii) given (1ⁿ,s,(t₁,,tₖ)) with t₁,,tₖ∈ H, find a generating system of the additive group of the ideal in H generated by ₁,,tₖ\, and (iii) given (1ⁿ,s), decide whether H∈ V, where V is an arbitrary finitely based variety of distributive $Ω$-expanded groups with nilpotent additive groups. The error probability of these algorithms is exponentially small in n. In particular, this can be applied to groups, rings, R-modules, and R-algebras, where R is a fixed finitely generated commutative associative ring with $1$. Rings and R-algebras may be here with or without $1$, where $1$ is considered as a nullary fundamental operation. 16 pages. Published in the journal of Groups, Complexity, Cryptology