Галуев Г.А. Математические основы криптологии

Подождите немного. Документ загружается.

[0]={..., –2n; -n, 0, n, 2n, ...}

[1]={..., -2n+1, -n+1, 1, n+1, 2n+1, ...}

[n -1]={..., -n -1, -1, n -1, 2n -1, 3n -1, ...}

Определение. Группа, образованная множеством { [0], [1],

... ,[n -1]} классов вычетов по модулю n с операцией

[a]+[b]=[a+b], называется группой классов вычетов по модулю

n и обозначается Z

Группа

является циклической с образующим элементом

[1] и имеет порядок n.

Определение. Группа называется конечной (бесконечной),

если она состоит из конечного (бесконечного) числа элементов.

Число элементов конечной группы

G называется ее порядком и

обозначается

Удобным способом задания конечной группы является их

представление в виде таблицы групповой операции (таблицы

Кэли), которая строится так: ее строки и столбцы помечаются

элементами группы и на пересечении строки, помеченной эле-

ментом

а и столбца, помеченного элементом b, ставится элемент

аb.

Пример:

Таблица Кэли группы

классов вычетов по модулю 6.

+ [0][1][2][3][4][5]

[0]

[1]

[2]

[3]

[4]

[5]

[0][1][2][3][4][5]

[1][2][3][4][5][0]

[2][3][4][5][0][1]

[3][4][5][0][1][2]

[4][5][0][1][2][3]

[5][0][1][2][3][4]

Эта группа Z

представляет собой:

Пусть

G - множество остатков {0, 1, 2, 3, 4, 5} от деления

целых чисел из

Z на 6 и для чисел а и b из G величина а*b пусть

остаток от деления на

6 обычной суммы а + b. Тогда получим

группу

Каждая группа содержит некоторые подмножества , кото-

рые сами образуют группу с той же групповой операцией.

Определение. Подмножества Н группы G называется под-

группой этой группы, если

Н само образует группу относитель-

но операций группы.

Примером группы является следующее определение.

Определение. Подгруппа группы G ,состоящая из всех

степеней элемента

а этой группы, называется подгруппой, по-

рожденной элементом а и обозначается <а>.

Если подгруппа

<а> конечна, то ее порядок называется по-

рядком элемента а. а

, а

, ... а

Приведем следующую теорему, доказательство которой

тривиально.

Теорема. Если Н - подгруппа группы G, то отношение R

на

G определяемое условием

(а,b)

∈

R↔a=bh

для некоторого

∈

H, является отношением эквивалентно-

сти.

Соответствующие отношению

классы эквивалентности

называются

левыми смежными классами группы G по под-

группе

H и обозначаются

aH={ah

∈

H} для мультипликативной группы

или

a + H ={a+h

∈

H} для аддитивной группы

где

а – фиксированный элемент группы G.

Аналогично определяется разбиение группы

G на правые

смежные классы по подгруппе

Ha={ha

∈

H}.

Если

G – абелева группа, то ее левые смежные классы по

подгруппе

H совпадают с правыми, а сама подгруппа Н нор-

мальная.

Пример.

Пусть G

={[0],[1],[2],...,[11]} и пусть H подгруппа

H={[0],[3],[6],[9]}. Тогда различными (левыми) смежными

классами

G по H являются

[0] + H = {[0],[3],[6],[9]}

[1] + H = {[1],[4],[7],[10]}

[2] + H = {[2],[5],[8],[11]}.

Теорема. Если H - конечная подгруппа группы G, то каж-

дый (левый или правый) смежный класс группы

G по подгруппе

H содержит столько же элементов, сколько H.

Определение. Если подгруппа H группы G такова, что

множество смежных классов

G по H конечно, то число этих

смежных классов называется

индексом подгруппы H в группе G

и обозначается

(G:H).

Так как левые смежные классы группы

G по подгруппе H

образуют разбиение этой группы, то из указанной выше теоремы

вытекает следующий важный результат.

Теорема. Порядок конечной группы G равен произведению

порядка любой её подгруппы

H на индекс (G:H) этой подгруппы

В частности, порядок любой подгруппы

H группы G и её

индекс в

G делят порядок группы G. Порядок любого элемента

∈

G делит порядок группы G.

Результаты относящиеся к подгруппам и порядкам элемен-

тов для циклических групп можно обобщить следующей теоре-

мой

Теорема

1. Каждая подгруппа циклической группы также является

циклической.

2. В конечной циклической группе <a> порядка m элемент

