Доброго времени суток! Не знает ли случайно кто-нибудь методов решения систем модулярных уравнений второго, третьего и выше порядков? В двух словах, конструкция типа: x^k=a1 mod C x^l=a2 mod C x^m=a3 mod C ...etc Переменная (x) и модуль (С) - одни и те же во всех уравнениях, степени и результаты - разные Спасибо!
Пардон, я не совсем понял, что требуется найти Похоже, между прочим, на проблему дискретного логарифма
Интересует вообще, существуют ли методы решения таких систем? Решение системы линейных уравнений (с несколькими неизвестными) по модулю - возможно и достаточно тривиально (при условии наличия необходимого числа уравнений, не меньше числа неизвестных, как для любой системы). Причем, как для общего для всех уравнений модуля, так и для различных модулей для каждого. Но там линейные уравнения, а в данном случае - нет
Приведу решение - громоздко - но может увидишь направление в котором надо двигаться... Хм... существует метод решения сравнений x^n=a(mod p) где p простое (для произвольного модуля - свести к системе сравнений по простым делителям модуля - потом эту систему надо свернуть в одну по Китайской Теореме об Остатках) Идея в следующем x^n=a(mod p) <=> n*log(x)=log(a)(mod p-1) второе - линейное, потом y=log(x) - находишь x Логарифмируешь по первообразному корню для данного модуля, скажем алгоритмом "больших и малых шагов" (baby step - giant step) осталось разобраться с системой x^l=a mod C ... x^r=b mod C каждое решаешь - получишь x={x11, ... x1N} mod C .... x={xM1, ... xMK} mod C ну тут надо выбрать х который удовлетворит всем системам --------------------------------------------------- возможно можно использовать факт что все уравнения по одному модулю - хз, надо подумать...
Да кстати, если степень вторая то можно не изврашаться через дискретные логарифмы, но это так к слову... Все что больше двух уже гадко...
ECk Можно записать в виде x^{k+l+m...} = a<sub>1</sub>*a<sub>2</sub>*a<sub>3</sub>*... mod C найти все решения x(логарифмирование) и простой подстановкой в исходную систему выбрать из них правильные. volodya Она и есть
Всем спасибо за ответы! В общем случае, это не совсем проблема дискретного логарифма (скорее это попытка решить таким образом проблему поиска идемпонент группы С)
Во-первых, надо вычислить d=НОД(k,l,m,...) который как известно представляется в виде линейной комбинации d = u*k + v*l + w*m + ... которая соответствует сравнению x^d = a1^u * a2^v * a3^m * ... (mod C) причем это сравнение равносильно исходной системе. Если повезет и d=1, то вот оно - решение. Если нет - то придется логарифмировать.
