рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

СТРУКТУРА КОНЕЧНОГО ПОЛЯ

СТРУКТУРА КОНЕЧНОГО ПОЛЯ - Домашнее Задание, раздел Домостроительство, Лекции и домашнии задания по курсу токбдискретная математика введение в дискретную алгебру Ранее В Данной Главе Мы Изучали, Как Строить Поле. Предполагая, Что Можно Най...

Ранее в данной главе мы изучали, как строить поле. Предполагая, что можно найти простой многочлен степени п над полем άGF (q), мы научились строить конечное поле с qп элементами.

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

В процессе работы над материалом данного параграфа мы углубим наше понимание структуры конечных полей. Структурные свойства будут полезны во многих приложениях. Мы докажем также, что для всех полей Галуа существуют простые многочлены всех степеней.

Определение 2.6.1. Число элементов наименьшего подполя поля GF(q) называется характеристикой поля GF(q).

 

Теорема 2.6.2. Каждое поле Галуа содержит единственное наименьшее подполе, число элементов которого равно простому числу. Следовательно, характеристика каждого поля Галуа является простым числом.

Доказательство. Поле содержит элементы 0 и 1. Для задания подполя рассмотрим подмножество G = {О, 1, 1 + 1, 1 + 1 + 1, ), обозначая его элементы через {О, 1, 2, 3, ...}. Это подмножество является циклической группой по сложению, которая должна содержать конечное число р элементов. Мы покажем, что р — простое число и что G = GF (р). Сложение в G, является сложением по модулю р, так как G образует циклическую группу по сложению. В силу закона дистрибутивности умножение также должно быть умножением по модулю р, ибо

άр = (1 + ••• + 1)∙р = р +....+ р,

где элемент p суммируется ά раз и суммирование ведется по мо­дулю р. Следовательно, умножение также является умножением по модулю р. По умножению каждый элемент обратим, так как последовательность {p, p2, p3, …} образует циклическую подгруппу в G.

Таким образом, подмножество G содержит единичный элемент, замкнуто относительно операций сложения и умножения и содержит элементы, обратные его элементам и по сложению, и по умножению. Следовательно, оно является подполем, и арифметика в этом подполе есть арифметика по модулю р. Но это в точности поле, описываемое теоремой 2.2.3, и, следовательно, р должно быть простым.

 

 

В поле Галуа GF(q) мы построили подполе GF (р), где р — простое число. В частности, если q, с которого мы начинаем, само является простым числом, то, как мы видим, поле GF(q) можно интерпретировать как поле чисел по модулю q. Следовательно, для заданного простого числа действительно существует только одно поле с данным числом элементов, хотя, конечно, оно может быть представлено многими разными способами. Два поля, различающиеся только представлениями, называются изоморфными.

Мы увидели, что исходное поле GF(q) является расширением подполя GF(р). Теперь мы рассмотрим многочлены над GF(р), корнями которых являются некоторые выбранные элементы поля GF(q). Для большей точности введем следующее определение.

Определение 2.6.3. Пусть GF(q) —некоторое поле, пусть GF(Q) —расширение поля GF(q), и пусть β —элемент GF(Q). Простой многочлен f(x) наименьшей степени над GF(q), для которого f(β)= 0, называется минимальным многочленом элемента β над GF(q).

 

 

Мы должны доказать, что минимальный многочлен всегда существует и является единственным.

Теорема 2.6.4. Каждый элемент β из GF(Q) имеет единственный минимальный многочлен над GF(q). Если минимальный многочлен элемента β равен f(х) и β является корнем многочлена g (х), то f(х) делит g (х).

Доказательство. Прежде всего β всегда является корнем многочлена xQ-х, представляющего собой многочлен над GF(q). Воспользуемся теоремой об однозначном разложении:

xQ-х=f1(x)∙f2(x)∙….∙fk(x)

множители в правой части - все простые многочлены над полем GF(q). Если β —корень левой части, то в правой части должен найтись некоторый член, корнем которого является β. Это может быть только один из членов правой части, так как над расширением GF(Q) простые многочлены дальше разлагаются в произведение линейных членов и констант, и β может быть корнем только одного из линейных членов.

