0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

You can solve the four equations in four unknowns ignoring the modulus. If any intermediate steps result in a number greater than the modulus, you can reduce by it or not as you wish. That will get you to four equations of the form $a_iL_i=b_i \pmod {10930888}$ Now they will be soluable or not, depending on whether $a_i$ is coprime to $10930888$ If it is coprime, there will be a unique solution. If not, there will be none or $\gcd (a_i,10930888)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.