Complexity of Membership-Testing for finite abelian groups Consider the following abelian-subgroup membership-testing problem.


  Inputs:
  
  
  A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with arbitrary-large $d_i$.
  A generating-set $\lbrace h_1,\ldots,h_n\rbrace$ of a subgroup $H\subset G$.
  An element $b\in G$.
  
  
  Output: 'yes' if $b\in H$ and 'no' elsewhere'.


Question: Can this problem be solved efficiently in a classical computer? I consider an algorithm efficient if it uses $O(\text{polylog}|G|)$ time and memory resources in the usual sense of classical Turing machines. Notice that we can assume $n= O(\log|G|)$ for any subgroup $H$. The input-size of this problem is $\lceil \log|G|\rceil$.

A bit of motivation. Intuitively it looks like the problem can be tackled with algorithms to solve linear systems of congruences or linear diophantine equations (read below). However, it seems that there are different notions of computational efficiency used in the context of computations with integers, such as: strongly versus weakly polynomial time, algebraic versus bit complexity. I am not an expert on these definitions and I can not find a reference that clearly settles down this question.


  Update: the answer to the problem is "yes".
  
  
  In a late answer, I proposed a method based on Smith normal forms which is efficient for any group with the prescribed form.
  An answer by Blondin shows that in the particular case where all $d_i$ are of the form $d_i= N_i^{e_i}$ and $N_i, e_i$ are "tiny integers" then the problem belongs to $\text{NC}^3\subset \text{P}$. Tiny integers are exponentially small with the input size: $O(\log\log|A|)$.
  
  
  In my answer I used "orthogonal subgroups" to solve this problem, but I believe this is not necessary. I will try to provide a more direct answer in the future based a row Echelon forms method I am reading.




Some possible approaches

The problem is closely related to solving linear system of congruences and/or linear diophantine equations. I briefly summarise these connection for the sake of completion.

Take $A$ to be the matrix whose columns are the elements of the generating set  $\lbrace h_1, \ldots, h_n \rbrace$. The following system of equations

$$
Ax^{T}=
\begin{pmatrix}
h_1(1) &amp; h_2(1) &amp; \ldots &amp; h_n(1)\\
h_1(2) &amp; h_2(2) &amp; \ldots &amp; h_n(2)\\
\vdots &amp; \vdots &amp; \cdots &amp; \vdots\\
h_1(m) &amp; h_2(m) &amp; \ldots &amp; h_n(m)
\end{pmatrix}

\begin{pmatrix}
x(1)\\
x(2)\\
\vdots\\
x(n)
\end{pmatrix}
=
\begin{pmatrix}
b(1) \\
b(2) \\
\vdots\\
b(m)
\end{pmatrix}
\begin{matrix}
\mod d_1\\
\mod d_2\\
\vdots\\
\mod d_m
\end{matrix}
$$

has a solution if and only if $b\in H$.

If all cyclic factors have the same dimension $d=d_i$ there is an algorithm based on Smith normal forms that solves the problem in polynomial time. In this case, an efficient algorithm from  [1]  
finds the Smith normal form of  $A$: it returns a diagonal matrix $D$ and two invertible matrices $U$ and $V$ such that $D=UAV$. This reduced the problem to solving the equivalent system system $DY=Ub \mod d$ with $D$ diagonal. We can decide efficiently if the system has a solution using the Euclidean algorithm.

The above example suggest that the problem can be solved efficiently using similar techniques in the general case. We can try to solve the system doing modular operations, or by turning the system into a larger system of linear diophantine equations. Some possible techniques to approach the problem that I can think of are:


Computing the Smith normal forms of $A$.
Computing the row Echelon form of $A$.
Integer Gaussian elimination.
Verifying whether $b \in \langle h_1, \ldots, h_n\rangle$ (where $h_i$ are vectors according to the OP's comments) is equivalent to verifying whether there is a solution to this system:
$$
\begin{pmatrix}
h_{1}(1) &amp; \cdots &amp; h_{n}(1) &amp; d_1^{e_1}      &amp; 0 &amp; \cdots &amp; 0 \\\\
\vdots  &amp; \ddots &amp; \vdots  &amp; \vdots &amp; \vdots  &amp; \vdots &amp; \vdots  \\\\
h_{1}(m) &amp; \cdots &amp; h_{n}(m) &amp; 0      &amp; 0 &amp; \cdots &amp; d_m^{e_N}
\end{pmatrix}
\begin{pmatrix}
x(1) \\\\
\vdots \\\\
x(n) \\\\
y(1) \\\\
\vdots \\\\
y(m)
\end{pmatrix}
\equiv
\begin{pmatrix}
b(1) \\\\
\vdots \\\\
b(m)
\end{pmatrix}
$$

In your case $e_1, \ldots, e_N$ are tiny numbers (ie. their value is logartihmic in the input size). Unfortunately, it doesn't seem like we can assume that $d_1, \ldots, d_n$ are tiny.

If they are, then you can find a solution to the system in $\text{NC}^3$ from a result of McKenzie &amp; Cook [1]. This paper shows that solving linear congruences modulo an integer with tiny factors (LCON) is in $\text{NC}^3$. Moreover, this problem is $\text{NC}^1$-equivalent to the abelian permutation group membership problem (AGM). McKenzie's doctoral thesis is fully devoted to those problems [1]. More recently, those problems were considered by Arvind &amp; Vijayaraghavan [3].

[1] Pierre McKenzie &amp; Stephen A. Cook. The parallel complexity of Abelian permutation group problems. 1987.

[2] Pierre McKenzie. Parallel complexity and permutation groups. 1984.

[3] V. Arvind &amp; T. C. Vijayaraghavan. Classifying Problems on Linear Congruences and Abelian Permutation Groups Using Logspace Counting Classes. 2010.