Чтобы доказать вторую часть теоремы, положим

g(x)= f(x) h(x) +s(x),

где степень многочлена s(х) меньше степени f(x;), так что β не может быть его корнем. Но

О =g(β) =f(β) h(β) +s(β); следовательно, s(х) должен равняться нулю, и теорема доказана.

 

 

Следствие 2.6.5. Если f1(x), ∙f2(x),∙….∙fk(x)все различные многочлены над GF(q), являющиеся минимальными для одного или нескольких элементов из GF(Q), то

xQ-х=f1(x)∙f2(x)∙….∙fk(x)

.

Доказательствоследует из теоремы, так как каждый такой элемент β является корнем многочлена х xQ-х.

 

При Q = q разложение сводится к равенству

xq –x =x .(x-β1)((x-β2) …(x-βq-1),

которое мы уже встречали в теореме 2.5.2. Минимальный много­член над GF(q) элемента β, принадлежащего GF(q), является многочленом первой степени f(x:) = x – β

.

Теорема 2.6.6. Пустьg (х) произвольный многочлен над GF(q). Тогда существует расширение GF(Q), в котором g(х) распадается на произведение линейных множителей.

Доказательство. Без потери общности можно предположить, что g(х) приведен. Построим последовательность расширений GF(q) < GF (Q1) <GF(Q2)< … <GF(Q) ) по следующему правилу. На каждом шаге запишем g(х) в виде произведения простых многочленов над GF(Qj). Если еще имеются нелинейные множители, то выберем один из них, скажем gj (х), и построим расширение поля GF(Qj), используя gj(у) в качестве простого модуля. В этом расширении g(х) можно разложить далее, поскольку новый элемент β = у является корнем многочлена g(х). Таким образом (в случае необходимости унифицируя обозначения) будем действовать до тех пор, пока все множители не станут линейными. Поскольку степень g(х) конечна, процесс закончится после конечного числа шагов.

 

Определение 2.6.7. Любое расширение поля GF(q), в котором многочлен g(х) над GF(q) распадается в произведение линейных множителей и констант, называется полем разложения много­члена g(х).

Теперь у нас есть все необходимое для описания структуры произвольного поля Галуа.

 

 

Теорема 2.6.8. Пусть α — примитивный элемент поля Галуа GF(Q), являющегося расширением поля GF(q), и пусть m — степень минимального многочлена f(х) элемента α над GF(q). Тогда число элементов в поле равно Q = qm и каждый элемент β может быть представлен в виде

β = аm-1α m-1+am-2αm-2 + ,,,, -+ a1α1+ a0,

где a0, a1, … ,am-1— элементы поля GF(q). . : :


Доказательство. Очевидно, что каждый элемент β вида

β = аm-1α m-1+am-2αm-2 + ,,,, -+ a1α1+ a0

принадлежит полю GF(Q). Такое разложение единственно, так как если

β= bm-1α m-1+bm-2αm-2 + ,,,, -+ b1α1+ b0

— другое представление элемента рβ, то

