По модулю m , которая обозначается $\backslash mathbb\{Z\}\_m^\{\backslash times\}$ или $U(\backslash mathbb\{Z\}\_m)$ .

Если m простое, то, как отмечалось выше, элементы 1, 2, ...,m -1 входят в $\backslash mathbb\{Z\}\_m^\{\backslash times\}$. В этом случае $\backslash mathbb\{Z\}\_m^\{\backslash times\}$ является полем .

Формы записи

Кольцо вычетов по модулю n обозначают $\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}$ или $\backslash mathbb\{Z\}\_n$. Его мультипликативную группу, как и в общем случае групп обратимых элементов колец, обозначают $(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})^*,$ $(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})^\backslash times,$ $U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}),$ $E(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}),$ $\backslash mathbb\{Z\}\_n^\{\backslash times\},$ $U(\backslash mathbb\{Z\}\_n)$.

Простейший случай

Чтобы понять структуру группы $U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$, можно рассмотреть частный случай $n=p^a$, где $p$ - простое число, и обобщить его. Рассмотрим простейший случай, когда $a=1$, т.е. $n=p$.

Теорема: $U(\backslash mathbb\{Z\}/p\backslash mathbb\{Z\})$ - циклическая группа.

Пример : Рассмотрим группу $U(\backslash mathbb\{Z\}/9\backslash mathbb\{Z\})$

$U(\backslash mathbb\{Z\}/9\backslash mathbb\{Z\})$ = {1,2,4,5,7,8} Генератором группы является число 2. $2^1\; \backslash equiv\; 2\backslash \; \backslash pmod\; 9$ $2^2\; \backslash equiv\; 4\backslash \; \backslash pmod\; 9$ $2^3\; \backslash equiv\; 8\backslash \; \backslash pmod\; 9$ $2^4\; \backslash equiv\; 7\backslash \; \backslash pmod\; 9$ $2^5\; \backslash equiv\; 5\backslash \; \backslash pmod\; 9$ $2^6\; \backslash equiv\; 1\backslash \; \backslash pmod\; 9$ Как видим, любой элемент группы $U(\backslash mathbb\{Z\}/9\backslash mathbb\{Z\})$ может быть представлен в виде $2^l$, где . То есть группа $U(\backslash mathbb\{Z\}/9\backslash mathbb\{Z\})$ - циклическая.

Общий случай

Для рассмотрения общего случая необходимо определение примитивного корня . Примитивный корень по простому модулю $p$ – это число, которое вместе со своим классом вычетов порождает группу $U(\backslash mathbb\{Z\}/p\backslash mathbb\{Z\})$.

Примеры: 2 11 ; 8 - примитивный корень по модулю 11 ; 3 не является примитивным корнем по модулю 11 .

В случае целого модуля $n$ определение такое же.

Структуру группы определяет следующая теорема: Если p - нечётное простое число и l – целое положительное, то существуют примитивные корни по модулю $p^\{l\}$, то есть $U(\backslash mathbb\{Z\}/p^\{l\}\backslash mathbb\{Z\})$ - циклическая группа.

Подгруппа свидетелей простоты

Пусть $m$ - нечётное число большее 1. Число $m-1$ однозначно представляется в виде $m-1\; =\; 2^s\; \backslash cdot\; t$, где $t$ нечётно. Целое число $a$, , называется свидетелем простоты числа $m$, если выполняется одно из условий:

• $a^t\backslash equiv\; 1\backslash pmod\; m$

• существует целое число $k$,

Если число $m$ - составное, существует подгруппа мультипликативной группы кольца вычетов, называемая подгруппой свидетелей простоты. Её элементы, возведённые в степень $m-1$, совпадают с $1$ по модулю $m$.

Пример : $m=9$. Есть $6$ остатков, взаимно простых с $9$, это $1,2,4,5,7$ и $8$. $8$ эквивалентно $-1$ по модулю $9$, значит $8^\{8\}$ эквивалентно $1$ по модулю $9$. Значит, $1$ и $8$ - свидетели простоты числа $9$. В данном случае {1, 8} - подгруппа свидетелей простоты.

Свойства

Экспонента группы

Порождающее множество

$U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$ - циклическая группа тогда и только тогда, когда $\backslash varphi(n)=\backslash lambda(n).$ В случае циклической группы генератор называется первообразным корнем .

Пример

Приведённая система вычетов по модулю $10$ состоит из $4$ классов вычетов: $\_\{10\},\; \_\{10\},\; \_\{10\},\; \_\{10\}$. Относительно определённого для классов вычетов умножения они образуют группу, причём $\_\{10\}$ и $\_\{10\}$ взаимно обратны (то есть $\_\{10\}\{\backslash cdot\}\_\{10\}\; =\; \_\{10\}$), а $\_\{10\}$ и $\_\{10\}$ обратны сами себе.

Структура группы

Запись $C\_n$ означает «циклическая группа порядка n».

Структура группы $U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$

$n\backslash ;$	$U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$	$\backslash varphi(n)$	$\backslash lambda(n)\backslash ;$	генератор		$n\backslash ;$	$U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$	$\backslash varphi(n)$	$\backslash lambda(n)\backslash ;$	генератор
2	C 1	1	1	1		33	C 2 ×C 10	20	10	10, 2
3	C 2	2	2	2		34	C 16	16	16	3
4	C 2	2	2	3		35	C 2 ×C 12	24	12	6, 2
5	C 4	4	4	2		36	C 2 ×C 6	12	6	19, 5
6	C 2	2	2	5		37	C 36	36	36	2
7	C 6	6	6	3		38	C 18	18	18	3
8	C 2 ×C 2	4	2	7, 3		39	C 2 ×C 12	24	12	38, 2
9	C 6	6	6	2		40	C 2 ×C 2 ×C 4	16	4	39, 11, 3
10	C 4	4	4	3		41	C 40	40	40	6
11	C 10	10	10	2		42	C 2 ×C 6	12	6	13, 5
12	C 2 ×C 2	4	2	5, 7		43	C 42	42	42	3
13	C 12	12	12	2		44	C 2 ×C 10	20	10	43, 3
14	C 6	6	6	3		45	C 2 ×C 12	24	12	44, 2
15	C 2 ×C 4	8	4	14, 2		46	C 22	22	22	5
16	C 2 ×C 4	8	4	15, 3		47	C 46	46	46	5
17	C 16	16	16	3		48	C 2 ×C 2 ×C 4	16	4	47, 7, 5
18	C 6	6	6	5		49	C 42	42	42	3
19	C 18	18	18	2		50	C 20	20	20	3
20	C 2 ×C 4	8	4	19, 3		51	C 2 ×C 16	32	16	50, 5
21	C 2 ×C 6	12	6	20, 2		52	C 2 ×C 12	24	12	51, 7
22	C 10	10	10	7		53	C 52	52	52	2
23	C 22	22	22	5		54	C 18	18	18	5
24	C 2 ×C 2 ×C 2	8	2	5, 7, 13		55	C 2 ×C 20	40	20	21, 2
25	C 20	20	20	2		56	C 2 ×C 2 ×C 6	24	6	13, 29, 3
26	C 12	12	12	7		57	C 2 ×C 18	36	18	20, 2
27	C 18	18	18	2		58	C 28	28	28	3
28	C 2 ×C 6	12	6	13, 3		59	C 58	58	58	2
29	C 28	28	28	2		60	C 2 ×C 2 ×C 4	16	4	11, 19, 7
30	C 2 ×C 4	8	4	11, 7		61	C 60	60	60	2
31	C 30	30	30	3		62	C 30	30	30	3
32	C 2 ×C 8	16	8	31, 3		63	C 6 ×C 6	36	6	2, 5

Применение

История

Вклад в исследование структуры мультипликативной группы кольца вычетов внесли Артин , Билхарц, Брауэр , Вильсон, Гаусс , Лагранж , Лемер, Уоринг , Ферма, Хули, Эйлер . Лагранж доказал лемму о том, что если $f(x)\; \backslash in\; k[x]$, и k - поле, то f имеет не более n различных корней, где n - степень f. Он же доказал важное следствие этой леммы, заключающееся в сравнении $x^\{p-1\}-1$ ≡ $(x-1)(x-2)...(x-p+1)mod(p)$. Эйлер доказал малую теорему Ферма . Уоринг сформулировал теорему Вильсона, а Лагранж её доказал. Эйлер предположил существование примитивных корней по модулю простого числа. Гаусс это доказал. Артин выдвинул свою гипотезу о существовании и количественной оценке простых чисел, по модулю которых заданное целое число является первообразным корнем. Брауэр внес вклад в исследование проблемы существования наборов последовательных целых чисел, каждое из которых - k-ая степень по модулю p. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезу Артина с предположением справедливости расширенной гипотезы Римана в полях алгебраических чисел.

Напишите отзыв о статье "Мультипликативная группа кольца вычетов"

Примечания

Литература

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. - М .: Мир, 1987.
• Алферов А.П., Зубов А.Ю., Кузьмин А.С. Черемушкин А.В. Основы криптографии. - Москва: «Гелиос АРВ», 2002.
• Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. - Санкт-Петербург: НПО «Профессионал», 2004.

Ссылки

• Бухштаб А. А. Теория чисел. - М .: Просвещение, 1966.
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .

Отрывок, характеризующий Мультипликативная группа кольца вычетов

– Получил известие. В числе пленных нет, в числе убитых нет. Кутузов пишет, – крикнул он пронзительно, как будто желая прогнать княжну этим криком, – убит!
Княжна не упала, с ней не сделалось дурноты. Она была уже бледна, но когда она услыхала эти слова, лицо ее изменилось, и что то просияло в ее лучистых, прекрасных глазах. Как будто радость, высшая радость, независимая от печалей и радостей этого мира, разлилась сверх той сильной печали, которая была в ней. Она забыла весь страх к отцу, подошла к нему, взяла его за руку, потянула к себе и обняла за сухую, жилистую шею.
– Mon pere, – сказала она. – Не отвертывайтесь от меня, будемте плакать вместе.
– Мерзавцы, подлецы! – закричал старик, отстраняя от нее лицо. – Губить армию, губить людей! За что? Поди, поди, скажи Лизе. – Княжна бессильно опустилась в кресло подле отца и заплакала. Она видела теперь брата в ту минуту, как он прощался с ней и с Лизой, с своим нежным и вместе высокомерным видом. Она видела его в ту минуту, как он нежно и насмешливо надевал образок на себя. «Верил ли он? Раскаялся ли он в своем неверии? Там ли он теперь? Там ли, в обители вечного спокойствия и блаженства?» думала она.
– Mon pere, [Отец,] скажите мне, как это было? – спросила она сквозь слезы.
– Иди, иди, убит в сражении, в котором повели убивать русских лучших людей и русскую славу. Идите, княжна Марья. Иди и скажи Лизе. Я приду.
Когда княжна Марья вернулась от отца, маленькая княгиня сидела за работой, и с тем особенным выражением внутреннего и счастливо спокойного взгляда, свойственного только беременным женщинам, посмотрела на княжну Марью. Видно было, что глаза ее не видали княжну Марью, а смотрели вглубь – в себя – во что то счастливое и таинственное, совершающееся в ней.
– Marie, – сказала она, отстраняясь от пялец и переваливаясь назад, – дай сюда твою руку. – Она взяла руку княжны и наложила ее себе на живот.
Глаза ее улыбались ожидая, губка с усиками поднялась, и детски счастливо осталась поднятой.
Княжна Марья стала на колени перед ней, и спрятала лицо в складках платья невестки.
– Вот, вот – слышишь? Мне так странно. И знаешь, Мари, я очень буду любить его, – сказала Лиза, блестящими, счастливыми глазами глядя на золовку. Княжна Марья не могла поднять головы: она плакала.
– Что с тобой, Маша?
– Ничего… так мне грустно стало… грустно об Андрее, – сказала она, отирая слезы о колени невестки. Несколько раз, в продолжение утра, княжна Марья начинала приготавливать невестку, и всякий раз начинала плакать. Слезы эти, которых причину не понимала маленькая княгиня, встревожили ее, как ни мало она была наблюдательна. Она ничего не говорила, но беспокойно оглядывалась, отыскивая чего то. Перед обедом в ее комнату вошел старый князь, которого она всегда боялась, теперь с особенно неспокойным, злым лицом и, ни слова не сказав, вышел. Она посмотрела на княжну Марью, потом задумалась с тем выражением глаз устремленного внутрь себя внимания, которое бывает у беременных женщин, и вдруг заплакала.
– Получили от Андрея что нибудь? – сказала она.
– Нет, ты знаешь, что еще не могло притти известие, но mon реrе беспокоится, и мне страшно.
– Так ничего?
– Ничего, – сказала княжна Марья, лучистыми глазами твердо глядя на невестку. Она решилась не говорить ей и уговорила отца скрыть получение страшного известия от невестки до ее разрешения, которое должно было быть на днях. Княжна Марья и старый князь, каждый по своему, носили и скрывали свое горе. Старый князь не хотел надеяться: он решил, что князь Андрей убит, и не смотря на то, что он послал чиновника в Австрию розыскивать след сына, он заказал ему в Москве памятник, который намерен был поставить в своем саду, и всем говорил, что сын его убит. Он старался не изменяя вести прежний образ жизни, но силы изменяли ему: он меньше ходил, меньше ел, меньше спал, и с каждым днем делался слабее. Княжна Марья надеялась. Она молилась за брата, как за живого и каждую минуту ждала известия о его возвращении.

– Ma bonne amie, [Мой добрый друг,] – сказала маленькая княгиня утром 19 го марта после завтрака, и губка ее с усиками поднялась по старой привычке; но как и во всех не только улыбках, но звуках речей, даже походках в этом доме со дня получения страшного известия была печаль, то и теперь улыбка маленькой княгини, поддавшейся общему настроению, хотя и не знавшей его причины, – была такая, что она еще более напоминала об общей печали.
– Ma bonne amie, je crains que le fruschtique (comme dit Фока – повар) de ce matin ne m"aie pas fait du mal. [Дружочек, боюсь, чтоб от нынешнего фриштика (как называет его повар Фока) мне не было дурно.]
– А что с тобой, моя душа? Ты бледна. Ах, ты очень бледна, – испуганно сказала княжна Марья, своими тяжелыми, мягкими шагами подбегая к невестке.
– Ваше сиятельство, не послать ли за Марьей Богдановной? – сказала одна из бывших тут горничных. (Марья Богдановна была акушерка из уездного города, жившая в Лысых Горах уже другую неделю.)
– И в самом деле, – подхватила княжна Марья, – может быть, точно. Я пойду. Courage, mon ange! [Не бойся, мой ангел.] Она поцеловала Лизу и хотела выйти из комнаты.
– Ах, нет, нет! – И кроме бледности, на лице маленькой княгини выразился детский страх неотвратимого физического страдания.
– Non, c"est l"estomac… dites que c"est l"estomac, dites, Marie, dites…, [Нет это желудок… скажи, Маша, что это желудок…] – и княгиня заплакала детски страдальчески, капризно и даже несколько притворно, ломая свои маленькие ручки. Княжна выбежала из комнаты за Марьей Богдановной.
– Mon Dieu! Mon Dieu! [Боже мой! Боже мой!] Oh! – слышала она сзади себя.
Потирая полные, небольшие, белые руки, ей навстречу, с значительно спокойным лицом, уже шла акушерка.
– Марья Богдановна! Кажется началось, – сказала княжна Марья, испуганно раскрытыми глазами глядя на бабушку.
– Ну и слава Богу, княжна, – не прибавляя шага, сказала Марья Богдановна. – Вам девицам про это знать не следует.
– Но как же из Москвы доктор еще не приехал? – сказала княжна. (По желанию Лизы и князя Андрея к сроку было послано в Москву за акушером, и его ждали каждую минуту.)
– Ничего, княжна, не беспокойтесь, – сказала Марья Богдановна, – и без доктора всё хорошо будет.
Через пять минут княжна из своей комнаты услыхала, что несут что то тяжелое. Она выглянула – официанты несли для чего то в спальню кожаный диван, стоявший в кабинете князя Андрея. На лицах несших людей было что то торжественное и тихое.
Княжна Марья сидела одна в своей комнате, прислушиваясь к звукам дома, изредка отворяя дверь, когда проходили мимо, и приглядываясь к тому, что происходило в коридоре. Несколько женщин тихими шагами проходили туда и оттуда, оглядывались на княжну и отворачивались от нее. Она не смела спрашивать, затворяла дверь, возвращалась к себе, и то садилась в свое кресло, то бралась за молитвенник, то становилась на колена пред киотом. К несчастию и удивлению своему, она чувствовала, что молитва не утишала ее волнения. Вдруг дверь ее комнаты тихо отворилась и на пороге ее показалась повязанная платком ее старая няня Прасковья Савишна, почти никогда, вследствие запрещения князя,не входившая к ней в комнату.
– С тобой, Машенька, пришла посидеть, – сказала няня, – да вот княжовы свечи венчальные перед угодником зажечь принесла, мой ангел, – сказала она вздохнув.
– Ах как я рада, няня.
– Бог милостив, голубка. – Няня зажгла перед киотом обвитые золотом свечи и с чулком села у двери. Княжна Марья взяла книгу и стала читать. Только когда слышались шаги или голоса, княжна испуганно, вопросительно, а няня успокоительно смотрели друг на друга. Во всех концах дома было разлито и владело всеми то же чувство, которое испытывала княжна Марья, сидя в своей комнате. По поверью, что чем меньше людей знает о страданиях родильницы, тем меньше она страдает, все старались притвориться незнающими; никто не говорил об этом, но во всех людях, кроме обычной степенности и почтительности хороших манер, царствовавших в доме князя, видна была одна какая то общая забота, смягченность сердца и сознание чего то великого, непостижимого, совершающегося в эту минуту.
В большой девичьей не слышно было смеха. В официантской все люди сидели и молчали, на готове чего то. На дворне жгли лучины и свечи и не спали. Старый князь, ступая на пятку, ходил по кабинету и послал Тихона к Марье Богдановне спросить: что? – Только скажи: князь приказал спросить что? и приди скажи, что она скажет.
– Доложи князю, что роды начались, – сказала Марья Богдановна, значительно посмотрев на посланного. Тихон пошел и доложил князю.
– Хорошо, – сказал князь, затворяя за собою дверь, и Тихон не слыхал более ни малейшего звука в кабинете. Немного погодя, Тихон вошел в кабинет, как будто для того, чтобы поправить свечи. Увидав, что князь лежал на диване, Тихон посмотрел на князя, на его расстроенное лицо, покачал головой, молча приблизился к нему и, поцеловав его в плечо, вышел, не поправив свечей и не сказав, зачем он приходил. Таинство торжественнейшее в мире продолжало совершаться. Прошел вечер, наступила ночь. И чувство ожидания и смягчения сердечного перед непостижимым не падало, а возвышалось. Никто не спал.

Была одна из тех мартовских ночей, когда зима как будто хочет взять свое и высыпает с отчаянной злобой свои последние снега и бураны. Навстречу немца доктора из Москвы, которого ждали каждую минуту и за которым была выслана подстава на большую дорогу, к повороту на проселок, были высланы верховые с фонарями, чтобы проводить его по ухабам и зажорам.
Княжна Марья уже давно оставила книгу: она сидела молча, устремив лучистые глаза на сморщенное, до малейших подробностей знакомое, лицо няни: на прядку седых волос, выбившуюся из под платка, на висящий мешочек кожи под подбородком.
Няня Савишна, с чулком в руках, тихим голосом рассказывала, сама не слыша и не понимая своих слов, сотни раз рассказанное о том, как покойница княгиня в Кишиневе рожала княжну Марью, с крестьянской бабой молдаванкой, вместо бабушки.
– Бог помилует, никогда дохтура не нужны, – говорила она. Вдруг порыв ветра налег на одну из выставленных рам комнаты (по воле князя всегда с жаворонками выставлялось по одной раме в каждой комнате) и, отбив плохо задвинутую задвижку, затрепал штофной гардиной, и пахнув холодом, снегом, задул свечу. Княжна Марья вздрогнула; няня, положив чулок, подошла к окну и высунувшись стала ловить откинутую раму. Холодный ветер трепал концами ее платка и седыми, выбившимися прядями волос.
– Княжна, матушка, едут по прешпекту кто то! – сказала она, держа раму и не затворяя ее. – С фонарями, должно, дохтур…
– Ах Боже мой! Слава Богу! – сказала княжна Марья, – надо пойти встретить его: он не знает по русски.
Княжна Марья накинула шаль и побежала навстречу ехавшим. Когда она проходила переднюю, она в окно видела, что какой то экипаж и фонари стояли у подъезда. Она вышла на лестницу. На столбике перил стояла сальная свеча и текла от ветра. Официант Филипп, с испуганным лицом и с другой свечей в руке, стоял ниже, на первой площадке лестницы. Еще пониже, за поворотом, по лестнице, слышны были подвигавшиеся шаги в теплых сапогах. И какой то знакомый, как показалось княжне Марье, голос, говорил что то.

4) Мультипликативная группа вычетов по
модулю n.
Несколько сложнее определяется
мультипликативная группа вычетов по
модулю n. Элементы этой группы образуют
множество Z*n , состоящее из элементов Zn ,
взаимно простых с n. Понятие взаимной
простоты имеет следующий смысл:
если k – целое число, то НОД(a,n) = 1
равносильно НОД(a+kn,n) =1.

Теорема 7.

Система
является конечной абелевой группой.

Доказательство.

Проверим, что любой элемент имеет
обратный в смысле групповой операции.
(Нейтральным элементом является класс С1).
Чтобы найти обратный к элементу а, рассмотрим
тройку (d,x,y), выдаваемую процедурой
Extended-Euclid(a,n). Поскольку
, числа a и n
взаимно просты и d= НОД(a,b) = 1, поэтому
ax + ny = 1 и
, таким образом,
элемент является обратным к
в группе
.

Единственность обратного можно доказать
(как и для любой группы) следующим образом:
если х и х’ обратны к а, то
,
а переставив скобки по ассоциативности,
получим
, ч.т.д.

В дальнейшем мы для простоты будем обозначать сложение и умножение по модулю обычными знаками + и ∙ (иногда опуская знак умножения), а аддит

В дальнейшем мы для простоты будем обозначать
сложение и умножение по модулю обычными
знаками + и ∙ (иногда опуская знак умножения), а
аддитивную и мультипликативную группы
вычетов по модулю n будем обозначать Zn и Z*n
(не упоминая групповую операцию). Элемент,
обратный (относительно операции умножения)
к а, мы будем обозначать а-1mod n. Как обычно,
частное a/b в Z*n определяется как
аb-1(mod n). Например, в
имеем
(mod 15),
поскольку
, откуда
.

5) Количество обратимых элементов в кольце вычетов.

Количество обратимых элементов в кольце
вычетов, т.е. число элементов в
,
обозначается
. Функция называется
- функцией Эйлера.

Можно доказать такую формулу для функции Эйлера: (3) где p1,….,ps – список всех простых делителей числа n. Можно пояснить эту формулу так: случа

Можно доказать такую формулу для функции
Эйлера:
(3)
где p1,….,ps – список всех простых делителей
числа n. Можно пояснить эту формулу так:
случайное число t взаимно просто с n, если
оно не делится на p1 (вероятность чего есть
(1-1/p1)), не делится на p2 (вероятность (1-1/p2))
и т.д., а события эти независимы.

Например,
,
поскольку простыми делителями числа 45
являются числа 3 и 5. Для простого числа
имеем
(4)
т.к. все числа 1,2,…, p -1 взаимно просты с p.
Если число n составное, то

6) Подгруппы.

Пусть
является группой, а
.
Если
тоже является группой, то
называют подгруппой группы
. Например,
четные числа образуют подгруппу целых чисел
(с операцией сложения).

10. Если является подгруппой конечной группы, то делит.

Теорема 8 (Лагранж).
Если
является подгруппой конечной группы
то
делит.
,

11. Доказательство.

Можно найти в учебниках алгебры (группа S
разбивается на непересекающиеся классы
вида
, каждый из которых содержит
элементов).
Подгруппа S’ группы S, не совпадающая со
всей группой, называется собственной
подгруппой.

12. Следствие 8.1.

Если S’ является собственной подгруппой конечной
группы S, то
.
Это (очевидное) следствие теоремы Лагранжа
используется при анализе вероятностного
алгоритма Шиллера – Рабина
(проверка простоты).

13. 7) Подгруппа, порожденная элементом группы.

Пусть а – некоторый элемент конечной
группы S. Рассмотрим последовательность
элементов
По аналогии со степенями (групповая операция
соответствует умножению) будем писать
и т.д.
Легко видеть, что
,
в частности
. Аналогичное
утверждение можно сформулировать и для
«отрицательных степеней»,
в частности
.

14. Если группа S конечна, то последовательность будет периодической (следующий элемент определяется предыдущим, поэтому раз повторившись, эл

Если группа S конечна, то
последовательность
будет периодической (следующий элемент
определяется предыдущим, поэтому раз
повторившись, элементы будут повторяться по
циклу). Таким образом, последовательность
имеет вид
(дальше все повторяется) и содержит t
различных элементов, где t – наименьшее
положительное число, для которого
.
Это число называется порядком элемента а и
обозначается ord(a).

15. Указанные t элементов образуют подгруппу, т.к. групповая операция соответствует сложению «показателей степени». Эта подгруппа называется

Указанные t элементов образуют
подгруппу, т.к. групповая операция соответствует
сложению «показателей степени». Эта подгруппа
называется порожденной элементом а и
обозначается или, если мы хотим явно указать
групповую операцию,(
). Элемент а
называют образующей подгруппы
; говорят,
что он порождает эту подгруппу.
Например, элемент а=2 группы Z6
порождает подгруппу, состоящую из элементов
0,2,4.

16. Вот несколько подгрупп группы Z6 , порожденных различными элементами: . Аналогичный пример для мультипликативной группы: здесь Из сказанно

Вот несколько подгрупп группы Z6 ,
порожденных различными элементами:
. Аналогичный
пример для мультипликативной группы
:
здесь
Из сказанного вытекает Теорема 9.

17. Пусть - конечная группа. Если, то число элементов в подгруппе, порождаемой а, совпадает с порядком а (т.е.).

Теорема 9.
Пусть
- конечная группа. Если
, то число
элементов в подгруппе, порождаемой а, совпадает с
порядком а (т.е.
).

18. Следствие 9.1.

Последовательность
имеет период
t=ord(a);
иначе говоря
, тогда и только тогда,
когда
.
Периодичность позволяет продолжить
последовательность в обе стороны, определив
как
при всяком целом i, в том числе и
отрицательном.

19. Следствие 9.2.

В конечной группе
с единицей e для всякого
выполняется равенство
.
Доказательство. По теореме Лагранжа ord(a)
делит, откуда
, где
, ч.т.д.

20. 8) Решение линейных диофантовых уравнений.