порождает подгруппу порядка

),( mKНОД

3. Если d положительный делитель порядка m конечной

циклической группы

<a>, то <a> содержит единственную под-

группу индекса

d. Для любого положительного делителя l числа

m группа

<a> содержит в точности одну подгруппу порядка l.

4. Пусть l положительный делитель порядка конечной цик-

лической группы

<a>. Тогда <a> содержит

(l) элементов по-

рядка

l. (Напомним, что

(l) – функция Эйлера: число целых чи-

сел

lK ≤≤1

, взаимно простых с числом l).

5. Конечная циклическая группа <a> порядка m содержит

(m) образующих (т.е. таких элементов a

, что <a

> = <a>). Об-

разующими являются те и только те степени

элемента а, для

которых

(r,m)=1 (т.е. r и m взаимно простые числа).

В большинстве числовых систем, используемых в элемен-

тарной арифметике, имеются две различные бинарные операции:

сложение и умножение. Примерами могут служить целые, ра-

циональные и действительные числа. Поэтому в абстрактной ал-

гебре были введены алгебраические структуры, которые обла-

дают основными свойствами указанных числовых систем. К та-

ким

алгебраическим структурам относятся кольца и поля.

Кольца. Поля.

Определение. Кольцом R называется множество R с двумя

бинарными операциями, обозначаемыми

+ или

⋅

такими, что:

R – абелева группа относительно операции + (т.е. вы-

полняется коммутативный закон сложения

a+b=b+a)

Операция

⋅

ассоциативна т.е. для любых a, b, c

∈

→

⋅

c = a

⋅

Выполняются законы дистрибутивности:

∀

a, b, c

∈

справедливо

⋅

(b + c) = ab + ac; (b + c)

⋅

a = ba + ca.

Здесь операции

+ и

⋅

не обязательно являются обычным

сложением и умножением. Единичный элемент аддитивной

группы кольца

K называется нулем и обозначается 0, а обратный

к элементу

a этой группы обозначают –a. Для кольца выполня-

ются по определению свойства:

a ⋅ 0 = 0 ⋅ a = 0 для всех a ∈ R

( -a) ⋅ b = a ⋅ ( -b) = -ab для всех a,b ∈ R.

Кольцо называется кольцом с единицей, если оно имеет

мультипликативную единицу, т.е. существует такой элемент

∈

R, что a

⋅

e = e

⋅

a = a для всех

∀

∈

Кольцо называется

коммутативным, если операция ⋅

коммутативна

⋅

b = b

⋅

Кольцо называется

целостным кольцом (или областью

целостности), если оно является коммутативным кольцом с

единицей

≠

0, в котором равенство a

⋅

b = 0 влечет за собой a=0

или

b=0.

Кольцо R называется

телом если R

≠

{0} и ненулевые эле-

менты в

R образуют группу относительно операции

⋅

. Другими

словами

тело – это кольцо с единицей, в котором для каждого

элемента

≠

0 существует обратный по умножению элемент a

-1

такой, что

⋅

-1

)=1.

Полем называется тело, операция

⋅

в котором коммутатив-

на, т.е.

⋅

b = b

⋅

Поскольку основной алгебраической структурой, которая

будет использоваться в дальнейшем, является поле, рассмотрим

более подробно его определения.

Поле есть множество

F на котором заданы две операции,

называемые сложением + и умножением

⋅

, и которое содержит

два выделенных элемента

0 и е, причем 0

≠

е. Поле это абелева

группа по сложению, единичным элементом которой является

а элементы из

F отличные от нуля, образуют абелеву группу по

умножению, единичным элементом которой является

е. Опера-

ции сложения и умножения в поле связаны законом дистрибу-

тивности

a(b+c)=ab+ac. Второй закон дистрибутивности

(b+c)a=ba+ca выполняется автоматически в силу коммутативно-

сти операции умножения. Элемент

0 называется нулевым, а эле-

мент

е – единицей т.е. е=1.

Свойство поля, появляющееся из определения целостности

кольца, т.е. равенство

⋅

b=0 влечет a=0 или b=0, выражают сло-

вами «отсутствуют делители нуля». Другими словами в комму-

тативном кольце ненулевой элемент

а называют делителем ну-

ля, если существует другой ненулевой элемент b такой, что

⋅

b=0. Если в кольце нет делителей нуля, то оно называется

кольцом без делителей нуля или областью целостности. Ни-

какой делитель нуля не может иметь обратного по умножению

элемента. Поэтому никакое поле и тело не содержат делителей

нуля.

Определение. Подмножество S кольца R называется под-

кольцом этого кольца, если оно замкнуто относительно опера-

ций

+ и

⋅

и образует кольцо относительно этих операций. (Замк-

нутость - это условие когда результат операций

a+b и a

⋅

b над

a,b

∈

S также

∈

S).

Определение. Подмножество J кольца R называется идеа-

лом этого кольца, если оно является подкольцом кольца R и для

всех

∈

J и r

∈

R имеет место ar

∈

J, ra

∈

Например.

Пусть R - поле рациональных чисел (вида

, ba, - целые числа, 0

≠

b ). Тогда множество целых чисел Z

(вида

–n,n,0, n – целые числа >0) является его подкольцом, но не

идеалом т.к., например

a=1

∈

Z, r=1/2

∈

R, но a

⋅

r=1

⋅