О = (аm-1- bm-1m-1+ (am-2 -bm-2m-2 + ,,,, -+ (a1- b11+ a0-b0, и, следовательно, α является корнем многочлена степени m- 1, что противоречит выбору числа m. Всего имеется qm таких элементов β, и, следовательно, число элементов поля Q не меньше qm . С другой стороны, каждый ненулевой элемент поля может быть представлен в виде некоторой степени элемента α. Но если f(х) — минимальный многочлен элемента α, то f(α) = 0. Следо­вательно,

αm+fm-1α m-1+fm-2αm-2 + ,,,, -+ f1α1+ f0=0,

Полученное равенство можно использовать для того, чтобы выразить элемент аm через сумму меньших степеней элемента α:

αm =-( fm-1α m-1+fm-2αm-2 + ,,,, -+ f1α1+ f0)

Полученное соотношение можно повторно применять для редукции любой степени элемента α

к линейной комбинации степеней (αm-1, .,., α1, α°).

Следовательно, каждый элемент поля GF(Q) может быть представлен в виде линейной

комбинации элементов (αm-1, .,., α1, α°), так что Q не может быть больше qm, и теорема доказана.

 

Следствие 2.6.9. Каждое поле Галуа содержит рm элементов, где р—некоторое простое, а m—положительное целое число.

Доказательство. Каждое поле Галуа содержит подполе с р элементами, к которому надо применить теорему 2.6.8.

 

Заметим, что теорему 2.6.8 можно использовать для того, чтобы связать с каждым элементом поля некоторый многочлен степени не выше m -1 путем простой замены элемента α на неопределенную переменную х. Эти многочлены можно рассматривать как элементы поля. Складываться и умножаться они будут по модулю минимального многочлена f(х) элемента α. Это в точности то же самое поле, которое получается в теореме 2.4.3, если в качестве простого многочлена выбрать f(х). Следовательно, число элементов в каждом поле Галуа равно степени простого числа, и каждое поле Галуа может быть построено с помощью арифметики по модулю простого многочлена.

Наконец, мы должны доказать и обратное: такое поле существует для каждого простого р и целого положительного числа m. Прежде всего установим некоторые предварительные результаты.

Теорема 2.6.10. Пусть характеристика поля GF(q) равна р. Тогда для любых элементов α и β из GF(q) и любого положительного целого

pm pm pm

(α±β) =α ±β

Доказательство. Предположим, что теорема верна для m=1. Тогда

p p p

(α±β) =α ±β

. Возведем это равенство в р-ю степень

((α±β)p)p =(αpp)p

и снова используем теорему для m = 1

p2 p2 p2

(α±β) = α ±β.

Повторяя эту процедуру m-1 раз, получим

 

pm pm pm

(α±β) =α ±β

Следовательно, теорему надо доказать только для m = 1. Вос­пользовавшись биномиальным разложением

p p

(α±β)p = ∑ ci αi (±β)p-i

i=0

 

видим, что достаточно доказать, что в поле GF(q) выполняется равенство cip =0.

Но для каждого i число сочетаний

cpi = p! /(i! (p-i)!)=(p (p-1)!)/(i!(p-1i)!)

является целым числом, а p — простое. Следовательно, знаменатель делит — 1)!, а число cpi кратно р. Таким образом, cpi (mod p)=0, и поскольку арифметикой целых чисел в поле GF(q) является арифметика по модулю р, то в GF (q) биномиальный коэффициент cpi. =0. Наконец, если р =— 2, то (±β)2 = β2, а если р нечетно, то (±β)р = ±βp. Это завершает доказательство теоремы.

Теорема 2.6.11.Пусть р — простое, а т положительное целое число. Тогда наименьшее поле разложения многочлена g(х) = ( x рт p)m х , рассматриваемого над полем GF(р), содержит рт элементов.

Доказательство.Каждый многочлен над GF(р) имеет наименьшее поле разложения. Пусть GF(Q) — наименьшее поле разложения многочлена g(х).. Тогда в поле GF(Q) многочлен g(х} имеет рт корней (возможно, кратных). Мы покажем, что все рт корней различны и образуют поле. Из этого будет следовать, что GF(Q) содержит рт элементов.

Для того чтобы доказать, что множество корней образует поле, достаточно показать, что оно замкнуто относительно операций сложения и умножения и содержит обратные для всех ненулевых элементов. Пусть α и β — корни многочлена g(х). Согласно теореме 2.6.10,

pm pm pm

(α±β) =α ±β =α± β ,

 

так что а ± β — также корень многочлена, и, следовательно, множество замкнуто относительно операции сложения. Далее m m m . ,

 

((αβ)p)m =(αp)m p )m =αβ

 

и, таким образом, αβ тоже является корнем, и множество корней замкнуто относительно операции умножения. Далее, -α является аддитивным обратным элементу α, так что каждый элемент имеет аддитивный обратный. Аналогично легко проверить, что если а — корень многочлена, то α-1 —также его корень.

 

Наконец, проверим, что все рm корней многочлена xpm- х( xp)m- х различны. Это вытекает из вида формальной производной: m m-1 .

d . d[( xp)m- х]/ dx =((pm)) xp - 1( xp)m/x - x),