Нас будут интересовать целочисленные
решения уравнения
(5)
(здесь а, b и n – целые числа; такие уравнения
называют «линейными диофантовыми
уравнениями»). Ясно, что здесь важен лишь
остаток от деления х на n, так что решением (5)
естественно называть не целое число, а элемент
группы Zn, (класс чисел, дающих один и тот же
остаток при делении на n). Таким образом, можно
сформулировать задачу так: есть элементы
,
мы ищем все
, для которых
.

21. Напомним, что через обозначается порождённая элементом а подгруппа (в данном случае подгруппа группы Zn). По определению, поэтому уравнени

Напомним, что через
обозначается
порождённая элементом а подгруппа (в данном
случае подгруппа группы Zn). По определению
, поэтому уравнение (5)
имеет хотя бы одно решение тогда и только
тогда, когда
. Сколько элементов в
?
По теореме Лагранжа (T8) это число является
делителем n. В Zn групповая операция – это
сложение т.к. Zn - аддитивная группа, поэтому
.

22. Пусть уравнение разрешимо и является его решением. Тогда уравнение имеет d =НОД(а,n) решений в Zn , задаваемых формулой, где i = 0,1,2,... , n - 1.

Теорема 10.
Пусть уравнение
разрешимо и
является его решением. Тогда уравнение имеет
d =НОД(а,n) решений в Zn , задаваемых формулой
, где i = 0,1,2,... , n - 1.

23. Доказательство.

Начав с и двигаясь с шагом n/d, мы
сделаем d шагов, прежде чем замкнем круг, т.к.
. Все пройденные числа будут
решениями уравнения
, так как при
увеличении х на n/d произведение ах
увеличивается на n(a/d), т.е. на кратное n. Таким
образом, мы перечислили все d решений.
a =b
a(+n/d)=a +an/d=a +na/d=a +kn≡a
ч.т.д.

24. Пусть n > 1. Если НОД(а, n) = 1, то уравнение имеет единственное решение (в Zn). Случай b=1 особенно важен – при этом мы находим обратный к х элемент п

Следствие 10.1
Пусть n > 1. Если НОД(а, n) = 1, то уравнение
имеет единственное решение (в Zn).
Случай b=1 особенно важен – при этом мы
находим обратный к х элемент по модулю п, т.е.
обратный в группе элемент.

25. Следствие 10.2

Пусть n > 1. Если НОД(а, n) = 1, то
уравнение ах ≡ 1 (mod n)
(6)
имеет единственное решение в Zn.
При НОД(а, п) > 1 это уравнение решений не
имеет.
Тем самым мы научились вычислять
обратный элемент в группе за O(log n)
арифметических операций.

26. 9) Китайская теорема об остатках.

Около 100 г. до Р.X. китайский математик Сун
Цу решил такую задачу: найти число, дающее
при делении на 3, 5 и 7 остатки 2, 3 и 2
соответственно (общий вид решения 23+105k
при целых k). Поэтому утверждение об
эквивалентности системы сравнений по взаимно
простым модулям и сравнения по модулю
произведения называют «китайской теоремой об
остатках».

27. Пусть некоторое число п представлено в виде произведения попарно взаимно простых чисел. Китайская теорема об остатках утверждает, что кол

Пусть некоторое число п представлено в виде
произведения попарно взаимно простых чисел
. Китайская теорема об остатках
утверждает, что кольцо вычетов Zn устроено как
произведение колец вычетов
(с покомпонентным сложением и умножением).
Это соответствие полезно и с алгоритмической
точки зрения, так как бывает проще выполнить
операции во всех множествах Zni , чем
непосредственно в Zn.

28. 10) Степени элемента.

Рассмотрим в мультипликативной группе
вычетов
последовательность степеней
некоторого элемента а:
(7)
Мы начинаем счет с нуля, полагая
;
i-й член последовательности степеней числа 3 по
модулю 7 имеет вид:
а для степеней числа 2 по модулю 7 имеем:

29. 11) Теорема 11 (Эйлер).

Если n>1 – целое число, то
для всякого
, где
(8)
- фи-функция Эйлера.
Без доказательства.
При простом n теорема превращается в «малую
теорему Ферма».

30. 12) Теорема 12 (малая теорема Ферма).

Если р – простое число, то
(9)
для всякого
.
Доказательство. Поскольку число р – простое,
= р-1 , ч.т.д.

31. Следствие 12.1. Пусть p – простое число Следствие 12.2. Пусть p – простое число, тогда теорема Ферма будет применима и к а=0.

32. 13) Теорема 13 (Усиление теоремы Эйлера).

Пусть n=pq, где p и q – разные простые числа.
Тогда для любого целого числа а и для любого
натурального k справедливо тождество
.

33. ч.т.д.

Доказательство.
ч.т.д.

34. 14) Вычисление степеней повторным возведением в квадрат.

Возведение в степень по модулю играет важную
роль при проверке чисел на простоту, а также в
криптосистеме RSA. Как и для обычных чисел,
повторное умножение – не самый быстрый
способ; лучше воспользоваться алгоритмом
повторного возведения в квадрат.

