I'm working on some MATLAB code to perform something called the Index Calculus attack on a given cryptosystem (this involves calculating discrete log values), and I've gotten it all done except for one small thing. I cant figure out (in MATLAB) how to solve a linear system of congruences mod p, where p is not prime. Also, this system has more than 1 variable, so, unless I'm missing something, the Chinese remainder theorem wont work. I'm trying to solve the following system $\pmod 8$. The end goal is that I'm solving it mod each factor of 10930888, and then using the Chinese remainder theorem to construct each $L_i$ value:
$\begin{pmatrix} 0 & 5 & 4 & 1 \\ 1 & 7 & 0 & 2\\ 8 & 1 & 0 & 2\\ 10 & 5 & 1 &0 \end{pmatrix}$*$\begin{pmatrix} L_1\\L_2\\L_3\\L_4 \end{pmatrix}$=$\begin{pmatrix} 2946321 \\ 5851213 \\ 2563617\\10670279 \end{pmatrix}$ $\pmod{10930888}$
I asked a question on the mathematics stackexchange with more detail/formatted mathjax here. I solved the issue in my question at that link, and now I'm attempting to find a utility that will allow me to solve the system of congruences modulo a non-prime. I did find a suite that includes a solver supporting modular arithmetic, but the modulus must be prime (here). I also tried stepping through to modify it to work with non-primes, but whatever method is used doesn't work, because it requires all elements of the system have inverses modulo p.
I've looked into using the ability in MATLAB to call MuPAD functions, but from my testing, the MuPAD function linsolve (which seemed to be the best candidate) doesn't support non-prime modulus values either. Additionally, I've verified with Maple that this system is solvable modulo my integer of interest (8), so it can be done.
Any help would be greatly appreciated- I feel like I've run out of options here!
