Check membership in a matrix group

I'm looking for a (preferably somewhat efficient) algorithm for this problem:

Given a normal subgroup of $SL(m, \mathbb{Z})$ generated by a finite set $\{M_1, M_2, \dotsc, M_n\}$, and some $A \in SL(m, \mathbb{Z})$, is $A$ in the normal subgroup? That is, is $A$ a product of elements of the generating set?

For the application I'm looking at, an existence algorithm would be fine; I don't actually need to know what product produces $A$.

Edit: The original phrasing implied commutativity, which is silly and wrong.

Update 2: @studiosus' answer looks good to me, but if there exists an efficient-enough-to-use algorithm, I'd rather award the bounty there.

There is one key ingredient that makes your problem algorithmically solvable:

Theorem. 1. Every normal subgroup of $\Gamma=SL(d,Z)$, $d\ge 3$, is either central or has finite index in $\Gamma$. 2. Every finitely generated normal subgroup of $\Gamma=SL(2,Z)$, is either central or has finite index in $\Gamma$.

Part 1 is due to Margulis and is very deep, part 2 was probably known to Poincare and is not deep. (I can find references if you like.)

I will leave you to work out an algorithm covering the central case (it is easy) and consider the "generic" situation.

You run in parallel two Turing Machines:

T1 simply enumerates reduced words in the alphabet $M_i^{\pm 1}, i=1,...,n$ according to their length and checks if the corresponding product of matrices equals $A$.

T2 enumerates maps from elementary matrices (generators of $\Gamma$) to permutation groups $S_k$ (for each $k=2, 3, ...$) and checks if they define a homomorphism $f$ that sends matrices $M_i$ to the identity permutation. At the same time, it checks if $f(A)=1$.

Eventually, one of these Turing machines stops and conforms that either $A$ is the product of matrices $M$ (that is if T1 wins) or that $A$ is not in the subgroup generated by $M_i$'s (if T2 wins). If $d\ge 3$ then T2 can be replaced by the following:

T3: Enumerate finite groups $SL(d, Z/k)$ where $k$'s are natural numbers. For each $k$ compute reductions of $A$ and $M_i$'s modulo $k$ and check if the reduction of $A$ is a product of reductions of $M_i$'s. If $A$ is not in the subgroup generated by $M_i$'s then T3 will eventually find $k$ such that the same is true mod $k$. (Validity of this algorithm depends on the Congruence Subgroup Property that $SL(d, Z)$ has if and only if $d\ge 3$.)

All these algorithms are terribly inefficient, but I am not a programmer.