так как ((р))=0 в поле GF(Q). Следовательно, многочлен g(х) = ( xp)m –х не имеет кратных корней.

 

Теперь мы получили обращение теоремы 2.6.9.

Следствие 2.6.12.Для каждого простого р и положительного целого числа т существует поле Галуа с рт элементами.

 

Покажем, наконец, что если q является не простым числом, а степенью простого числа, то GF(qт) можно построить как расширение поля GF(q). Для этого достаточно доказать существование над GF(q) простых многочленов степени т.

 

Теорема 2.6.13.Для каждого целого положительного т над каждым конечным полем GF(q) существует хотя бы один простой многочлен степени т.

Доказательство.Так как q—степень простого числа, то qт также является степенью простого числа. Согласно следствию 2.6.12, существует поле с qт элементами. Это поле содержит примитивный элемент а, и, по теореме 2.6.8, минимальный многочлен этого элемента а над GF(q) является простым многочленом степени т.

 

Следствие 2.6.14.Для каждого целого положительного т над каждым конечным полем GF(q) существует хотя бы один примитивный многочлен степени т.

Доказательство.Пусть α — примитивный элемент поля GF(qт), и пусть f(х) — минимальный многочлен элемента а, над GF(q). Тогда в поле многочленов по модулю f(х) примитивный элемент α = х является корнем многочлена f(х), так что многочлен х представляет собой примитивный элемент поля.

 

3. ВАРИАНТЫ ДОМАШРИХ ЗАДАНИЙ

3.

3. ЗАДАНИЕ № 1

3.

3. Пусть G=(0;1;2;3;4;5;6;7;8 )- группа с групповой операцией- сложение по модулю 9. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. Найти НОД(1573, 308). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 1573, 308)= А*1573 + В*308.

3. Доказать, что р(х)=х2+ 2х3+ 3 неприводим над полем GF(5 ). Чему равен порядок элемента х по умножению в поле GF(52), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(52)

3.

3.

3.

3. ЗАДАНИЕ № 2

3.

3. Пусть G=(0;1;2;3;4;5;6;7;8;9;10;11 )- группа с групповой операцией- сложение по модулю 12. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. Найти НОД(605, 308). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 605, 308)= А*605 + В*308.

3. Доказать, что р(х)=х2+ 3х3+ 3 неприводим над полем GF(5 ). Чему равен порядок элемента х по умножению в поле GF(52), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(52)

3.

3.

3.

3. ЗАДАНИЕ № 3

3.

3. Пусть G=(0;1;2;3;4;5 )- группа с групповой операцией- сложение по модулю 6. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. Найти НОД(1572, 308). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 1572, 308)= А*1572 + В*308.

3. Доказать, что р(х)=х2+4х+ 2 неприводим над полем GF(5 ). Чему равен порядок элемента х по умножению в поле GF(52), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(52 )

3.

3.

3.

3. ЗАДАНИЕ № 4

3.

3. Пусть G=(0;1;2;3;4;5;6;7 )- группа с групповой операцией- сложение по модулю 8. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. Найти НОД(8991, 592). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 8991, 592)= А*8991 + В*592.

3. Доказать, что р(х)=х3+ 2х+1 неприводим над полем GF( 3).Чему равен порядок элемента х по умножению в поле GF(33), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(33)

3.

3. ЗАДАНИЕ № 5

3.

3. Пусть G=(0;1;2;3;4;5;6;7;8;9 )- группа с групповой операцией- сложение по модулю 10. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. Найти НОД(3003,429). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 3003, 429)= А*3003 + В*429.

3. Доказать, что р(х)= х3+ х2+ 2х+ 1 неприводим над полем GF( 3).Чему равен порядок элемента х по умножению в поле GF(33), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(33)

3.

3.

3.

3.

3. ЗАДАНИЕ № 6

3.

3. Пусть G=(0;1;2;3;4;5;6;7;8;9;10;11;12;13 )- группа с групповой операцией- сложение по модулю 14. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. Найти НОД(1155, 616). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 1155, 616)= А*1155 + В*616.

