I'm interested in either techniques or computational hardness results around enumerating solutions to a system of (not necessarily homogeneous) linear equations over the ring $\mathbb{Z}/n\mathbb{Z}$. (Of course, when $n$ is prime, this ring is a field, and we can do this with standard linear algebra techniques.)
One thing that I have noticed, is that you can get a lower bound for the number of solutions by quotienting with a maximal ideal to get a field, and use linear algebraic techniques.
I mostly care about large-ish systems of equations (dozens of equations and hundreds of variables), but to be concrete, here's a small example I care about over $\mathbb Z/6\mathbb Z$: $$ \begin{alignat}{6} 3x_1 && && &&+ 2x_4 &+ x_5 &= 0 \\ 2x_1 && &&+ 3x_3 && &+ x_5 &= 1 \\ && 2x_2 && && &+ x_5 &= 0 \\ && && && x_4 & &= 1 \\ \end{alignat} $$
Of course, we could mod out by the ideals $\langle 2 \rangle$ and $\langle 3 \rangle$ respectively and solve the following linear systems over $\mathbb F_2$ and $\mathbb F_3$, the fields of two and three elements: $$ \begin{bmatrix} 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \end{bmatrix} $$ $$ \begin{bmatrix} 0 & 0 & 0 & 2 & 1 \\ 2 & 0 & 0 & 0 & 1 \\ 0 & 2 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \\ y_5 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \end{bmatrix} $$
Is there a better-than-brute-force algorithm for finding the other solutions? Or is there a proof or heuristic for why finding these other solutions might be computationally hard?
For $n$ square free, once you solve the system mod the various prime factors of $n,$ the total number of solution mod $n$ is just the product of the numbers for the prime factors (by chinese remainder theorem). This leaves the case when $n$ is not square free. Then you replace the prime divisors by the maximal prime power divisors, and therein lies the crux of the matter. Notice that a solution modulo $p^2$ (say) must reduce to a solution mod $p$ so you now do Hensel lifting to get solution mod $p^2.$ (higher powers are similar).