Number of solutions for a system of linear equations over a finite ring Let $R$ be a finite ring with operations $(+,\cdot)$. Let $A \in R^{m\times n}$ and 
$b\in R^{m}$.

Questions: 


What is the complexity of counting the number of solutions to the system of equations $Ax = b$? Can it be done in polynomial time? 
More generally, let $R$ is a finite set and $(+,\cdot)$ be binary opeartions such that $(R,+)$ and $(R,\cdot)$ are (not necessarily commutative) semigroups. What is the complexity of counting the number of solutions to a system of linear equations $Ax=b$? 


Note that it is well known that the answer to Question 1 is affirmative if the the ring $R$ is a finite field.
The answer to (1) is yes (regardless of the properties D.W. asked for in the comments), depending on how $R$ is given: First, note that since $R$ is finite, the abelian group $(R,+)$ is of the form $\mathbb{Z}_{p_1^{k_1}} \oplus \dotsb \oplus \mathbb{Z}_{p_\ell^{k_\ell}}$, where $\ell \leq \log_2|R|$. Now, if $R$ is only given to you by generators and relations, even finding this decomposition is as hard as factoring (but given a factoring oracle, it can then be done easily). But if $R$ is fixed for all time (not part of the input), then this can be done as a once-and-for-all off-line precomputation, or if $R$ is part of the input, this can be done in $O(|R|)$ steps (even when given generators and relations).

So depending on your assumptions, the preceding step is either hard or easy. But let's suppose it's done. Now we'll use two viewpoints on the elements of $R$ to reduce to linear algebra over abelian groups.

Viewpoint 1: We may consider elements of $R$ as "vectors" with $\ell$ integer coordinates, where we consider the $i$-th coordinate modulo $p_i^{k_i}$. 

Viewpoint 2: This requires a little setup. Let $Hom(\mathbb{Z}_{p_j^{k_j}}, \mathbb{Z}_{p_i^{k_i}})$ denote the set of ring homomorphisms between these two rings. In particular, when $p_i \neq p_j$, this is zero; when $p_i = p_j$ if $k_i &lt; k_j$ then this involves taking element of $\mathbb{Z}_{p_j^{k_j}}$ modulo $p_i^{k_i}$, and possibly multiplying it by an element of $\mathbb{Z}_{p_i^{k_i}}$ (which we may represent by an integer, treated modulo $p_i^{k_i}$); if $k_i &gt; k_j$ it involves possibly multiplying by an element of $\mathbb{Z}_{p_j^{k_j}}$ (represented by an integer), and then applying the unique embedding of $\mathbb{Z}_{p_j^{k_j}}$ into $\mathbb{Z}_{p_i^{k_i}}$ (as the multiples of $p_i^{k_i-k_j}$, modulo $p_i^{k_i}$)

Now, consider the left multiplicative action of any $r \in R$ on $R$. Then we may associate to $r$ an $\ell \times \ell$ matrix, where the $(i,j)$ entry is an element of $Hom(\mathbb{Z}_{p_j^{k_j}}, \mathbb{Z}_{p_i^{k_i}})$, which can be represented by an integer, following the conventions above.

Now, replace each entry of $A$ by the associated $\ell \times \ell$ matrix as in viewpoint 2, replace each entry of $b$ by the associated vector as in viewpoint $1$, and replace each entry of $x$ with a vector of length $\ell$ (as in viewpoint 1).

Now the original problem has been reduced to linear algebra over abelian groups, which can be solved in polynomial time (see, e.g., Mikael Goldmann and Alexander Russell. The complexity of solving equations over finite groups. Inf. Comput., 178(1):253–262, 2002).