Базисы GF(2^(2n)) специального вида

[maxal]

Пусть $g$ - произвольный примитивный элемент поля $GF(2^{2n})$. Рассмотрим базисы $GF(2^{2n})$ как линейного пространства над $GF(2)$ вида

$$\{ g^0, g^1, \dots, g^{n-1}, g^{k}, g^{k+1}, \dots, g^{k+n-1} \},$$

где $k$ - целое число.
Докажите, что количество таких базисов равно $2^{2n-1}.$ Опишите все подходящие значения $k$.

[maxal]

Видимо, пора дать подсказку:

Докажите, что число пар взаимно простых полиномов степени не превосходящей $d$ над полем GF(2) равно $2^{2d+1} - 1.$

[Kid Kool]

maxal, можете дать ссылку или на пальцах объяснить, что это за поле такое - GF(2)?

[Профессор Снэйп]

Kid Kool писал(а):

maxal, можете дать ссылку или на пальцах объяснить, что это за поле такое - GF(2)?

Насколько я понял, $GF(n)$ --- это конечное поле из $n$ элементов. Оно, как известно, существует в том и только в том случае, когда $n$ является степенью простого числа, и если оно существует, то единственно с точностью до изоморфизма.

[maxal]

GF - это стандартное обозначение для полей Галуа (Galois Field), то есть конечных полей. При этом количество элементов в таком поле обязано быть степенью простого числа.

Для случая простого $p$ (в частности, $p=2$) поле Галуа может быть представлено вычетами по модулю $p$:

$$GF(p) \cong \mathbb{Z}_p = \{ 0, 1, \dots, p-1 \}$$

со стандартными арифметическими операциями по модулю $p$.

Для нетривиальной степени простого числа простейшую реализацию поля Галуа $GF(p^n)$ можно получить как вычеты кольца полиномов над полем $\mathbb{Z}_p$ по модулю некоторого фиксированного (произвольного) неприводимого полинома степени $n$. То есть,

$$GF(p^n)\cong \mathbb{Z}_p[x] /\langle f(x) \rangle,$$

где $f(x)$ - неприводимый над $\mathbb{Z}_p$ полином степени $n$.

Вот тут чуть более подробно и с примерами.

[maxal]

Ну что ж, видимо, пора публиковать решение.
Мое решение тут: http://mersenneforum.org/showpost.php?p ... ostcount=6