3. Доказать, что р(х)=х3+ 2х2+ х+ 1 неприводим над полем GF(3 ). Чему равен порядок элемента х по умножению в поле GF(33 ), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(33 )

3.

3.

3. ЗАДАНИЕ № 7

3.

3. Пусть G=(0;1;2;3;4;5;6;7;8;9;10;11;12;13;14 )- группа с групповой операцией- сложение по модулю 15. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. Найти НОД(1001, 858). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 1001, 858)= А*1001 + В*858.

3. Доказать, что р(х)=х3+ 2х2+1 неприводим над полем GF( 3). Чему равен порядок элемента х по умножению в поле GF(33), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(33)

3.

3.

3.

3. ЗАДАНИЕ № 8

3.

3. Пусть G=(0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15 )- группа с групповой операцией- сложение по модулю 16. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. Найти НОД(603, 308). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 603, 308)= А*603 + В*308.

3. Доказать, что р(х)=х2+ х+2 неприводим над полем GF( 3).Чему равен порядок элемента х по умножению в поле GF(32 ), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(32 ). Разложить над этим полем многочлен q(y)=7y3 -5y2-6y+8.

3.

3.

3. ЗАДАНИЕ № 9

3.

3. Пусть G=(0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17 )- группа с групповой операцией- сложение по модулю 18. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. Найти НОД(1573, 552). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 1573, 552)= А*1573 + В*552.

3. Доказать, что р(х)=х2+ 2х+ 2 неприводим над полем GF( 3).Чему равен порядок элемента х по умножению в поле GF(32 ), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(32 ). Разложить над этим полем многочлен q(y)=5y3 -5y2-8y+8

3.

3.

3. ЗАДАНИЕ № 10

3.

3. Пусть G- группа с групповой операцией- сложение по модулю 20. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. Найти НОД(1570, 306). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 1570, 306)= А*1570 + В*306.

3. Доказать, что р(х)=х2+ 2х+ 3 неприводим над полем GF(5).Чему равен порядок элемента х по умножению в поле GF(52 ), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(52 )

3.

3.

3.

3. ЗАДАНИЕ № 11

3.

3. Пусть G- группа с групповой операцией- сложение по модулю 21. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. Найти НОД(3146, 924). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 3145, 924)= А*3145 + В*924

3. Доказать, что р(х)=х2+ х+ 2 неприводим над полем GF(4 ). Чему равен порядок элемента х по умножению в поле GF(42 ), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(42)

3.

3.

3.

3. ЗАДАНИЕ № 12

3.

3. Пусть G- группа с групповой операцией- сложение по модулю 24. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. Найти НОД(3100, 308). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 3100, 308)= А*3100 + В*308.

3. Доказать, что р(х)=х2+ х+ 3 неприводим над полем GF(4 ). Чему равен порядок элемента х по умножению в поле GF(42 ), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(42)

3.

3.

3.

3. ЗАДАНИЕ № 13

3.

3. Пусть G=(1;2;3;4;5;6;7;8 )- группа с групповой операцией *, задаваемой таблицей. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. * |1 2 3 4 5 6 7 8

3. _ .|___________

3. 1 |1 2 3 4 5 6 7 8

3. 2 |2 3 4 1 6 7 8 5

3. 3 |3 4 1 2 7 8 5 6 4 |4 1 2 3 8 5 6 7

3. 5 |5 8 7 6 1 4 3 2

3. 6 |6 5 8 7 2 1 4 3

3. 7 |7 6 5 8 3 2 1 4

3. 8 |8 7 6 5 4 3 2 1

3. Найти НОД(3146, 208). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 3146, 208)= А*3145 + В*208.

3. Доказать, что р(х)=х2+ 2х+ 2 неприводим над полем GF(4 ).Чему равен порядок элемента х по умножению в поле GF(42 ), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(42)

3.

3.

3.

3.

3.

3.

3.

3. ЗАДАНИЕ № 14

3.

3. Пусть G=(1;a;b;c;d;e;f;g )- группа с групповой операцией *, задаваемой таблицей. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. * |1 a b c d e f g

3. _ .|___________

3. 1 |1 a b c d e f g

3. a |a b c 1 e f g d

3. b |b c 1 a f g d e c |c 1 a b g d e f

3. d |d g f e 1 c b a

3. e |e d g f a 1 c b

3. f |f e d g b a 1 c

3. g |g f e d c b a 1

3. Найти НОД(8991, 552). Найти целые числа А и В, удовлетворяющие равенству

3. НОД (8991, 552)= А*8991 + В*552.

3. Доказать, что р(х)=х2+ 3х+ 3 неприводим над полем GF(4 ). Чему равен порядок элемента х по умножению в поле GF(42 ), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(42)

3.

3.

3.

3. ЗАДАНИЕ № 15

3.

3. Пусть G=(1;a;b;c;d;e;f;g )- группа с групповой операцией *, задаваемой таблицей. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. * |1 g b e d c f a

3. _ .|___________

3. 1 |1 g b e d c f a

3. g |g b e 1 c f a d

3. b |b e 1 g f a d c e |e 1 g b a d c f

3. d |d a f c 1 e b g

3. c |c d a f g 1 e b

3. f |f c d a b g 1 e

3. a |a f c d e b g 1

3.

3. Найти НОД(8931, 309). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 8931, 309)= А*8931 + В*309.

3. Доказать, что р(х)=х4+ х+ 1 неприводим над полем GF( 2).Чему равен порядок элемента х по умножению в поле GF( 24), построенному по модулю р(х).Построить таблицы по умножению и по сложению в поле GF(24 )

3.

3.

3.

3.

3.

3.

3.

3.

3. ЗАДАНИЕ № 16

3.

3. Пусть G=(1;a;b;c;d;e;f;g )- группа с групповой операцией *, задаваемой таблицей. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. * |1 g f e d c b a

3. _ .|___________

3. 1 |1 g f e d c b a

3. g |g f e 1 c b a d

3. f |f e 1 g b a d c e |e 1 g f a d c b

3. d |d a b c 1 e f g

3. c |c d a b g 1 e f

3. b |b c d a f g 1 e

3. a |a b c d e f g 1

3. Найти НОД(8961, 309). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 8961, 309)= А*8961 + В*309.

3. Доказать, что р(х)=х4+ х3+ 1 неприводим над полем GF( 2).Чему равен порядок элемента х по умножению в поле GF( 24), построенному по модулю р(х).Построить таблицы по умножению и по сложению в поле GF(24 )

3.

3.

3.

3. ЗАДАНИЕ № 17

3.

3. Пусть G=(1;a;b;c;d;e)- группа с групповой операцией *, задаваемой таблицей. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. * |1 a b c d e

3. _ .|_________

3. 1 |1 a b c d e

3. a |a b 1 d e c

3. b |b 1 a e c d c |c e d 1 b a

3. d |d c e a 1 b

3. e |e d c b a 1

3.

3. Найти НОД(963, 306). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 963, 306)= А*963 + В*306

3. Доказать, что р(х)=х3+ х2+ 1 неприводим над полем GF(2 ).Чему равен порядок элемента х по умножению в поле GF(23 ), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(23 ). Разложить над этим полем многочлен q(y)=7y3 -5y2-6y+3

3.

3.

3.

3.

3.

3. ЗАДАНИЕ № 18

3.

3. Пусть G=(1;a;b;c;d;e)- группа с групповой операцией *, задаваемой таблицей. Определить порядок каждого элемента группы. Найти подгруппы. Разложить группу на смежные классы по одной из подгрупп.

3. * |1 2 3 4 5 6

3. _ .|_________

3. 1 |1 2 3 4 5 6

3. 2 |2 3 1 5 6 4

3. 3 |3 1 2 6 4 5 4 |4 6 5 4 3 2

3. 5 |5 4 6 2 1 3

3. 6 |6 5 4 3 2 1

3. Найти НОД(1562, 297). Найти целые числа А и В, удовлетворяющие равенству

3. НОД ( 1562, 297)= А*1562 + В*297