35. Пусть мы хотим вычислить ab mod n, где а – вычет по модулю n, a b – целое неотрицательное число, имеющее в двоичной записи вид (bk,bk-1,... ,b1,b0) (число з

Пусть мы хотим вычислить ab mod n, где
а – вычет по модулю n, a b – целое
неотрицательное число, имеющее в двоичной
записи вид (bk,bk-1,... ,b1,b0) (число знаков
считаем равным k + 1; старшие разряды, как
обычно, слева). Мы вычисляем ас mod n для
некоторого с, которое возрастает и, в конце
концов, становится равным b.

36. При умножении с на 2 число ас возводится в квадрат, при увеличении с на 1 число ас умножается на a. На каждом шаге двоичная запись с сдвигается

на 1 влево, после
чего, если надо(bi=1), последняя цифра
двоичной записи меняется с 0 на 1. (3аметим,
что переменная с фактически не используется и
может быть опущена.)

37. Оценим время работы процедуры. Если три числа, являющиеся её исходными данными, имеют не более β битов, то число арифметических операций ес

Оценим время работы процедуры. Если
три числа, являющиеся её исходными
данными, имеют не более β битов, то число
арифметических операций есть О(β), а число
битовых – О (β 3).
Пример (а = 7, b = 560, n=561) показан на
рисунке.
Возведение в квадрат – это сдвиг на 1 влево
степени числа.

38.

i
9
8
7
6
5
4
3
2
1
0
bi
1
0
0
0
1
1
0
0
0
0
c
1
2
4
8
17
35
70
140
280
560
d
7
49
157
526
160
241
298
166
67
1
Рис. Работа процедуры возведение в
степень по модулю n
при a = 7, b = 560 = (1000110000) и n = 561.
Показаны значения переменных после
очередного исполнения тела цикла for.
Процедура возвращает ответ 1.

Тела группа, элементами к рой являются все ненулевые элементы данного тела, а операция совпадает с операцией умножения в теле. М. г. поля абелева группа. О. А. Иванова … Математическая энциклопедия

Приведённая система вычетов по модулю m множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(·) функция Эйлера. В качестве приведённой системы вычетов… … Википедия

Теория групп … Википедия

Группа в абстрактной алгебре непустое множество с определённой на нём бинарной операцией, удовлетворяющей указанным ниже аксиомам. Ветвь математики, занимающаяся группами, называется теорией групп. Всем знакомые вещественные числа наделены… … Википедия

Группа автоморфизмов нек рой полуторалинейной формы f на правом K модуле Е, где К кольцо; при этом f и Е(а иногда и К)удовлетворяют дополнительным условиям. Точного определения К. г. нет. Предполагается, что f либо нулевая, либо невырожденная… … Математическая энциклопедия

Группа всех обратимых матриц степени пнад ассоциативным кольцом K с единицей; общепринятое обозначение: GLn(K).или GL(n, К). П. л. г. GL(n, K) может быть также определена как группа автоморфизмов АutK(V) свободного правого K модуля Vс… … Математическая энциклопедия

Для общего описания теории групп см. Группа (математика) и Теория групп. Курсив обозначает ссылку на этот словарь. # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У … Википедия

В §1.1 было дано аксиоматическое определение поля, введены понятия и приведены примеры простого и расширенного поля.

Обобщением сказанного в §1.1 и §1.3 являются следующие определения:

1.Для простых полей:

2.Для расширенных полей:

К многочлену π (x),кроме требования неприводимости, предъявляется ещё одно принципиальное требование – ненулевые элементы поля являются степенями корня α многочлена π(x) .

Если ненулевые элементы поля GF(m ) могут быть представлены как степени некоторого элемента α, то α называют примитивным элементом этого поля.

В §1.1 было показано, что поле GF(2 2 ) в качестве ненулевых элементов имеет 1, α, 1+α, где α- корень π(x)=1+x+x 2 ,т.е.1+α+α 2 =0. Поскольку 1=α 0 , а 1+α=α 2 , то все ненулевые элементы GF(2 2 ) представляются степенями корня π(x) .Элемент α является примитивным элементом GF (2 2 ) , а π(х)=1+х+х 2 является примитивным неприводимым многочленом.

Рассмотрим поле GF(5). Поскольку 5- простое число, то кольцо классов вычетов по модулю 5 образует поле GF(5). Таблицы сложения и умножения по модулю 5 приведены в §1.3. Для этого поля также существует примитивный элемент, степени которого дают все ненулевые элементы поля. Например, 2 0 =1, 2 1 =2, 2 2 =4, 2 3 =8=3,2 4 =16=1,2 5 =32=2.

Эти примеры могут быть обобщены следующим образом. В любой конечной мультипликативной группе можно рассмотреть совокупность элементов, образованную некоторым элементом g и его степенями g 2 , g 3 и т.д. Так как группа имеет конечное число элементов,то неизбежно появится повторение, т.е. для некоторых i и j будет g i =g j .

Если наблюдается g i =g j , то g j - i =1. Следовательно, некоторая степень элемента g равна 1. Пусть e – наименьшее положительное число , при котором g e =1. Совокупность элементов 1, g, g 2 , ..., g e -1 образует подгруппу по операции умножения, т.к. налицо единичный элемент 1, замкнутость, наличие обратных элементов: для g i обратный элемент g e - i . Группа, состоящая из всех степеней одного из ее элементов получила, название циклической группы .

Число e называется порядком элемента g .

Обобщением изложенного выше является следующее:

Если мультипликативная группа порядка q содержит циклическую подгруппу из e элементов, порожденную некоторым элементом g, то число смежных классов в разложении группы по циклической подгруппе будет равно q/e и каждый смежный класс также будет содержатьe элементов. Значит справедливо следующее утверждение:

где φ (e ) – функция Эйлера , равная числу чисел взаимно простых с e и меньших e . Функция Эйлера может быть вычислена следующим образом:

если e – составное число вида e =
, гдеp i > 1 – простое, а l i – натуральное число и i = 1,2, ... t , то

φ(e ) =
.

В частности, для простого р и целого а

φ(р а )= р а - р а-1 , φ(р ) = р – 1.

Кроме того,

φ(а 1 ×а 2) = φ(а 1)φ(а 2),

если а 1 и а 2 взаимно просты.

Например:

φ(1) = 1, φ(4) = 2,

φ(2) = 1, φ(5) = 4,

φ(3) = 2, φ(6) = 2.

Пример1.4.1 . Определить число элементов Ni поля GF(2 6) порядка i = 1, 3, 7, 9, 21, 63.

Решение: Ni = φ(i), где φ(i) – функция Эйлера, для вычисления которой необходимо знать каноническое разложение числа i:

1=1, 3=3, 7=7, 9=3 2 , 21=3×7, 63=3 2 ×7.

Теперь находим:

N9 = φ(9) = 9(1-1/3) = 9×2/3 = 6,

N21 = φ(21) = 21(1-1/3)(1-1/7) = 21×2/3×6/7 = 12,или φ(21)=φ(3)φ(7)=2×6=12,

N63 = φ(63) = 63(1-1/3)(1-1/7) = 63×2/3×6/7 = 36.

Рассмотренные числа 1, 3, 7, 9, 21, 63 являются делителями числа 63 и поэтому определяют все возможные порядки элементов мультипликативной группы поля GF(2 6). Полученный результат может быть обобщен следующим образом:

Важным следствием из рассмотренного является следующее.Пусть а – примитивный элемент GF(p m) Порядок а равен p m -1, т.е α
=1.Если среди элементов поля GF(p m) есть элемент β порядка p r -1 , где r < m, т.е. βα,то последовательность элементов β 1 , β 2 , …,
=
, образует циклическую подгруппу мультипликативной группыGF(p m), т.е. содержит все ненулевые элементы нового поля GF(p r),являющегося подполем GF(p m).Итак,

В § 2.1 будет показано, что p r -1 делит p m -1,если r делит m. Таким образом, окончательно

Пример 1.4.2 .В качестве примера рассмотрим подполя поля GF(2 12). Число 12 делится на числа 6,4,3 и 2, т.е. в составе поля GF(2 12) существуют в качестве подполей поля GF(2 6), GF(2 4), GF(2 3), GF(2 2). Так как любое расширенное поле содержит основное поле, то в каждом из указанных полей содержится поле GF(2). Найдем циклические группы рассматриваемых полей. Обозначим примитивные элементы полей:

GF(2 12)→α,GF(2 6)→β,GF(2 4)→γ,GF(2 3)→δ,GF(2 2)→ε,GF(2)→ζ.

Выразим ненулевые элементы полей через степени примитивных элементов:

GF(2 12): α 1 , α 2 ,α 3 ,… ,α 4095 =α -1 =1= α 0 и порядок α равен 4095;

GF(2 6) : β 1 , β 2 ,β 3 ,… ,β 63 =β -1 =1=β 0 и порядок β равен 63; GF(2 4) : γ 1 , γ 2 ,γ 3 ,… ,γ 15 =γ -1 = 1=γ 0 и порядок γ равен 15; GF(2 3) : δ 1 , δ 2 ,δ 3 ,… ,δ 7 =δ -1 = 1=δ 0 и порядок δ равен 7; GF(2 2) : ε 1 , ε 2 ,ε 3 =ε -1 = 1=ε 0 и порядок ε равен 3; GF(2) : ζ 1 = ζ -1 =1 = ζ 0 и порядок ζ равен 1.

Элементы полей GF(2 6), GF(2 4), GF(2 3), GF(2 2) и GF(2) входят в состав GF(2 12). При этом β = α 65 , т.к. β 63 = α 4095 = 1 = (α 65) 63 . Аналогично γ = α 273 ,δ = α 585 , ε = α 1365 , ζ = α 4095 . Связь между рассмотренными полями иллюстрирует рис.1.1.

Рис.1.1. Поле GF(2 12) и его подполя

Глава.2.Многочлен Х n -1, его корни и неприводимые сомножители

2.1 .Связь между корнями Х n -1 и элементами поля GF ( q )

Многочлен Х n -1, его неприводимые сомножители и их корни играют существенную роль в построении важнейшего класса групповых кодов -циклических кодов. Знание корней сомножителей Х n -1 позволяет решить задачу выбора требуемого кода для конкретного дискретного канала.

Рассмотрим общий случай:

Пусть Х n -1 задан над полем GF(q). Известно, что GF(q) имеет циклическую группу из q-1 своих ненулевых элементов.

Порядок каждого ненулевого элемента GF(q) не может быть выше q-1, а это означает, что α q -1 =1 для любого ненулевого элемента α из GF(q),т.е. любой ненулевой элемент GF(q) обращает Х q -1 -1 в нуль, а, значит, является его корнем. Поскольку Х q -1 -1 имеет ровно q-1 корней, то, следовательно, все ненулевые элементы GF(q) являются корнями Х q -1 -1.

Таким образом,

В случае двоичных циклических кодов нас интересуют многочлены с корнями из расширенных полей Галуа GF(2 m). В соответствии с полученным выше результатом справедливо утверждение:

Важно уметь сопоставлять совокупности элементов GF(q), в частном случае GF(2 m), с корнями неприводимых сомножителей Х q -1 -1 (в двоичном случае с корнями Х -1 -1), ровно как и с корнями Х n -1 при произвольном n.

При выявлении сомножителей Х n -1 полезны следующие свойства, характеризующие связи между элементами GF(q) и многочленами, являющимися делителями Х n -1.

Свойство 1 . Наличие в двучлене Х n -1 сомножителей вида Х m -1, где m

Пусть n=m×d, где n, m и d-целые положительные числа. Рассмотрим двучлен У d -1.Очевидно, что при У=1 он обращается в нуль, и 1 является корнем У d -1.

Тогда по теореме Безу У d -1 делится на У-1.Положим, что У = Х m . Тогда, очевидно, Х md -1 делится на Х m -1.Таким образом, справедливо следующее:

Свойство 2. Поля Галуа GF(p m), образованные классами вычетов многочленов по модулю примитивного неприводимого над полем GF(p) многочлена π(x) степени m, называют полями характеристики р при любомвыборе m.В поле GF(p) элемент p=0.

В поле характеристики p для любых чисел a и b справедлива биноминальная теорема:

(a+b) p = a p + C a p-1 b + Ca p-2 b 2 +…+ b p ,

где C i p-биноминальные коэффициенты, вычисляемые по формуле:

Поэтому справедливо:

Свойство 3. Пусть многочлен f(x)=a0+a1x+...+amx m степени m неприводим в

поле GF(p). Рассмотрим (f(x)) p .

По предыдущему свойству:

(f(x)) p = (а 0) p +(a1x 1)+...+(amx m) p =

A0 p +a1 p (x p) ’ +...+am p (x p) m =

A0+a1(x p) ’ +...+am(x p) m = f(x p).

Этот результат получен в силу того, что для любого элемента a i из GF(p) справедливо: ai p -1 = 1 и ai p = ai.

Пусть β - корень f(x), тогда f(β) = 0.

В силу полученного результата (f(β)) p = f(β p) = 0, т.е. для любого корня β многочлена f(x) справедливо утверждение, что β p также является корнем f (x ). Так как неприводимый многочлен f (x ) степени m имеет всего m корней и один из его корней есть β, то m степеней β от р 0 =1 до p m -1 являются корнями f(x ), т. е. справедливо:

Если f (x ) - многочлен степени m с коэффициентами из поля GF (p ), неприводимый в этом поле, и β – корень f(x ), то β, β p ,…, β р
– все корниf (x ).

Свойство 4. Прямым следствием из свойства 3 является следующее:

Все корни неприводимого многочлена имеют один и тот же порядок.

Для доказательства этого свойства предположим, что корнями некоторого неприводимого многочлена f (x ) степени m является β, имеющий порядок e и β, имеющий порядокl . Тогда (β) e = (β e )=1, и поэтомуe делится на l . Аналогично, β l = (β) l =β
=((β) l )
=1
=1, так что l делится на e . .Поскольку e и l - целые положительные числа, то e = l , что и доказывает свойство 4.

Свойство 5. Выше было показано однозначное соответствие между ненулевыми элементами GF (p m ) и корнями двучлена Х
-1 . Определим вид многочлена, корнями которого являются все элементы поля GF (p m ). Пусть α – произвольный элемент поля порядка p m -1 . Тогда справедливо: α=α, т.е.α является корнем уравнения

х- х = 0.

Данный результат известен в литературе как теорема Ферма :

Любой элемент α поля GF ( p m ) удовлетворяет тождеству α=α или, эквивалентно, является корнем уравнения х- х = 0 .

Следствием теоремы Ферма является тот факт, что двучлен х- х может быть представлен в виде произведения p m сомножителей следующим образом:

где a i = GF (p m ), т. е. все элементы a i или GF (p m ) являются корнями двучлена х- х , причём каждый корень встречается только один раз.

Выше мы показывали, что элемент поля GF (p m ) α порядка p m -1 называется примитивным и любой ненулевой элемент поля являются степенью α , т. е. для ненулевых элементов a i справедливо a i = α i , где i принимает значение от 1 до p m -1.

Свойство 6.

Свойство 3 устанавливает связь между последовательностями корней неприводимого многочлена f (x ). Естественно считать что корень f (x ) – элемент расширенного поля GF (p m ). Какой может быть максимальная степень неприводимого многочлена с корнями из GF (p m ) или что тоже самое – какова максимальная степень неприводимого сомножителя х- х ?

Ответ на этот вопрос даёт анализ возможной максимальной степени в последовательности корней:

Удобно рассматривать последовательность степеней в выражении корня через примитивный элемент поля GF (p m ). Тогда приведённая выше последовательность корней однозначно соответствует последовательности степеней примитивного элемента:

{s ,

p 2 s ,

p 3 s ,…, p s}

где m s – наименьшее положительное число, такое, что p×s =s по модулю p m -1 . Модуль p m -1 отражает порядок примитивного элемента поля. В последовательности степеней корней следующая степень β=β , т.е.

Максимальная степень неприводимого многочлена в разложении - , равно как и в разложении многочлена - , равна m .

Последовательность, взятая в фигурные скобки, получившая название циклотомического класса, в зависимости от значения s может содержать m s ≤ m элементов. Число s, стоящее в начале циклотомического класса, получило название образующего или представителя циклотомического класса. Ниже будет показано, что число элементов в циклотомическом классе m s должно быть делителем числа m. Справедливо следующее:

Множество целых чисел, отображающих степени примитивного элемента α поля GF (p m ) в представлении ненулевых элементов поля в виде циклической группы распадается на подмножества, называемые циклотомическими классами по модулю p m -1. Каждый циклотомический класс однозначно соответствует одному из неприводимых сомножителей - .

Понятно, что:

Полное число циклотомических классов для поля GF (p m ) совпадает с числом неприводимых сомножителей многочлена - , и множество элементов, охватыаемых циклотомическими классами, отображает все ненулевые элементы поля GF (p m ).

Например, циклотомическими классами по модулю 15 для p =2 являются:

С 0(15) ={0 },

C 1(15) ={1 ,2 ,4 ,8 },

C 3(15) ={3 ,6 ,12 ,9 },

C 5(15) ={5 ,10 },

C 7(15) ={7 ,14 ,13 ,11 }.

Здесь С S (15) обозначает циклотомический класс по модулю 15, начинающийся с числа s .

Анализ приведённых последовательностей означает, что двучлен x 15 +1 над полем GF (2 ) состоит из 5 неприводимых сомножителей: одного сомножителя 1-ой степени с корнем порядка 1, одного сомножителя 2-ой степени с корнем порядка 3 и трёх сомножителей степени 4, два из которых имеют порядок корней 15, а один – имеет порядок корней 5. Результаты этого анализа показывают, что последовательность C 0(15) соответствует многочлену x +1; последовательность C 5(15) соответствует многочлену 2-ой степени с корнями порядка 3 – это многочлен x 2 + x +1 – неприводимый сомножитель двучлена x 3 +1; последовательность C 3(15) соответствует неприводимому сомножителю 4-ой степени двучлена x 5 +1= (x +1)( x 4 + x 3 + x 2 + x +1), отсюда и порядок корней равный пяти. Многочлены, соответствующие последовательностям C 1(15) и C 7(15) могут быть найдены на основе теоремы Безу:

f 1 (x )= (x + α ))(x + α 2 ))(x + α 4 ))(x + α 8 ),

f 7 (x )= (x + α 7 )(x + α 11 )(x + α 13 ))(x + α 14 ).

Анализ многочленов f 1 (x ) и f 7 (x ) будет выполнен ниже.

Свойство 7. Анализ неприводимых многочленов, входящих в разложение Х

, имеющих корни среди элементовGF(2 4) показывает, что степени всех неприводимых многочленов: 1, 2, 4 является делителями числа 4. Обобщим этот результат следующими рассуждениями.

Пусть f(х)- неприводимый сомножитель степени d ≤ m многочлена Х-Х и пусть β элемент порядкаp d -1 поля GF(p m), являющийся примитивным элементом подполя GF(p d) поля GF(p m), принадлежит циклической группе GF(p m) порядка p m -1.Следовательно p d -1 делит p m -1, а это возможно только в том случае, когда d делит m. Значит справедливо:

Свойство 8. Аналогичные рассуждения приводят к следующему утверждению:

Свойство 9.

Рассмотрим подробнее многочлены над GF(2):

f 1 (x ) = (x + α )(x + α 2 )(x + α 4 )(x + α 8 ),

f 7 (x ) = (x + α 7 )(x + α 11 )(x + α 13 )(x +2 14 ).

Корни этих многочленов являются элементами поля GF(2 4).С учетом правил сложения и умножения в этом поле простым умножением находим:

f 1 (x ) = 1+ x + x 4 ,

f 7 (x ) = 1+ x 3 + x 4 .

Многочлены f1(x) и f7(х) относятся к двойственным (взаимным) многочленам.

Многочлен f * (x), двойственный некоторому многочлену f (x), определяется как f * (x) = х m f(1/х), где m-степень f(x).

Для двойственных многочленов f * (x) и f(x) справедливо:

1.Корни f * (x) обратны корням f(x).

2.Многочлен f * (x) неприводим тогда и только тогда, когда неприводим f(x).

3.Если многочлен f(x) неприводим, то f(x) и f * (x) принадлежат к одному и тому же показателю.