1/2=1/2

∉

Так как идеалы являются нормальными (левые смежные

классы совпадают с правыми) подгруппами аддитивной группы

кольца, то каждый идеал

J кольца R определяет некоторое раз-

биение множества

R на смежные классы по аддитивной под-

группе

J, называемые классами вычетов кольца R по модулю

идеала

J. Класс вычетов кольца R по модулю J, содержащий

элемент

∈

R обозначают через [a]=a+J, т.к. он состоит из всех

элементов

R вида a+c, где c

∈

J. Элементы a,b

∈

R, принадлежа-

щие одному и тому же классу вычетов по модулю

J (т.е. такие,

что

a -b

∈

J), называют сравнимыми по модулю J и обозначают

≡

b(mod J). Для них справедливо:

Если

a≡b(mod J), то a+r≡b+r(mod J), ar≡br(mod J)

ra≡rb(mod J), na≡nb(mod J) ∀ n∈Z, r∈R.

Если кроме того r≡s mod J), то a+r≡b+s(mod J) и ar≡bs(mod

J).

Множество классов вычетов кольца

R по модулю идеала J

образует кольцо относительно операций

+ и

⋅

. Эти операции оп-

ределяются равенствами:

(

a+J)+(b+J)=(a+b)+J(1)

(

a+J)⋅(b+J)=ab+J(2)

Определение. Кольцо классов вычетов кольца R по моду-

лю идеала

J относительно операций (1), (2) называется фактор-

кольцом кольца R по идеалу J и обозначается R/J.

Пример.

Факторкольцо (или кольцо вычетов) Z/(n). Как и в

случае, когда мы рассматривали группы, обозначим класс выче-

тов по модулю

n (n

∈

N) содержащий число a

∈

Z через [a]. Этот

класс может быть записан в виде

a+(n), где (n) идеал, порожден-

ный числом

n. Тогда элементами факторкольца Z/(n) будут

[0]=0+(n), [1]=1+(n), ... , [n -1]=n -1+(n).

Теорема. Факторкольцо Z/(p) кольца Z целых чисел по

главному идеалу, порожденному простым числом

Р, является

полем.

Идеал

J кольца R называется главным, если существует

элемент

∈

R, такой что J=(a). Здесь, для коммутативного кольца

R, величина (a)={ra+na

∈

R, n

∈

Z} - наименьший идеал, содер-

жащий данный элемент

∈

R. Если кольцо имеет единицу, то (a)

={ra

∈

R} ((a) - главный идеал).

Пример.

Пусть p=3 простое число. Тогда факторкольцо со-

стоит из трех элементов

[0],[1],[2]. Операции в этом кольце

можно задать таблицами, аналогичными таблицам Кэли конеч-

ных групп

+ [0][1][2]

⋅

[0][1][2]

[0]

[1]

[2]

[0][1][2]

[1][2][3]

[2][3][4]

[0]

[1]

[2]

[0][0][0]

[0][1][2]

[0][2][1]

Приведенный пример является первым рассматриваемым

нами образцом

конечного поля, т.е. поля, содержащего конечное

число элементов, которые играют основную роль в современной

криптографии.

5. Элементы теории конечного поля. Основные

понятия и теоремы.

Поле.

Определение. Отображение

: R

→

S кольца R в кольцо S

называется

гомоморфизмом, или для любых a,b

∈

(a+b)=

(a)+

(b) и

(ab)=

(a)

(b).

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

: R

→

S сохраняет обе опе-

рации

+ и

⋅

. кольца R.

Определение. Для простого числа Р обозначим через F

множества

{0,1,2,...,P -1} целых чисел, и пусть отображение

Z/p

→

определяется условием

([a])=a для a=0,1,2,...,P -1. То-

гда множество

со структурой поля, индуцированной отобра-

жением

, называется полем Галуа порядка P. (Такое поле еще

обозначают

GF(p) – аббревиатура от слов Galois и Field(поле)).

Отображение

: Z/p

→

является изоморфизмом т.к.

([a]+[b])=

([a])+

([b]) и

([a]

⋅

[b])=

([a])

⋅

([b]). Нулем

конечного поля

будет 0 ноль, а единицей – единица 1 и его

структура совпадает со структурой поля

Z/p.

Пример.

Важным является пример конечного поля GF

второго порядка. Элементами этого поля являются

0 и 1 - бинар-

ные элементы, для которых выполняются операции

⊕

0 1

⋅

0 1

1 0

0 0

0 1

В связи с использованием для вычислений ЭВМ не менее

важным является поле Галуа из элементов

{0,1}, обозначаемое

GF(2

) и соответствующие строкам данных длиной N бит. Такие

строки бит удобно рассматривать в виде многочленов. Напри-

мер, байт из 8 бит можно представить

(10010101)=x

+1.

Определение. Пусть R произвольное кольцо. Если сущест-

вует такое натуральное число

n, что для каждого r

∈

R выполня-

ется равенство

⋅

r=0, то наименьшее из таких чисел n (напри-

мер,

) называется характеристикой кольца R, а само R назы-

вают

кольцом характеристики n

Теорема. Если кольцо R

≠

{0} с единицей е и без делителей

нуля имеет положительную характеристику

n, то n – простое

число.

Следствие. Характеристикой конечного поля является

простое число.

Теорема. Пусть R – коммутативное кольцо простой харак-

теристики

p. Тогда

nnn

PPP

baba +=+ )( ;

nnn

PPP

baba −=− )( ;

Rba

∈

∀

и Nn

∈

Выясним теперь, каким должен быть идеал

М коммутатив-

ного кольца

R с единицей, чтобы фактор -кольцо R/M было по-

лем.

Пусть

R – коммутативное кольцо с единицей. Элемент a

∈

называется делителем элемента

∈

R, если существует элемент

∈

R такой, что ас=b. Делители единицы

(

)

называются об-

ратимыми элементами a

-1

. Элементы a и b из R называют ас-

социированными, если

∃

обратимый элемент r

∉

R такой, что

a=br. Элемент c

∈

R называется простым элементом кольца R, ес-

ли он не является обратимым элементом и не имеет других де-

лителей, кроме ассоциированных с ним элементов или обрати-

мых элементов. Идеал

≠

R кольца R называют простым идеа-

лом, если для a,b

∈

R включение a

⋅

∈

P имеет место лишь в том

случае, когда либо

∈

P, либо b

∈

P. Идеал M

≠

R кольца R называ-

ется

максимальным идеалом, если

∀

идеала J кольца R вклю-

чение

JM ≤ влечет за собой J=M или J=R. Кольцо R называют

кольцом главных идеалов, если оно является целостным коль-

цом, и каждый идеал

J кольца R является главным, т.е.

∃

эле-

мент

∈

R такой, что J=(a)={ra

∈

R}.

Как уже указывалось на прошлых лекциях, важную роль в

криптографических приложениях играют многочлены и наибо-

лее важные и интересные результаты по ним получены в теории

конечного поля.

Напомним, что

многочленом называется выражение вида

∑

=+++=

xaxaxaaxf

...)(

где

n – целое неотрицательное число – степень многочле-

на,

– элементы кольца (коэффициенты многочлена),

x – переменная или неизвестная не принадлежащая кольцу.

Следует отметить, что при обычном определении много-

члена связь между коэффициентами

и переменной x обычно

не обсуждается. Однако такая связь существует и возможно ее

показать в рамках абстрактной алгебры, давая определение мно-

гочлена как элемента кольца многочленов.

Определение. Кольцо S, образованное многочленами над

кольцом

R, называется кольцом многочленов над R и обознача-

ется

R[x].

Рассмотрим множество

S всех бесконечных последова-

тельностей вида

,...,a

,...), компонентами a

которого явля-

ется элементы коммутативного кольца

R с единицей 1, причем

лишь конечное число компонент

может быть отлично от 0.

Это множество образует коммутативное кольцо с единицей от-

носительно операций

+ и

⋅

. Кольцо R таким образом можно рас-

сматривать как подкольцо кольца

S, а S – как расширение кольца

R. Элементами кольца S являются многочлены ][)( xRxf ∈ , оп-

ределяемые как бесконечные последовательности с конечным

числом ненулевых элементов.

При этом переход от кольца

R к кольцу многочленов S над

R называется кольцевым присоединением элемента x к кольцу

R. Таким образом, отображается связь между элементами кольца

R (коэффициентами многочлена a

) и новым элементом x.

В дальнейшем изложении в основном будем иметь дело с

многочленами над полями

F, поэтому для кольца многочленов

над полем

F будем использовать обозначение F[x] или G F[x].

Для кольца многочленов над полем справедливы операции

⋅

, сравнения, деления с остатком, делимость:

Два многочлена

)(xf и )(xg

∈

F[x] над полем F считают-

ся

равными тогда и только тогда, когда

∑

xaxf

)(,

∑

xbxg

)(, и

для ni ≤≤

∀

0 .

Сумма многочленов )(xf и )(xg определяется равенством

∑

+=+

xbaxgxf

)()()(,

произведение многочленов

∑

xaxf

)(

∑

xbxg

)(

∑

xcxgxf

)()(,

∑

kji

iik

bac njmi

≤

0,0.

Деление: многочлен g(x)

∈

F[x] делит многочлен f(x)

∈

F[x]

если существует

h(x)

∈

F[x] такой, что f(x)=g(x)

⋅

h(x).

Деление с остатком. Пусть g(x)

≠

0 – многочлен из F[x]

над полем

F. Тогда для каждого f(x)

∈

F[x] существуют такие

многочлены

q(x) и r(x)

∈

F[x], что

f(x)=q(x)⋅g(x)+r(x) (deg(r)<deg(g).

Простые элементы кольца многочленов F[x] обычно назы-

вают

неприводимыми многочленами.

Определение: Многочлен f(x)

∈

F[x] называется неприво-

димым над полем F или в кольце F[x], если он имеет положи-

тельную степень и равенство

f(x)=g(x)

⋅

h(x); g(x),h(x)

∈

F[x] мо-

жет выполнятся лишь в том случае, когда либо

g(x), либо h(x)

являются

постоянными многочленами (т.е. имеют степень

0≤n и являются константами).

Неприводимость многочлена существенным образом зави-

сит от того, над каким полем он рассматривается.

Примеры:

Многочлен f(x)=x

-2

∈

Q неприводим над полем рацио-

нальный чисел

Q, но приводим над полем действительных чисел

R т.к. )2)(2(2

+−=− xxx .

Многочлен f(x)=x

+x+1 неприводим над полем Галуа

GF(r) т.к. f(0)=f(1)=1, но приводим над его расширением GF(4).

Неприводимые многочлены играют важную роль в устрой-

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

F[x] может быть пред-

ставлен, причем единственным способом, в виде произведения

неприводимых многочленов. Эти неприводимые многочлены

являются, по сути дела, аналогами простых чисел, через произ-

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

n>1

(

основная теорема арифметики).

В нашем дальнейшем изложении применительно к крипто-

системам особенный интерес будут представлять многочлены

неприводимые степени

n над простыми полями F

порядка p, где

p – простое число. Поиск всех неприводимых многочленов за-

данной степени

n над некоторым полем F

или GF(p) представ-

ляет собой очень сложную задачу. Французский математик Эва-

рист Галуа (1811 -1832гг) создал теорию (теорию поля Галуа),

доказывающую существование неприводимых многочленов

сколь угодно большой степени, но поиск таких многочленов -

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

ведут активную работу по поиску таких многочленов, но эти ра-

боты засекречены. Известен

неприводимый многочлен степени

+ x

+1, а для n>61 данных найти не удалось. Чтобы более

подробно осветить вопросы нахождения неприводимых много-

членов над конечными полями, вопросы разложения многочле-

нов на множители над конечными полями и связанные с ними

проблемы построение линейных рекуррентных последователь-

ностей над конечными полями, которые лежат в основе построе-

ния современных криптосистем, продолжим знакомство

с ос-

новными понятиями и элементами теории конечного поля.

Определение. Пусть F – произвольное поле и f(x)

∈

F[x].

Тогда замена переменной

x в многочлене f(x) произвольным

элементом

∈

F обращает этот многочлен в корректно опреде-

ленный элемент поля

F. Если f(x)=a

x+...+a

∈

F[x] и b

∈

то, заменяя

x на b, получаем элемент f(b)=a

b+...+a

∈

Элемент

f(b) называют значением многочлена f(x) при x=b. Если

в кольце

F[x] имеется какое -либо полиномиальное равенство, то

заменяя в нем

x на b

∈

F, получаем равенство в поле F. (Принцип

подстановки). Тогда: элемент

∈

F называют корнем (или ну-

лем) многочлена f(x)

∈

F[x], если при x=b f(b)=0.

Теорема

(устанавливает связь между корнями и де-

лимостью

). Элемент b

∈

F является корнем многочлена

f(x)

∈

F[x] тогда и только тогда, когда многочлен x -b делит f(x)

(т.е.

x -b

f(x)).

Определение. Пусть b

∈

F - корень многочлена f(x)

∈

F[x].

Кратностью корня b называют такое натуральное число

K=(1,2,...), что f(x) делится на (x -b)

, но не делится на (x -b)

K+1

При

K=1 корень называют простым, а при K>1 – кратным.

Определение. Производной многочлена

f(x)=a

x+a

+...+a

∈

F[x] называется многочлен

f’(x)=a

+2a

x+...+na

n -1

∈

F[x]. Отсюда следует теорема.

Теорема. Корень b

∈

F многочлена f

∈

F[x] является крат-

ным тогда и только тогда, когда он одновременно является и

корнем производной

f’(x) многочлена f(x).

Существует связь между отсутствием или несуществова-

нием корней и неприводимостью многочленов. Если

f(x) - не-

приводимый многочлен из

F[x] степени n

≥

2, то согласно теоре-

ме

он не имеет корней в поле F. Обратное утверждение спра-

ведливо только для многочленов степени

2 и 3.

Теорема. Для неприводимости многочлена f(x)

∈

F[x] сте-

пени

2 и 3 в кольце F[x] необходимо и достаточно, чтобы он не

имел корней в поле

Пример:

Пользуясь этой теоремой, можно найти неприво-

димые многочлены степени

2 и 3 в кольце F

[x] над конечным

полем

, путем исключения из всей совокупности многочленов

указанной степени, принадлежащих кольцу

[x], тех многочле-

нов, которые имеют корни в поле

. Напомним, что элементами

поля

или GF(r) являются {0,1}. Тогда очевидно, что в кольце

[x] имеется только один неприводимый многочлен степени 2:

f(x)=x

+x+1 и два неприводимых многочлена степени 3:

f(x)=x

+x+1, x

+1.

Действительно: многочлены степени 2 – это

+1,

+x, f

+x+1.

Подставляя в них вместо

x элементы в поля GF(r), т.е. 0

или

1, видно, что f

=0 при x=1, f

=0 при x=1 и x=0, а f

≠

0 при

любом

∈

{0,1}. Тоже самое и для многочленов степени 3:

+x+1, f

+1, f

+x+1, f

+x, f

…

Наряду с многочленами

f(x) от одной переменной х, рас-

сматривают многочлены от нескольких переменных. Пусть

R -

коммутативное кольцо с единицей, и пусть

,...,х

символы, ко-

торые выступают в качестве переменных, образуем сначала

кольцо многочленов

R[x

], затем кольцо R[x

]=R[x

]R[x

] и

т.д. пока не получим

R[x

,...,x

]=R[x

,...,x

n -1

]R[x

]. Элементами

кольца

R[x

,...,x

] являются выражения

f(x

,...,x

∑

i1...in

...x

с коэффициентами а

i1...in

∈

R, причем суммирование распро-

страняется на конечное множество

n наборов (i

,...,i

) неотрица-

тельных целых чисел и соблюдается соглашение

=1, 1

⊆

Такое выражение называют

многочленом от переменных

,...,х

над кольцом R. Два многочлена f и g из R[x

,...,x

] равны,

когда равны все соответствующие коэффициенты. При этом

предполагается, что переменные

,...,х

перестановочны друг с

другом, так что, например, выражения

и х

отожде-

ствляются.

Определение. Пусть многочлен f(х

,...,х

)

∈

R[x

,...,x

] за-

дан выражением

f(x

,...,x

∑

i1...in

...x

Если a

i1...in

≠

0,то a

i1...in

...x

называется членом много-

члена

f(x

,...,x

), а i

+...+i

- степенью этого члена. Степень мно-

гочлена

f(x

,...,x

) (deg(f)) определяется как наибольшая из сте-

пеней его членов. Для

f(x

,...,x

)=0 полагают deg(f)= -

∝

. Если

f(x

,...,x

)=0 и все члены f имеют одну и туже степень, то много-

член

f называют однородным.

Определение. Многочлен f(x

,...,x

)

∈

R[x

,...,x

] называется

симметрическим, если для любой перестановки i

+...+i

целых

чисел

1,...,n выполняется равенство

f(x

,...,x

)= f(x

,...,x

Введем несколько понятий, связанных с расширением по-

лей, о котором мы немного говорили ранее.

Пусть

F поле. Подмножество К поля F, которое само явля-

ется полем относительно операций поля

F, называется его под-

полем. В этом случае поле F называется расширением поля К.

Если K

≠

F, то К – собственное подполе поля F.

Если

К - подполе конечного поля F

при простом Р, то оно

должно по определению содержать элементы

0 и 1, а значит, и

все другие элементы поля

в силу замкнутости поля К по сло-

жению. Следовательно, поле

не имеет собственных подполей,

отсюда следующее определение: поле, не содержащее собствен-

ных подполей называется

простым полем. Любое конечное по-

ле

порядка Р при простом Р есть простое поле.

Определение. Пусть К - подполе поля F и М – любое под-

множество поля

F. Тогда поле К(М) определим как пересечение

всех подполей поля

F, содержащих одновременно К и М: оно

называется

расширением поля К, полученным присоединением

элементов множества

М. В случае конечного множества

М={

1,...,

} будем писать К(М)=К(

1,...,

). Если М состоит из од-

ного элемента

θ∈

F, то поле L=K(

) называют простым расши-

рением поля К, а элемент

θ∈

F - образующим элементом про-

стого расширения

L поля К.

Определение. Пусть К – некоторое подполе поля F и

θ∈

Если

удовлетворяет нетривиальному полиномиальному урав-

нению с коэффициентами из поля

К, т.е. если a

+...+a

=0,

где элементы

лежат в К и не равны нулю одновременно, то

элемент

называется алгебраическим над К. Расширение L по-

ля

К называется алгебраическим расширением поля К, если ка-

ждый элемент поля

L является алгебраическим над К.

Одним из наиболее фундаментальных результатов, отно-

сящимся к понятию расширения полей является

теорема Кро-

нежра:

Пусть многочлен f(x)

∈

K[x]неприводим над полем К. То-

гда существует простое алгебраическое расширение поля

К, об-

разующим элементом которого является некоторый корень

f(x).

Эта теорема гарантирует для любого неприводимого над

полем

F существование такого расширения поля F, в котором

этот многочлен имеет корень.

Рассмотрим теперь вопросы строения конечных полей,

опишем их основные свойства и методы построения.

6. Элементы теории конечного поля. Строение

конечных полей. Основные свойства и методы

построения конечных полей.

Из предыдущих лекций вспомним, что для каждого про-

стого числа

Р фактор кольцо Z/(р) является конечным полем, со-

стоящим из

Р элементов, которое отождествляют с конечным

полем Галуа

или GF(p) порядка р. Эти поля играют важную

роль в теории полей, так как каждое поле характеристики

должно содержать изоморфное

подполе и потому может рас-

сматриваться как расширение поля

р.

Рассмотрим вопрос о числе элементов конечного поля.

Лемма 1. Пусть F - конечное поле, содержащее подполе К

из

q элементов. Тогда F

состоит из q

элементов, где m=[F:K].

Здесь

[F:K] обозначает степень поля F над К, т.е. размер-

ность пространства

F над К. Если рассматривать F как вектор-

ное пространство над полем

К.

Теорема. Пусть F - конечное поле. Тогда оно состоит из р

элементов, где

р простое число, являющееся характеристикой

поля

F, а n - натуральное число, являющееся степенью поля F

над его простым подполем.

Доказательство этой теоремы достаточно простое и при-

водится, чтобы вспомнить материал прошлой лекции. Так как

поле

F конечно, то его характеристика есть некоторое простое

число

р. Поэтому простое подполе К поля F изоморфно F

значит содержит

р элементов и, следовательно, согласно лемме

1, поле

F содержит р

элементов.

Лемма 2. Если F - конечное поле из q элементов, то каж-

дый элемент

∈

F удовлетворяет равенству а

=а.

Лемма 3. Если F - конечное поле из q элементов и К - под-

поле поля

F, то многочлен x

-x из К[х] вполне разлагается в

F[х] следующим образом

-x=

(х -а), а

∈

так что F является полем разложения многочлена x

-x

над полем

К.

На основе представленных лемм можно сформировать

главную характеризационную теорему конечных полей.

Теорема о существовании и единственности конечных

полей. Для каждого простого числа р и каждого натурального

числа

n существует конечное поле из р

элементов. Любое ко-

нечное поле из

q=р

элементов изоморфно полю разложения x

x над полем F

Эта теорема позволяет ввести в рассмотрение т.е. постро-

ить конкретное конечное поле Галуа порядка

q, содержащее q

элементов, где

q - это степень простого числа р, которое являет-

ся характеристикой этого поля. Поля этого типа обозначают

или

GF(q).

Для конечного поля

F(q) будем обозначать через F

(q)

мультипликативную группу его ненулевых элементов. Тогда

следующая теорема устанавливает важное свойство такой груп-

пы.

Теорема. Мультипликативная группа F

(q) ненулевых эле-

ментов произвольного конечного поля

является циклической,

с образующим элементом

∈

Определение. Образующий элемент b

∈

циклической

группы

называется примитивным элементом поля F

Теорема. Пусть F

– конечное поле и F

его конечное рас-

ширение. Тогда

является простым алгебраическим расшире-

нием поля

, причем образующим элементом этого простого

расширения может служить любой примитивный элемент поля

Отсюда имеет место важное

следствие: Для каждого ко-

нечного поля

и каждого натурального числа n в кольце F

[x]

существует неприводимый многочлен f(x) степени n.

Рассмотрим теперь вопрос о множестве корней неприво-

димого

многочлена над конечным полем. На этот важный во-

прос дают ответ следующие теоремы конечного поля.

Лемма. Пусть f

(x)

∈

[x] - неприводимый многочлен сте-

пени

m над F

Тогда f

(x)

делит многочлен

a -x тогда и только

тогда, когда число

m делит n (т.е. m/n).

Теорема Галуа. Если f

(x)

∈

[x] неприводимый многочлен

степени

m, то в поле F

содержится любой корень, а многочле-

на

f(x). Более того, все корни многочлена f(x) просты (напом-

ним, что корень простой, если его кратность

к=1) и ими являют-

ся m различных элементов

a ,

a ,...,

1−m

a поля F

Из этой теоремы следуют следующие факты:

Неприводимый многочлен f

(x)

∈

[x] над полем F

вполне разлагается в этом поле, т.е. (см. лемму 3). Поле

яв-

ляется полем разложения над полем

Поля разложения любых двух неприводимых много-

членов одной и той же степени из кольца

[x] изоморфны.

Каждое конечное расширение F

конечного поля F

является

нормальным расширением, т.е. оно обладает тем свой-

ством, что каждый неприводимый многочлен из

[x], имеющий

хотя бы один корень в поле

разлагается в этом поле на ли-

нейные сомножители.

Любое конечное поле является совершенным полем,

т.е. обладает следующим свойством: каждый неприводимый

многочлен над этим полем имеет лишь простые корни.

Определим теперь ряд понятий, которые потребуются для

дальнейшего изучения основных элементов теории конечного

поля.

Определение. Пусть F

расширение поля F

, и пусть

∈

. Тогда элементы

a ,

a ,...,

1−m

a называются сопря-

женными с элементом a относительно F

Пусть

К=F

= F

(т.е конечное расширение F конечно-

го поля

K это векторное пространство над K). Тогда размерность

F над K равна m, и если {a

, ..., a

} базис пространства F над

полем

K или базис поля F над K, то каждый элемент a

∈

F одно-

значно представим в виде линейной комбинации

a=c

+...+ c

, c

∈

K, mj

≤

1 .

Тогда можно ввести важную функция из F в K, которая

также является линейной.

Определение. Пусть K=F

, F=F

и a

∈

F. Тогда определим

след )(

элемента a над равенством

...)(

−

++++=

qqq

aaaaaT

Если

K простое подполе поля F, то )(

называют аб-

солютным следом элемента a и обозначают )(aT

Иными словами

след )(

элемента а над полем K есть

сумма всех сопряженных с

а относительно K элементов.

Дадим

еще одно определение следа. Пусть f(x)

∈

K[x] ми-

нимальный многочлен элемента

∈

F над полем K. Его степень d

является делителем числа

m. Назовем многочлен g(x)=f(x)

m/d

из

K[x] характеристическим многочленом элемента а над полем

К. Согласно представленной выше теореме Галуа корнями мно-

гочлена

f(x) в поле F являются элементы

,...,,

−d

aaa , поэтому

получаем, что корнями многочлена

g(x) в поле F являются эле-

менты, которые сопряжены с элементом а относительно поля

Отсюда

))...()((...)(

−

−−−=+++=

−

qqm

axaxaxaxaxxg

и сравнение коэффициентов дает

)(

−

aaT

Этот след всегда является элементом поля

К.

Определение. Для a

∈

F=F

и K=F

определим норму

F/K

(a) элемента а над полем К равенством

)1/()1(

...)(

−−

=⋅⋅⋅⋅=

qqqqq

aaaaaaN .

Через свободный член

a характеристического многочлена

элемента

а над полем К:

)1()( aaN

−= .

Определение. Пусть К конечное поле и F его конечное

расширение. Тогда два базиса {

,...,a

} и {b

,...,b

} поля F над

К называется дуальными, если для mji

≤

≤ ,1

⎩

⎨

⎧

≠

baN

iir

)(

Определение. Пусть K=F

и F=F

. Тогда базис поля F над

К вида },...,,,{

12 −m

qqq

aaaa состоящий из подходящим образом

выбранного элемента

∈

F и сопряженных с ним относительно

поля

К элементов, называют нормальным базисом поля F над К.

Пример:

Пусть a

∈

корень неприводимого многочлена

+1 из F

[x]. Тогда {a,a

,(1+a+a

)} - базис поля F

над F

Однозначно определенным к нему дуальным базисом (в данном

случае автодуальным) будет этот же базис. Действительно эле-

мент

∈

можно представить в виде

a+c

(1+a+a

где коэффициенты c

, c

из F

определяются

888

525 25

123

()0; ( )1; ((1 ))1

FFF

rrr

cTaa cTaa cT aaa=⋅= = ⋅= = ++ =

так

, что a

+(1+a+a

Указанный базис является также нормальным базисом по-

ля

над F

, т.к. 1+a+a

. Чтобы разобраться в представлен-

ном выше примере рассмотрим один из способов представления

элементов конечного поля

из q=p

элементов. Идея этого спо-

соба базируется на следующих фактах: Поле

является про-

стым алгебраическим расширением простого поля

. Если f(x)

неприводимый многочлен степени

n из F

[x] , то любой корень а

этого многочлена принадлежит полю

и потому F

(a).

Тогда каждый элемент поля

можно однозначно представить в

виде значения некоторого многочлена от х над

степени не бо-

лее

n -1, при x=a.

Например, чтобы представить таким способом элементы

поля

будем рассматривать это поле как простое алгебраиче-

ское расширение степени 2 поля

, которое получается присое-

динением корня а неприводимого над

многочлена степени 2,

пусть это будет

f(x)=x

∈

[x]. Тогда f(a)=a

+1=0 в F

и девять

элементов поле

можно задать в виде: p

a, где p

∈

Точнее,

={0,1,2,a,1+a,2+a,2a,1+2a,2+2a}.

Продолжим теперь более детальное рассмотрение элемен-

тов теории многочленов над конечными полями ввиду важности

ее приложений в криптографии.

У каждого ненулевого многочлена

f(x) над конечным по-

лем кроме его степени

deg(f(x)) имеется еще одна важная цело-

численная характеристика – его порядок.

Лемма. Если f(x)

∈

[x] многочлен степени m

≥

1, удовле-

творяющий условию

f(0)

≠

0, то существует натуральное число

−≤

qe , для которого двучлен x

-1 делится на f(x).

Этот факт позволяет ввести определение порядка много-

члена над конечным полем.