Задача состоит в следующем: дано поле Галуа и известны значения многочлена f(x) во всех элементах этого поля. Не известно только, для каких именно элементов поля вычислены известные значения. В поле n элементов, степень многочлена не больше log(n). Можно ли как-нибудь определить многочлен? Если есть хоть какие-нибудь идеи или если вы встречали похожую задачу напишите плз. Заранее спасибо!
mart Не очень понимаю условие.. Возьмем например Z_{7}, многочлены x, x+1, x-1 (и т.д.) дадут на нем одинаковые множества значений - само Z_{7}. Как их отличать друг от друга?
Stiver Наверное имеется в виду, что известны значения y1=f(x1),...,yn=f(xn), но неизвестно, для каких x1,...,xn они получены. Т.е. задача видимо такова: известны y1,...,yn, известен многочлен f(x), найти x1,...,xn.
2Stiver: Отличать их не надо, надо найти хотя бы один многочлен. Т.е. если множество значений есть все поле, как в вашем примере, то подходит абсолютно любой полином вида ax+b. 2crypto: Не совсем. Известны y1,..,yn - да. Но неизвестен полином f и неизвестен порядок x1,x2,..,xn, однако известно что x1,...,xn образуют поле целиком.
mart То есть нужно просто найти какой-то многочлен, дающий такое множество значений? Первое, что приходит в голову - построить его. Произвольно разнести y по x и вычислить стандартным образом коэффициенты по n точкам. Степень правда будет далеко не оптимальная, в худшем случае n-1. Если речь идет именно о вычислении такого порядка x_{i}, при котором полином будет иметь минимальную степень, то надо думать дальше. Можно попробовать превратить интерполяционное вычисление коэффициентов в задачу на (нелинейное) оптимирование, не уверен только, будет ли она эффективно решаемой. Это уже лучше обсуждать в каком-нибудь математическом сообществе.
Степень многочлена фиксирована. У меня вообще сложилось впечатление, что задача NP-полная, а это так херово=)
Похоже проблематика "Обратной задачи Галуа". Решение в нахождении коэф-в по теореме Виета. Берётся симметричный многочлен с неопределёнными коэф-ми. Находятся все его значения в группе при перестановке корней, после чего попытка найти неопределённые коэф-ы. А уж из полученных уравнений попытаться найти коэф-ы Виета и получить основной многочлен. ...В поле n элементов... - ну и замашки у вас. А вообще как сейчас развитие софта для символьной алгебры не знаю даже (relf на другом форуме для линукса вроде магму нашел), а так только Курош "Высшая алгебра" ...
mart Если фиксирована и неизвестна, то задача не имеет ни смысла, ни решения. Поэтому предполагаю, что степень известна. Тогда в немного более общей формулировке: дано векторное конечномерное пространство V над конечным полем. В V даны подпространство W и вектор a. Определить, можно ли с помощью перестановки компонентов (то есть последовательными отражениями на гиперплоскостях x_{i} = x_{j}) получить из a какой-то вектор b, лежащий в W. Быстрого решения (чтобы без факториалов) пока придумать не могу. Советую задать этот вопрос в математическом сообществе (например http://community.livejournal.com/ru_math/) и оставить здесь ссылку - интересная тема. А NP-полноту тоже еще доказать надо
Всем большое спасибо за помощь! Только сейчас после праздников наконец-то добрался до инета=) 2Relf: n = 1024, степень многочлена d = 50, например.
Можно попробовать так, например: Нетрудно видеть, что сумма SUM x^k, где x пробегает все ненулевые элементы поля порядка n, равна 0, если k не делится на n-1; и равна n-1 в противном случае. Предположим, что нам даны значения неизвестного многочлена фиксированной степени на ненулевых элементах поля (понятно, что значение на нулевом элементе, если таковой тоже присутствует, легко исключается простым перебором). Тогда, рассматривая суммы всех этих значений в фиксированной степени k и пользуясь вышеуказанным утверждением, можно получить систему алгебраических уравнений (соответствующих разным значениям k=1,2,3,...) относительно коэффициентов многочлена. Ну а дальше решать эту систему стандартными средствами (базисы Гребнера и т.п.)
Relf, спасибо огромное за предложенный способ! Жаль, что в общем случае решение системы алгебраических уравнений принадлежит классу NP. Но тем не менее сам способ очень интересный, надеюсь мне повезёт и задача решится за полиномиальное время Ещё раз спасибо!
