2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Конечная группа
Сообщение05.11.2012, 23:29 
Есть группа Галуа $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}$?

 
 
 
 Re: Конечная группа
Сообщение05.11.2012, 23:35 
Аватара пользователя
vlad_light в сообщении #640535 писал(а):
олином $g(x)$ над нашей группой

Это как?

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

 
 
 
 Re: Конечная группа
Сообщение06.11.2012, 00:38 
$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}$ или вроде того.

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

 
 
 
 Re: Конечная группа
Сообщение06.11.2012, 01:06 
Ну, это понятно. Я имел ввиду, как найти в виде степени альфа (кроме перебора).
Тут такая задача: я пишу программу, которая умеет складывать и умножать элементы поля Галуа. Тогда каждый элемент поля имеет две (эквивалентные) записи:
$$\{\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 ^?$$Так вот как мне найти это "?", чтоб получить вторую запись?
Либо предложите свой вариант сложения, поскольку я в этом ничего не смыслю...

 
 
 
 Re: Конечная группа
Сообщение06.11.2012, 01:48 
Блин, таблицу логарифмов/антилогарифмов храните. Или можете составить таблицу логарифмов Якоби $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$ — Карацуба и БПФ.

 
 
 
 Re: Конечная группа
Сообщение06.11.2012, 02:18 
Спасибо!

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group