Конечная группа

[vlad_light]

Есть группа Галуа $GF(2^m)$ и примитивный полином $g(x)$ нашего поля. Тогда элементами группы будут $\{0,\alpha ^0,\alpha ^1,...,\alpha ^{2^m-2}\}$. Далее рассмотрим отображение

$$A:GF(2^m)\to \{0,1\}^m$$

где каждый элемент группы представляется в виде вектора, который состоит из коэффициентов многочлена

$$\alpha ^i\mathrm {mod}g(\alpha), i=\overline {0,2^m-2}$$

, а нулевой элемент отображается в $0$-вектор. Какой вид имеет оператор $A^{-1}$?

[xmaister]

vlad_light в сообщении #640535 писал(а):

олином $g(x)$ над нашей группой

Это как?

[vlad_light]

Понятия не имею Я в этой алгебре не сильно. Вообщем, $g(\alpha )=0, deg(g)=m, \alpha $ - примитивный элемент поля. Надеюсь, Вы поняли, что я имел ввиду:)

[Joker_vD]

$A^{-1}\colon \{0,1\}^m\to GF(2^m)$, $A^{-1}(a_0,a_1,\dots,a_{m-1})=a_0x^{m-1}+a_1x^{m-2}+\dots+a_{m-1}$ или вроде того.

И это, поле, поле Галуа. Группа Галуа — совсем другая вещь.

[vlad_light]

Ну, это понятно. Я имел ввиду, как найти в виде степени альфа (кроме перебора).
Тут такая задача: я пишу программу, которая умеет складывать и умножать элементы поля Галуа. Тогда каждый элемент поля имеет две (эквивалентные) записи:

$$\{\alpha ^0, \alpha ^1,..., \alpha ^{2^m-2}\}\ni x\leftrightarrow (x_1,x_2,...,x_m)\in \{0,1\}^m$$

Тогда $\forall a,b\in GF(2^m): a\leftrightarrow (a_1,...,a_m)\leftrightarrow \alpha ^a; b\leftrightarrow (b_1,...,b_m)\leftrightarrow \alpha ^b$ и

$$a\cdot b=\alpha ^a\cdot \alpha ^b=\alpha ^{a+b}=\alpha ^{(a+b)\mathrm{mod}2^m-1}\leftrightarrow \Phi(\alpha ^{(a+b)\mathrm{mod}2^m-1} \mathrm{mod}g(\alpha ))$$

где $\Phi : \mathbb P_{n-1}\to \{0,1\}^n; \sum\limits _{k=0}^{n-1}a_kx^k\mapsto (a_0,a_1,...,a_{n-1})$. Тут всё понятно: делим, получаем полином, выделяем коэффициенты, заносим их в массив и получаем новый элемент с известными нам обеими записями. Дальше рассмотрим сложение:

$$a+b=(a_1,...,a_m)+(b_1,...,b_m)=(a_1+b_1,...,a_m+b_m)\leftrightarrow \alpha ^?$$

Так вот как мне найти это "?", чтоб получить вторую запись?
Либо предложите свой вариант сложения, поскольку я в этом ничего не смыслю...

[Joker_vD]

Блин, таблицу логарифмов/антилогарифмов храните. Или можете составить таблицу логарифмов Якоби $L(n)$: этот логарифм $L(n)$ определяется равенством $\alpha^{L(n)}=1+\alpha^n$ (случай $\alpha^n=-1$ отбрасывается). Тогда $\alpha^m+\alpha^n=\alpha^{m+L(n-m)}$.

-- Вт ноя 06, 2012 03:14:37 --

Вот не знаю, оптимально ли это, но NTL хранит элементы $GF(2^m)$ как многочлены над $\mathbb Z_2$, при сложении просто покомпонентно складывает (практически XOR), а умножение... честно перемножает, а потом находит остаток. Благо, для $GF(2^m)$ все сводится к сдвигам и XOR'ам. В случае же произвольного $p$ — Карацуба и БПФ.

[vlad_light]

Спасибо!