Как построить поле: 1- F(q) , q=2^3 ?

Подскажите пожалуйста как построить такие поля:
1- F(q) , q=2^3.
2- F(q), q=3^2

В общем я понимаю это. Но как будут выглядеть эти факторкольца и как и строить, вот в этом вопрос...

Поле - это не только /ценный мех/ набор элементов, но и операции!

Прежде всего, как уже написал Echo-off, нужно подобрать неприводимый многочлен нужной степени. Конечно, тем самым имеем алгоритмы сложения и умножения: складывать и умножать многочлены обычным образом, а потом находить остатки от деления на выбранный неприводимый многочлен. Но для некоторых практических нужд такое умножение слишком долгое.

Чтобы по-настоящему разобраться с операцией умножения в конечном поле, желательно найти порождающий элемент мультипликативной группы поля, т. е. такой элемент a, степени которого будут совпадать со всеми ненулевыми элементами поля. Часто порождающим элементом является x. Когда удастся угадать a, нужно по порядку посчитать все его степени. Тем самым для каждого f из поля найдём такое d, что a^d=f. Иногда говорят, что d - дискретный логарифм элемента f. Когда построили таблицу дискретных логарифмов, умножать элементы становится легко и приятно.

А ещё можно для каждого элемента f из поля (кроме f=-1) найти такую степень k, что f+1=a^k. Тогда можно забыть о полиномиальном представлении элементов и легко складывать их с помощью таблицы этих чисел k.

Вот подробно для F(2^2).

1. Выбор неприводимого многочлена.
Над полем F(2) находим неприводимый многочлен степени 2.
В данном случае такой многочлен только один: x^2+x+1.

2. Искомое поле F(2^2) есть фактор-кольцо F(2)[x]/(x^2+x+1).
Таким образом, элементы F(2^2) можно представлять как многочлены
с коэффициентами из F(2) степени не выше 2:
0, 1, x, x+1.
Складывать как обычные многочлены с коэффициентами из F(2).
Пример сложения: 1+(x+1)=x.
При умножении результат делить с остатком на x^2+x+1.
Другими словами, полагать x^2=-x-1.
А поскольку -1=1 в поле F(2), можно полагать x^2=x+1.
Пример умножения: (x+1) * (x+1) = x^2 + x+x + 1 = (x+1) + 0 + 1 = x.

3. Выбор порождающего элемента g и построение таблицы логарифмов.
Нужно выбрать в F(2^2) элемент g, степени которого будут совпадать со всеми ненулевыми элементами (1, x, x+1).
Попробуем g=x (обычно подходит).
x^0 = 1,
x^1 = x,
x^2 = x+1.
Подошёл! Дальше получится x^3=1, так как порядок мультипликативной группы поля F(2^2) равен 4-1=3.

Заодно построили таблицу дискретных логарифмов (по основанию g):
f k: f=g^k
0 - (не существует)
1 0
x 1
x+1 2
Конечно, в более сложных примерах числа во втором столбце не обязаны возрастать.

Таблица логарифмов позволяет мгновенно умножать элементы:
x * (x+1) = g^1 * g^2 = g^3 = 1,
(x+1) * (x+1) = g^2 * g^2 = g^4 = g^1 = x.

Дальше можно для каждого элемента f найти такое число v, что f+1=g^v,
но об этом думать рано, если непонятны предыдущие этапы.

Построение поля F(2^4).

1. Выбор неприводимого многочлена степени 4.
Приводимые (разложимые) многочлены степени 4
делятся либо на многочлены первой степени,
либо на неприводимый многочлен второй степени x^2+x+1.
Значит, нужно исключить:
1) многочлены, которые делятся на x,
т. е. многочлены с нулевым свободным членом;
2) многочлены, которые делятся на x+1,
т. е. многочлены с чётным числом единичных коэффициентов,
3) многочлен (x^2+x+1)(x^2+x+1)=x^4+x^2+1.
Из оставшихся многочленов выберем x^4+x+1.

2. Будем строить F(2^4) как F(2)[x]/(x^4+x+1).
Таким образом, всюду считаем, что x^4=-x-1.
Поскольку коэффициенты в поле F(2), то x^4=x+1.

3. Найдём порождающий элемент мультипликативной группы.
Попробуем на эту роль многочлен x.
x^0 = 1
x^1 = x,
x^2 = x^2 (не упрощается),
x^3 = x^3 (не упрощается),
x^4 = x+1,
x^5 = x(x+1) = x^2+x,
x^6 = x(x^2+x) = x^3+x^2,
x^7 = x(x^3+x^2) = x^4+x^3 = x^3+x+1,
x^8 = x(x^3+x+1) = x^4+x^2+x = (x+1)+(x^2+x) = x^2+1,
x^9 = x(x^2+1) = x^3+x,
x^(10) = x(x^3+x) = x^4+x^2 = x^2+x+1,
x^(11) = x(x^2+x+1) = x^3+x^2+x,
x^(12) = x(x^3+x^2+x) = x^4+x^3+x^2 = x^3+x^2+x+1,
x^(13) = x(x^3+x^2+x+1) = x^4+x^3+x^2+x = x+1+x^3+x^2+x = x^3+x^2+1,
x^(14) = x(x^3+x^2+1) = x^4+x^3+x = x+1+x^3+x = x^3+1.
Получили все ненулевые элементы поля.
Значит, g=x - порождающий элемент.
Порядок мульт. группы поля равен 15, поэтому g^(15)=1.
Проверка: g^(15) = x^(15) = x(x^3+1) = x^4+x = x+1+x = 1.

Предыдущие вычисления дают таблицу логарифмов:
f <-> log_g(f)
0 <-> - (не существует)
1 <-> 0
x <-> 1
x+1 <-> 4
x^2 <-> 2
x^2+1 <-> 8
x^2+x <-> 5
x^2+x+1 <-> 10
x^3 <-> 3
x^3+1 <-> 14
x^3+x <-> 9
x^3+x+1 <-> 7
x^3+x^2 <-> 6
x^3+x^2+1 <-> 13
x^3+x^2+x <-> 11
x^3+x^2+x+1 <-> 12

С помощью таблицы логарифмов теперь легко умножать элементы.
Пример: (x^3+x)(x^3+x^2+x) = g^9 * g^11 = g^(20) = g^5 = x^2+x.

может быть, Вы понимаете, как эта теория используется в теории кодирования? например, мне надо построить линейный сдвиговый регистр с обратной связью lfsr. И там фигурирует эта теория.

здесь про конечные поля написано исчерпывающе подробно, и есть все нужные формулы.
Ищите да обрящете!

Спасибо * n, где n стремится к бесконечности. =)