Databases
StackOverflow2013
Postsdbo
POMatlab: linear congruence solver that supports a non-prime modulus?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMatlab: linear congruence solver that supports a non-prime modulus?
    primarykey
    data
    text
    <p>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 <em>not</em> prime. Also, this system has more than one variable, so, unless I'm missing something, the Chinese remainder theorem wont work. </p> <p>I asked a question on the mathematics stackexchange with more detail/formatted mathjax <a href="https://math.stackexchange.com/questions/585609/having-trouble-using-the-chinese-remainder-theorem-to-solve-a-system-of-congruen">here</a>. 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 (<a href="http://www.mathworks.com/matlabcentral/fileexchange/22725-variable-precision-integer-arithmetic" rel="nofollow noreferrer">here</a>). 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.</p> <p>I've looked into using the ability in Matlab to call MuPAD functions, but from my testing, the MuPAD function <code>linsolve</code> (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.</p> <p>To be more specific, this is the exact command I'm trying to run in MuPAD: </p> <pre><code>linsolve([0*x + 5*y + 4*z + q = 2946321, x + 7*y + 2*q = 5851213, 8*x + y + 2*q = 2563617, 10*x + 5*y + z = 10670279],[x,y,z,q], Domain = Dom::IntegerMod(8)) Error: expecting 'Domain=R', where R is a domain of category 'Cat::Field' [linsolve] </code></pre> <p>The same command returns correct values if I change the domain to IntegerMod(23) and IntegerMod(59407), so I believe 8 is unsuitable because it's not prime. Here is the output when I try the above command with each 23 and 59407 as my domain: </p> <pre><code>[x = 1 mod 23, y = 1 mod 23, z = 12 mod 23, q = 14 mod 23] [x = 14087 mod 59407, y = 1 mod 59407, z = 14365 mod 59407, q = 37320 mod 59407] </code></pre> <p>These answers are correct- <code>x</code>, <code>y</code>, <code>z</code>, and <code>q</code> correspond to <code>L1</code>, <code>L2</code>, <code>L3</code>, and <code>L4</code> in the system of congruences located at my Math.StackExchange link above.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USdkhaupt
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POMatlab: linear congruence solver that supports a non-prime modulus?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POMatlab: linear congruence solver that supports a non-prime modulus?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POMatlab: linear congruence solver that supports a non-prime modulus?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI wonder if you might get more help (and be more on-topic) at [Computational Science Stack Exchange](http://scicomp.stackexchange.com) for this sort of question?
      singulars
      1. POMatlab: linear congruence solver that supports a non-prime modulus?
      1. UShorchler
    2. COSure, I'll ask there as well, thanks for the tip! Any particular reason why I may be off-topic here?
      singulars
      1. POMatlab: linear congruence solver that supports a non-prime modulus?
      1. USdkhaupt
    3. COThis is a programing site so showing some code and the expected output is always helpful. For example, the Matlab code you're using for the 4-by-4 example that you showed in your Math.StackExchange link. I'm not clear on what you mean by `linsolve` not working (and even which of the three `linsolve` functions you mean). Is it that you expect more than one solution, but the solvers are [returning just one](http://mathematica.stackexchange.com/questions/31696/solving-a-system-of-linear-equations-modulo-n)? Is there any C code that implements this? – you might be able to create a mex function.
      singulars
      1. POMatlab: linear congruence solver that supports a non-prime modulus?
      1. UShorchler
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload