Конечное поле. Поле Галуа.

[ScarfaseV]

Меня интересует вот какой вопрос.
Есть теорема о том, что количество элементов любого конечного поля есть его характеристика в степени натурального числа.
Допустим 2^3.
GF {0,1,2,3,4,5,6,7} так ведь получается?
Но характеристика поля это 1+1+1+1..+1 P раз =0; и тогда получается что характеристика равна 8.
Также при таком раскалде получается что в поле есть делители нуля (2*4) а их там не может быть.
Кто нибудь может мне объяснить?

[Xaositect]

$GF(2^3) \neq \mathbb{Z}/8\mathbb{Z}$!!!
Поле Галуа порядка $p^n$ строится как расширение простого поля $GF(p)$.
В случае $2^3$ можно взять неприводимый над $GF(2)$ многочлен $x^3 + x + 1$ и раcширить поле $GF(2)$ его корнем $\alpha$:
$GF(2^3) = \{0,1,\alpha,\alpha+1,\alpha^2,\alpha^2+1,\alpha^2+\alpha,\alpha^2+\alpha+1\}$, таблица умножения в нем выводится из соотношения $\alpha^3 + \alpha + 1 = 0$

[ScarfaseV]

А корень "a" может быть целым числом?
И существует ли какоенибудь правило нахождения неприводимых многочленов над полем? или есть какаято таблица?

[Sonic86]

ScarfaceV писал(а):

А корень "a" может быть целым числом?

Не может, ибо тогда у этого многочлена был бы корень в $\mathbb{Z}/2 \mathbb{Z}$ и он тогда был бы приводимым. Однако условия отсутствия корня из $\mathbb{Z}/2 \mathbb{Z}$ недостаточно для неприводимости.

ScarfaceV писал(а):

И существует ли какоенибудь правило нахождения неприводимых многочленов над полем? или есть какаято таблица?

Посмотрите книгу Лидл, Нидеррайтер Конечные поля - несложная книжка, там на этот вопрос есть ответы в общем виде. Такая таблица там тоже кажется есть.
Если Вам нужен небольшой неприводимый многочлен - можете его перебором найти.

[ScarfaseV]

А есть какойто определенный алгоритм построения поля? чтоб работал во всех случаях?
например мне нужно построить поле с числом элементов 2^n. Допустим n=3.
И тогда элементами поля будут
1) x (mod x^3+x+1) =x=2 (Т.е подставляем вместо x двойку).
2)x^2 (mod x^3+x+1) =x^2=4
3)x^3 (mod x^3+x+1) =x+1=3
4)x^4 (mod x^3+x+1) = x^2+x=6
5)x^5 (mod x^3+x+1) =x^2+x+1=7
6)x^6 (mod x^3+x+1) =x^2+1=5
7)x^7 (mod x^3+x+1) =1
Т.е возвожу x последовательно в степень, и привожу его по модулю неприводимого многочлена.
Можно ли так делать во всех случаях?
И в полях с расширением 2^n двойка всегда будет примитичвным элементом?

[Xaositect]

Любой элемент поля Галуа $\mathbb{F}_{p^n}$ будет иметь вид $\sum\limits_{k = 0}^n a_i x^i$, $a_i\in\mathbb{F}_p$. Умножение производится по модулю неприводимого полинома.


Еще небольшое замечание. Надо помнить, что те числа 1-7, которые у Вас написаны (результат подстановки $x=2$), вообще говоря, имеют мало отношения к целым числам 1-7, это скорее коды, полезные, например, в случае компьютерной реализации.

[ScarfaseV]

А Х будет всегда примитивным элементом? И можно ли всегда последовательно строить поля( искать его элементы) так как я предложил?
Мне какбы нужен алгоритм поиска этих элементов.

[VAL]

ScarfaseV в сообщении #257671 писал(а):

А Х будет всегда примитивным элементом? И можно ли всегда последовательно строить поля( искать его элементы) так как я предложил?
Мне какбы нужен алгоритм поиска этих элементов.

Для того, чтобы корень неприводимого полинома, с помощью которого задается поле, был примитивным элементом, необходимо и достаточно, чтобы этот неприводимый полином сам был примитивным, т.е. $e=p^n-1$ должно быть наименьшим показателем, при котором $x^e-1$ делится на этот полином.
О том как строить такие полиномы можно почитать в первом томе монографии Лидла и Нидеррайтера "Конечные поля".
Впрочем, если вы задаете поле с помощью неприводимого полинома, не являющегося примитивным, найти в нем примитивный элемент совсем не сложно. Достаточно возвести "подозреваемого" во все степени с показателями $\frac{p^n-1}{q_i}$, где $q_i$ пробегает все простые делители $p^n-1$. Учитывая, что бинарный алгоритм возведения в степень по модулю полинома над $\mathbb{Z}_i$ пишется очень просто и работает очень быстро, это не проблема. Чтобы элемент был примитивным, нужно чтобы при этих возведениях ни разу не получилась 1.

[Vitara]

Стоит задача построить поле GF(8)
Рещала я по такому принципу:
GF(8)={0,1,α,α+1,α2 , α2+1, α2+α, α2 +α+1}
Не приводимый многочлен х2 +х+1
Сложение элементов как обычно
1+ α=1+ α
…
α2 +α+1+ α2 +α=2 α2 +2 α+1=(первое и второе слагаемое =0 из-за коэфф 2)=1
и т.п.
Причем на диагонали стоят нули.
Умножение из соотношения α3 +α+1=0.
Например (α2 +α+1)*( α2 +α)=α4 + α3 + α3 + α2 + α2 + α = α (α3 + α +1)+ α2 =(скобка = 0)= α2 .
А если не получается сразу выделить скобку (α3 + α +1), то я ее прибавляла, так как она равна 0 и в некоторых случаях прибавляла α2 + α2 и группировала , далее уже упрощала чтобы ответ получился в виде элементов {0,1,α,α+1,α2 , α2+1, α2+α, α2 +α+1}. К тому элементы вида 2, 2 α , 2α2 равны 0.
Я правильно делаю?=))
И еще вопрос, почему α3 +α+1=0 =? И почему именно 2, 2 α , 2α2 равны 0? (так как у нас Z2 ={0,1} ?)

[Vitara]

Стоит задача построить поле GF(8)
Рещала я по такому принципу:
GF(8)={0,1,α,α+1,α2 , α2+1, α2+α, α2 +α+1}
Не приводимый многочлен х2 +х+1
Сложение элементов как обычно
1+ α=1+ α
…
α2 +α+1+ α2 +α=2 α2 +2 α+1=(первое и второе слагаемое =0 из-за коэфф 2)=1
и т.п.
Причем на диагонали стоят нули.
Умножение из соотношения α3 +α+1=0.
Например (α2 +α+1)*( α2 +α)=α4 + α3 + α3 + α2 + α2 + α = α (α3 + α +1)+ α2 =(скобка = 0)= α2 .
А если не получается сразу выделить скобку (α3 + α +1), то я ее прибавляла, так как она равна 0 и в некоторых случаях прибавляла α2 + α2 и группировала , далее уже упрощала чтобы ответ получился в виде элементов {0,1,α,α+1,α2 , α2+1, α2+α, α2 +α+1}. К тому элементы вида 2, 2 α , 2α2 равны 0.
Я правильно делаю?=))
И еще вопрос, почему α3 +α+1=0 =? И почему именно 2, 2 α , 2α2 равны 0? (так как у нас Z2 ={0,1} ?)

[Xaositect]

Vitara в сообщении #258542 писал(а):

Я правильно делаю?=))

В общем да.

Vitara в сообщении #258542 писал(а):

Не приводимый многочлен х2 +х+1

Вам надо построить $GF(2^3)$, поэтому полином должен быть 3-ей степени.

Vitara в сообщении #258543 писал(а):

И еще вопрос, почему α3 +α+1=0 =?

Потому что используется неприводимый многочлен $x^3 + x + 1$, мы расширяем поле $\mathbb{F}_2$ его корнем $\alpha$.

Vitara в сообщении #258543 писал(а):

И почему именно 2, 2 α , 2α2 равны 0? (так как у нас Z2 ={0,1}

Да, именно поэтому. В $\mathbb{F}_2$ $2=0$.