3. Доказать, что р(х)=х3+ х+ 1 неприводим над полем GF( 2). Чему равен порядок элемента х по умножению в поле GF(23 ), построенному по модулю р(х). Построить таблицы по умножению и по сложению в поле GF(23 ). Разложить над этим полем многочлен q(y)=7y3 -5y2+5y+7

3.

3.

 

– Конец работы –

Эта тема принадлежит разделу:

Лекции и домашнии задания по курсу токбдискретная математика введение в дискретную алгебру

Лекции и домашнии задания по курсу токбдискретная математика.. для студентов дневного отделения специальности киришкий филиал.. введение в дискретную алгебру..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: СТРУКТУРА КОНЕЧНОГО ПОЛЯ

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Доказательство.
(1). аО = а (0 + 0) = аО + аО. Вычитая из обеих частей равенства аО, получаем 0 = аО. Вторая часть утверждения (1) доказывается аналогично, (2). О = аО = а (b — b) = аb

Теорема 1.2.4.
(1) Множество единиц кольца образует группу относительно умножения в кольце (2) Если с = аb и с — единица, то а имеет правый обратный, а b — левый о

ВЕКТОРНЫЕ ПРОСТРАНСТВА
Известный пример векторного пространства дает трехмерное евклидово пространство, фигурирующее во многих физических задачах. Его обобщением является n-мерное векторное пространство над полем веществ

ЛИНЕЙНАЯ АЛГЕБРА
  Широко используемые разделы прикладной математики — линейная алгебра, в частности теория матриц, — обычно изучаются только для поля вещественных чисел и поля комплексных чисел, одна

Теорема 12.56.3.
10) Если все элементы некоторой строки квадратной матрицы равны нулю, то определитель этой матрицы равен нулю., 2П) Определитель матрицы равен определителю транспони­рованной мат

КОЛЬЦО ЦЕЛЫХ ЧИСЕЛ
| Множество всех целых чисел (положительных, отрицательных и нуля) образуют кольцо относительно обычных операций сложе­ния и умножения. Это кольцо принято обозначать через Z. В данном пара

Теорема 2.1.2.
1. Rd(a+b)=Rd{ Rd (a) + Rd (b) } 2 . Rd(a*b)=Rd{ Rd (a) *Rd (b

КОНЕЧНЫЕ ПОЛЯ, ОСНОВАННЫЕ НА КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ
Имеется очень важная конструкция, позволяющая по заданному кольцу построить новое кольцо, называемое кольцом отношений. В случае произвольного кольца для построения кольца отноше­ний строятс

КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ
Когда можно однозначно определить целое число, если заданы только его вычеты по модулям нескольких целых чисел? Ответ на этот вопрос был известен еще в древнем Китае. Китайская теорема об остатк

КОЛЬЦА МНОГОЧЛЕНОВ
Многочленом над полем GF(q) называется математическое выра­жение f(x)= fn-1 xn-1+fn-2 xn

Теорема 2.3.4.
(1) Rd(х)[a(х)+b(x)]= Rd(х)[a(х)]+ Rd(х)[b(х)] , (2 ) Rd(х)

КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ
Теорема 2.3.8. Для заданного множества попарно взаимно простых многочленов т1 (х), m2(х), ..., тk (х) и множества многочленов с1 (х),

КОНЕЧНЫЕ ПОЛЯ, ОСНОВАННЫЕ НА КОЛЬЦАХ МНОГОЧЛЕНОВ
Конечные поля можно построить из колец многочленов таким же образом, каким были построены поля из кольца целых чисел. Пусть имеется кольцо многочленов F [х] над полем F. Так же, как б

Степень Простые многочлены
2 x2 +x +1 3 x3 +x +1 4 x4 +x +1 5 x5 +x2 +1 6 x6 +x +1 7 x7 +x3

ПРИМИТИВНЫЕ ЭЛЕМЕНТЫ
В предыдущем параграфе было построено поле GF(4). На рис. 2.2 видно, , за исключением нуля, все элементы поля могут быть представлены в виде степени элемента х. Опред

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги