我正在编写一些Matlab代码，对给定的密码系统进行索引演算攻击（这涉及计算离散的对数值），除了一件小事，我已经完成了所有这些。我不知道（在Matlab中）如何求解线性同余系统mod p，其中p是而不是素数。此外，这个系统有不止一个变量，所以，除非我遗漏了什么，否则中国余数定理是行不通的。
我问了一个关于数学堆栈交换的问题，这里有更详细/格式化的mathjax。我在这个环节上解决了我的问题，现在我正试图找到一个实用程序，让我能够解决模非素数的同余系统。我确实找到了一个套件，其中包括一个支持模运算的求解器，但模必须是素数（此处）。我也尝试过逐步修改它以使用非素数，但无论使用什么方法都不起作用，因为它要求系统的所有元素都有模p的逆。
我已经研究过在Matlab中使用调用MuPAD函数的能力，但从我的测试来看，MuPAD功能linsolve（似乎是最好的候选者）也不支持非素数模值。此外，我已经用Maple验证了这个系统是可以模我感兴趣的整数（8）求解的，所以它是可以实现的。
更具体地说，这正是我试图在MuPAD:中运行的命令
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]
如果我将域更改为IntegerMod（23）和IntegerMod（59407），则相同的命令将返回正确的值，因此我认为8不合适，因为它不是素数。以下是我尝试上述命令时的输出，每个23和59407都是我的域：
[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]
这些答案是正确的——x、y、z和q对应于位于我上面的Math.StackExchange链接上的同余系统中的L1、L2、L3和L4。
我想知道您以前是否尝试过使用sym/linsolve和sym/solve，但可能传入了数字值而不是符号值。例如，这返回了关于您正在寻找的内容的无稽之谈：
A = [0 5 4 1;1 7 0 2;8 1 0 2;10 5 1 0];
b = [2946321;5851213;2563617;10670279];
s = mod(linsolve(A,b),8)
但是，如果将数值转换为符号整数，sym/linsolve将以有理分数表示。然后
s = mod(linsolve(sym(A),sym(b)),8)
返回预期答案
s =
6
1
6
4
这只是使用符号数学来解决系统线性系统，就好像它是一个正规矩阵一样。对于大型系统来说，这可能很昂贵，但我认为这只不过是使用MuPAD的numeric::linsolve或linalg::matlinsolve。sym/mod应返回每个溶液组分分子的模数。我相信，如果模和分母不是互质的，你会得到一个误差。
sym/solve也可以用类似的方式来解决这个问题：
L = sym('L',[4,1]);
[L1,L2,L3,L4] = solve(A*L==b);
s = mod([L1;L2;L3;L4],8)
使用sym/solve或sym/linsolve的一个可能问题是，如果线性同余问题（与线性系统相反）有多个解，则这种方法可能不会返回所有解。
最后，使用MuPAD函数numlib:：ichrem（中国整数余数定理），这里有一些代码试图获得完整的解决方案：
A = [0 5 4 1;1 7 0 2;8 1 0 2;10 5 1 0];
b = [2946321;5851213;2563617;10670279];
m = 10930888;
mf = str2num(strrep(char(factor(sym(m))),'*',' '));
A = sym(A);
b = sym(b);
s = sym(zeros(length(b),length(mf)));
for i = 1:length(mf)
s(:,i) = mod(linsolve(A,b),mf(i));
end
mstr = ['[' sprintf('%d,',mf)];
mstr(end) = ']';
r = sym(zeros(length(b),1));
for i = 1:length(b)
sstr = char(s(i,:));
r(i) = feval(symengine,'numlib::ichrem',sstr(9:end-2),mstr);
end
check = isequal(mod(A*r,m),b)
我不确定这是否是你想要的，但希望它能有所帮助。我认为，向MathWorks提交增强/服务请求可能是个好主意，这样MuPAD和其他求解器将来可以更好地处理系统。