Matlab: решатель линейных конгруэнций, который поддерживает непростой модуль?

Question

Я работаю над некоторым кодом 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 соответствовать L1, L2, L3, а также L4 в системе сравнений, расположенной по моей ссылке Math.StackExchange выше.

Answer 1

Мне интересно, если вы пытались использовать 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 и другие решатели могли лучше обрабатывать системы в будущем.