3

我正在编写一些 Matlab 代码来对给定的密码系统执行称为索引演算攻击的东西（这涉及计算离散的对数值），除了一件小事之外，我已经完成了所有工作。我不知道（在 Matlab 中）如何解决同余 mod p 的线性系统，其中 p不是素数。另外，这个系统有不止一个变量，所以，除非我遗漏了什么，否则中国剩余定理是行不通的。

我在这里问了一个关于数学 stackexchange 的问题，其中包含更多详细信息/格式化的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对应于L1, L2, L3, 并且L4在位于我上面的 Math.StackExchange 链接的同余系统中。

4

1 回答 1

3

我想知道您是否尝试过使用sym/linsolveandsym/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

这只是使用符号数学解决系统线性系统，就好像它是一个普通矩阵一样。对于大型系统，这可能会很昂贵，但我想最多只能使用 MuPADnumeric::linsolve或linalg::matlinsolve. sym/mod应该返回每个解分量的分子的模数。我相信如果模数和分母至少不是coprime ，你会得到一个错误。

sym/solve也可以用类似的方式解决这个问题：

L = sym('L',[4,1]);
[L1,L2,L3,L4] = solve(A*L==b);
s = mod([L1;L2;L3;L4],8)

使用sym/solveor的一个可能问题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 和其他求解器可以在未来更好地处理系统。

于 2013-12-02T01:43:28.170 回答