|
RAMM
|
|
QWERTY
|
|
|
|
|
|
|
Рег.: 28.03.2004
|
|
Сообщений: 1437
|
|
|
|
Рейтинг: 4
|
|
Помогите с алгоритмом.
27.04.2005 18:59
|
|
|
Есть кольцо - (Z/(2^m)Z)[X]/(X^n-1),
т.е. кольцо многочленов степени < n и c коэффициентами из Z/(2^m)Z, где m и n- натуральные.
Нужен алгоритм нахождения обратного элемента в этом кольце, который можно легко реализовать на комп-е.
Может кто-нибудь знает? Помогите, плиз.
|
Что посмеешь, то и пожмешь. |
|
|
vdremov
|
|
лесочный т-кеон
|
|
|
|
|
|
|
Рег.: 12.10.2003
|
|
Сообщений: 1184
|
|
Из: Москва
|
|
Рейтинг: 18
|
|
Re: Помогите с алгоритмом.
[re: RAMM]
28.04.2005 00:01
|
|
|
Ну во-первых, в этом кольце далеко не всякий элемент обратим.
А по существу так:
Правильно сначала обратить элемент p(X) над Z/2Z
Пока метода лучше, чем стандартный метод Гаусса, не придумалось. Ну зато он - прост и легок в реализации (хоть и дает сложность Cn^3). Записываешь искомый многочлен y(X) с неопределенными коэффициэнтами и решаешь систему n на n
py=1(mod 2), все время оставляя в качестве чисел только "0 и 1". Тут наверно удобнее не сложение, а соответствующие логические операции типа xor
получили какой-то элемент y, приближение к p^{-1}
посчитаем py=1+2u
получили u из (Z/2^{m-1}Z)[X]
далее p^{-1}=y(1+2u)^{-1}
а (1+2u)^{-1} уже находится довольно просто с помощью разложения ряда в произведение:
(1-2u)(1+2^2u^2)(1+2^4u^4)(1+2^8u^8)...
На этом этапе сложность где-то порядка n^2 ln^3 m (ну да не суть)
Детали реализации наверно сам додумаешь, если собираешься программу писать.
|
В математических  . Наверно мне там проще.
|
|
|
|
Список
Плоский
Дерево
