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

Я работаю над некоторым кодом Matlab для выполнения так называемой атаки индексного исчисления на данную криптосистему (это включает в себя вычисление дискретных значений журнала), и я все это сделал, за исключением одной маленькой вещи. Я не могу понять (в Matlab), как решить линейную систему сравнений по модулю 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 выше.


matlab cryptography linear-algebra symbolic-math mupad
person dkhaupt    schedule 01.12.2013    source источник
comment
Интересно, не могли бы вы получить дополнительную помощь (и быть более по теме) на обмен стеками вычислительной науки для такого рода вопросов?   -  person horchler    schedule 02.12.2013
comment
Конечно, спрошу и там, спасибо за подсказку! Любая конкретная причина, по которой я могу быть не по теме здесь?   -  person dkhaupt    schedule 02.12.2013
comment
Это сайт для программирования, поэтому демонстрация некоторого кода и ожидаемого результата всегда полезна. Например, код Matlab, который вы используете для примера 4 на 4, который вы показали в своей ссылке Math.StackExchange. Я не понимаю, что вы подразумеваете под linsolve неработающей (и даже какую из трех linsolve функций вы имеете в виду). Вы ожидаете более одного решения, но решатели вернуть только один? Есть ли какой-нибудь код C, который это реализует? – возможно, вы сможете создать функцию mex.   -  person horchler    schedule 02.12.2013
comment
Спасибо за ответ - извините, у меня не было кода заранее. Я добавил точную проблему, которую вижу. Если есть что-то еще, что я могу предоставить, дайте мне знать. Прошу прощения - я новичок в StackOverflow и StackExchange.   -  person dkhaupt    schedule 02.12.2013
comment
Я ужасно невежественен, но разве вы не можете вычислить приближенное решение линейной системы другими численными методами (например, nlinfit)?   -  person Landak    schedule 02.12.2013
comment
Не невежество - вы совершенно правы, исчерпывающий поиск для этой проблемы довольно прост. Однако, поскольку я должен эмулировать атаку на криптосистему, мне не разрешено использовать грубую силу! Разочаровывает то, что я могу выполнить это по мере необходимости, но меня не сбивает с толку алгоритм, а просто проблема с решением этой системы с помощью MATLAB. Я также изучал выполнение Maple в MATLAB, но кажется, что это идет только в другую сторону, несмотря на то, что Maple рекламирует двустороннюю связь.   -  person dkhaupt    schedule 02.12.2013
comment
@Landak: поскольку они эквивалентны линейным диофантовым уравнениям, bintprog может быть лучшим вариантом.   -  person horchler    schedule 02.12.2013

Ответы (1)


arrow_upward
3
arrow_downward

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

person horchler    schedule 02.12.2013
comment
Все это выглядит великолепно, особенно верхняя часть о преобразовании матриц в символические - большое спасибо! Я только что попытался воспроизвести его на своей машине, и я получаю сообщение об ошибке, что linsolve не поддерживает аргументы sym. Это новая функция? Я использую 7.11.0 (R2010b) - person dkhaupt; 02.12.2013
comment
Попробовав примеры со страницы справки sym/linsolve, я получаю ту же ошибку: неопределенная функция или метод linsolve для входных аргументов типа sym. так что я предполагаю, что sym/linsolve отсутствует в R2010b? - person dkhaupt; 02.12.2013
comment
Извините за поздний ответ. Математический набор инструментов Symbolic Math сильно изменился за прошедшие годы, поэтому вам, вероятно, не следует смотреть онлайн-документацию, которую выдает Google (хотя архивная документация для старых версий находится здесь). Вместо этого используйте функции doc и help. Даже если sym/linsolve не существует в R201b, я полагаю, что вы можете использовать версию sym/solve, показанную выше. Возможно, вам придется преобразовать матричное уравнение в четырехструнное уравнение — я не знаю. - person horchler; 04.12.2013
comment
Не беспокойтесь - спасибо за любой ответ! На самом деле я пытался использовать функцию решения, но у меня с ней проблемы. Я попросил помощи в решении другого вопроса здесь - person dkhaupt; 04.12.2013