Математические основы криптологии и криптографические методы и средс

физма/ от изоморфизма заключается в наличии нетривиального ядра Кег / являющегося мерой неинъективности/ Если же Kerf - { e \ , то f:G —*\m /-изоморфизм. Заметим, что Да) = е \ ДЬ) = е', Да*Ь) =

=Да)°ДЬ) —е'ое' = е' иД а~1) =Да)~1=(е)~1—е\ Поэтому ядро Кег/ - подгруппа в G.

Пусть Я = К е г /с G. Тогда у ^ 1) = № Д К )№ Х) =/(g)e>/(g-1) =

= е \ V А еЯ , J G C, т.е. ^А# -1 е Я и, значит, gHg~l еЯ . Заменив здесь # на получим g~lH geH , откуда Hc:gHg~l Стало быть, H =gHg~l, VgeG . Подгруппы, обладающие этим свойством, называются нор­ мальными. Еще их называют инвариантными подгруппами или нор­ мальными делителями. Итак, нами доказана:

Теорема 7. Ядра гомоморфизмов всегда являются нормальными подгруппами.

Значение этого факта мы оценим в должной мере позднее. Заме­ тим пока, что далеко не всякая подгруппа нормальна в G.

Пример 27. Отображение f:R —>T=SO(2) аддитивной группы вещественных чисел на группу Т вращений плоскости с неподвиж­ ной точкой 0, задаваемое формулойДТ) = Фх (где Фхвращение про­ тив часовой стрелки на угол 2яХ), гомоморфно. Поскольку Ф).офц = Фх+(1, а вращение на угол, целочисленно кратный 2л, совпа­ дает с единичным вращением (на нулевой угол), то Кег / = (2ял | n^Z}. Говорят также, что /-гомоморфизм R на окружность .S'1 еди­ ничного радиуса, поскольку имеется взаимно однозначное соответ­ ствие между Фх и точкой на S 1с полярными координатами (1 ,2 яХ), 0 <Х<1 .

Пример 28. Полная линейная группа GL(rtJR) вещественных матриц А (т.е. матриц с коэффициентами в R) с не равным нулю оп­ ределителем det4 гомоморфно отображается на мультипликативную группу R * отличных от нуля вещественных чисел, если положить / = det. Условие гомоморфизма ДАВ) ~ДА)ДВ) выполнено. Здесь

SL(n,R) = Кег/

Пример 29. Группа Aut(G) и даже отдельный неединичный эле­

мент ф € Aut(G) могут служить источником важных сведений о группе G. Вот яркий пример такого рода. Пусть G - конечная груп­

па, на которой действует автоморфизм порядка 2 (ф 2 = ф е = 1 ) без неподвижных точек:

а фе => ф(а ) ф а.

Предположим, что ф (a)a~l = <p(b)b~' для каких-то a,beG. Тогда

после умножения этого равенства слева на ф(б) 1 и справа на а полу­

чим ф(Л)_1ф(а) = Ь~ха, т.е. cp(b la) —Ь~1а, откуда Ь~1а = е и Ь~х = а.

Итак, ф(а)а-1 пробегает вместе с а все элементы группы G, или, что

равносильно, любой элемент g e G записывается в виде g —Cp(a)a~l Но в таком случае

ФС?) = ф (ф (я))ф (а') = ф 2(я)ф (я') = я ф (я )' = (ф (я)я1) ' =g~l.

Итак, ф совпадает с отображением g-^g* ■Зная это, получаем

ab = ф(я_1)ф (Г 1) = ф(я_1А_|) = {а~хЬ~'ух= Ьа,

т.е. группа G оказывается абелевой. Кроме того, (G:e) - нечетное число, ибо G состоит из е и непересекающихся пар элементов gt: gr1 -

=Ф&)-

1.2.10.Кольца

Определение и общие свойства колец

Алгебраические структуры (Z, + ), (Z,*) выступали у нас в каче­ стве самых первых примеров моноидов, причем на (Z, + ) мы смот­ рели позднее как на аддитивную абелеву группу. В повседневной жизни, однако, эти структуры чаще всего объединяются, и получает­ ся то, что в математике называется кольцом. Важный элемент эле­ ментарной арифметики заключен в дистрибутивном (или сочета­ тельном) законе (а +b)c = ас + Ьс, кажущимся тривиальным только в силу приобретенной привычки. Попытавшись, например, объеди­ нить алгебраические структуры (Z, +), (Z,o), где пот = п+ т + nnt, мы уже не заметим столь хорошей согласованности между двумя би­ нарными операциями. А сейчас дадим определение кольца.

Пусть К - непустое множество, на котором заданы две бинар­ ные алгебраические операции + (сложение) и х (умножение), удовле­ творяющие следующим условиям:

К1(К9+ ) - коммутативная (абелева) группа; К2 (К,*) - полугруппа;

КЗ операции сложения и умножения связаны дистрибутивными законами (другими словами, умножение дистрибутивно по сложе­ нию):

(а + Ь) х с = а х с + Ь х с, с х {а + Ь) = с х а + с х Ь, а,Ь,с^К.

Тогда (К, + ,*) называется кольцом.

Структура (К, + ) называется аддитивной группой кольца, а (ЛГ,х) - его мультипликативной полугруппой. Если (К,*) - моноид, то говорят, что (К, + ,х) - кольцо с единицей.

Подмножество L кольца К называется подкольцом, если

х,y e L => х + у е Ь и х х у е Ь ,

г.е. если L - подгруппа аддитивной группы и подполугруппа муль­ типликативной полугруппы кольца.

Кольцо называется коммутативным, если д: * у =у х х для всех х,уе К (в отличие от групп коммутативное кольцо не принято назы­ вать абелевым).

Пример 30. (Z, + ,•) - кольцо целых чисел с обычными опера­ циями сложения и умножения. Множество mZ целых чисел, деля­ щихся на т, будет в Z подкольцом (без единицы при т > 1). Анало­ гично кольцами с единицей являются Q и R, причем естественные включения Z ^ Q ^ R определяют цепочки подколец кольца R.

Пример 31. Свойства операций сложения и умножения в M„(R) показывают, что M„(R) - кольцо, называемое кольцом квадратных матриц порядка п над R.

Пример 32. Можно рассматривать кольцо квадратных матриц М„(К) над произвольным коммутативным кольцом К, поскольку при сложении и умножении двух матриц А,В<=М„(К) будет снова полу­ чаться матрица с коэффициентами из К. Все это прямо вытекает из формальных действий с матрицами.

Пример 33. Пусть X - произвольное множество, К - произволь­ ное кольцо, Xх = {Х—+К} - множество всех функций f:X-+K9рассмат­ риваемое вместе с двумя бинарными операциями - поточечной сум­ мой f+ g и поточечным произведением^, определяемыми следую­ щим образом:

<f+ g)(x) =Дх) 0 g(x),

(fg)(x) =/(x)®g(x)

( Ф и ® - операции сложения и умножения в К).

Без труда проверяется, что Кх удовлетворяет всем аксиомам кольца. Так, ввиду дистрибутивности операций в ЛТ, имеем

1Л*) ©£(*)] ®А(*) =Ax)®h(x) ®g{x)®h(x)

для любых fg ,h е Кх и любого jeeA', а это по определению поточеч­ ных операций дает (f +g)h =fft +gh. Справедливость второго дист­

рибутивного закона устанавливается аналогично.	в К,	то Ох-'х—►О
Если 0,1 - нулевой и единичный элементы
и \х:х—>1 - постоянные функции, играющие роль	нуля	и единицы

в Кх В случае коммутативности К кольцо функций /Г*также комму­ тативно.

Пример 34. Кольцо Кх содержит разнообразные подкольца, оп­ ределяемые специальными свойствами функций. Пусть Х = [0,1] - замкнутый интервал в R и К = R. Тогда кольцо I?*0’11 всех веществен­ ных функций, определенных на [0,1], содержит в качестве подколец кольцо Л ^ ч всех ограниченных функций, кольцо /?н«пp,0’,, всех не­ прерывных функций, кольцо /?днф|0’11 всех непрерывно дифференци­ руемых функций и т.д., поскольку все отмеченные свойства сохра­ няются при сложении (вычитании) и умножении функций.

Пример 35. Каждому а е R отвечает постоянная функция ах:х—кг, и отображение вложения а-+ах позволяет рассматривать R как подкольцо в Rx, т.е. почти каждому естественному классу функ­ ций соответствует свое подкольцо в Rx.

Многие свойства колец являются переформулировками соответ­ ствующих свойств групп и вообще - множеств с одной ассоциатив­ ной операцией. Например, «"'в" = ат+п, (ат)п = атпдля всех неотриЦа­

тельных целых т, п и всех аеК . Другие свойства, более специфиче­ ские для колец и вытекающие прямо из аксиом кольца, моделируют, по существу, свойства Z. Отметим некоторые из них.

1. аО = Оа = О для всех а & К. Действительно, а + 0 = а => а(а + 0) = аа => а2 + аО = а2 => а2+ аО = а2+ 0 => аО = 0 (аналогично 0 а = 0 ).

2. Предположим, что 0 = 1. Тогда получаем, что а = а1 = аО = 0 для всех а^К , т.е. К состоит только из нуля. Стало быть, в нетриви­ альном кольце К всегда 0 ^ 1 .

3. (~a)b = a(-b) = - (ab). Действительно, 0 = аО = a(b-b) = ab + +(-£) => a(-b) =- (ab).

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

1.2.11. Сравнения. Кольцо классов вычетов

Множество mZ, очевидно, замкнуто относительно операций сложения и умножения, удовлетворяя при этом всем аксиомам коль­ ца. Таким образом, верно следующее утверждение: каждое ненуле­ вое подкольцо кольца mZ имеет вид mZ, где m eN .

Теперь, используя подкольцо m ZeZ, построим ненулевое коль­ цо, состоящее из конечного числа элементов. С этой целью введем следующее определение.

Два целых числа п и п ' называются сравнимыми по модулю т, если при делении на т они дают одинаковые остатки. Пишут и = п \т ) или п = п '(mod /и), а число т называют модулем сравнения.

Таким образом, получается разбиение Z на классы чисел, срав­ нимых между собой по mod т и называемых классами вычетов по mod т. Каждый класс вычетов имеет вид

{г}т = r + mZ = {г + тк \ Ле Z}, так что

Z = {0 }mu { l} mu ...и {т-Цт.

Таким образом, каждым двум классам {к}ти {/}„, независимо от выбора в них представителей к, I, можно сопоставить классы, яв­ ляющиеся их суммой, разностью или произведением, т.е. на множе­ стве Z„ = Z/ m Z классов вычетов по модулю т однозначным образом

индуцируются операции Ф и ® :

{*}„,©{/},„ ={к+[}m{к}т®{1}„={*/}„.

Поскольку определение этих операций сводится к соответст­ вующим операциям над числами из классов вычетов, т.е. над элемен­

тами из Z, то {Zm,® ,®} будет также коммутативным кольцом с еди­ ницей {1},„ = 1 + mZ. Оно называется кольцом классов вычетов по модулю пи При небольшом навыке (и фиксированном модуле) отка­ зываются от кружочков и оперируют с каким-нибудь фиксирован­ ным множеством представителей по модулю ///, чаще всего - с мно­ жеством {0 , 1 , 2 , ... i / f - 1 } (оно называется приведенной системой вычетов по модулю /и). В соответствии с этим соглашением - к =т - к, 2(т - 1 ) = - 2 = т - 2 .

Итак, конечные кольца существуют. Приведем два простейших примера, указывая отдельно таблицы сложения и умножения:

+	0	1		0	1
2 : 0	0	1	0	0	0 ,1
1	1	0	1	0	0

+	0	1	2		0	1	2
0	0	1	2	0	0	0	0
1	0	1	2	1	0	1	2
2	0	2	1	2	0	2	1

1.2.12. Гомоморфизмы и идеалы колец

Отображение/: п^>{п}тобладает следующими свойствами:

Лк+1)=Лк) ®АГ);АкЬ =Ak)®At)

Это дает основание говорить о гомоморфизме колец Z и Zm в соответствии с общим определением.

Пусть {К, +, •} и {А1,®,®} - кольца. Отображение f.K —*IC на­ зывается гомоморфизмом, если оно сохраняет все операции, т.е. если

А а + Ь) =д«) ®АЬ);А«Ь) =Аа)®АЬ).

При этом, конечно,/(0) = 0'; Дяа) = яДа), я eZ. Ядром гомоморфизмаf называется множество К ег/= {аеК \А а) = O'}.

Ясно, что Кег / - подкольцо в К. Но это не произвольное под­

кольцо. Действительно, если Z, = Ker /еЛГ, то L x c iL (поскольку

Д1х) =/(/) Дх) = 0 Дх) = О' для всех l^L ) и х L c Z для всех хеК .

Стало быть, L K ^ L n K L ^ L . П о д к о л ь ц о L, обладающее этими свойствами, называется идеалом кольца К. Итак, ядра гомоморфиз­ мов всегда являются идеалами.

Пример 36. При построении Zmнеявным образом как раз и ис­ пользовался тот факт, что m Z - идеал кольца Z.

Мы видим, что в кольце Z каждое ненулевое подкольцо является идеалом - случайное обстоятельство, которому нет места, скажем,

уже в матричном кольце M2(Z): множество

ся подкольцом, но не идеалом в M2(Z).

Пример mZ подсказывает способ построения идеалов (возможно, не всех) в произвольном коммутативном кольце К: если а - какой-то элемент К, то множество аК всегда является идеалом в К. Действи­ тельно,

ах + ау = а(х +у), (ах)у = а{ху).

Говорят, что а К - главный идеал, порожденный элементом а^К.

1.2.13.Типы колец

Вхорошо известных нам числовых кольцах Z, Q и R из того, что аЪ = 0, следует, что либо а = 0, либо 6 = 0. Но кольцо квадратных матриц Мпэтим свойством уже не обладает. Используя матрицы Е„, состоящие из нулей всюду, кроме элемента, стоящего на пересечении l-й строки иу-го столбца (равного 1 ), получаем что EijEki = 0 приj фЛ,

хотя, конечно, ЕдфО и Емф0. Заметим, что ЕцДк1ф 0. Можно было бы приписать столь необычный для элементарной арифметики фе­ номен некоммутативное™ кольца Л/„, но это не так. Рассмотрим еще несколько примеров.

Пример 37. Числовые пары (a,b) (a,beZ, Q или if) со сложением и умножением, определенными формулами

(abbi) + (аъЬ2) = (с, + аъЬ\ + Ь2), (аьЬх)(аьЬ2) = (а1а2, Ьф2),

образуют,	очевидно,	коммутативное кольцо с единицей (1 ,1 ),
в котором	мы снова	встречаемся с тем же явлением: (1 ,0 )(0 ,1) =

= (0,0) = 0.

Пример 38. В кольце RR вещественных функций (примеры 28 - 30) функции /лк—►|х| + х и g:x—>рс| - х таковы, что fix) = 0 для JC< 0 и g(.x) = о для х > 0 , а поэтому их поточечным произведением fg будет нулевая функция, хотяf -ф0 и g Ф0 .

Пример 39. Если кольцо состоит из трех и менее элементов, то это кольцо коммутативное.

a) если элемент один, тогда он равен нулю; B) если два элемента, тогда аа = аф 0 ;

c) если три элемента, тогда а + b - 0, так как третий элемент не совпадает ни с в, ни с Ь. Следовательно, ab~ —аа. Это следует из такого рассуждения: а(а + b) = аа + ab = 0=>аа =- ab. С другой сто­ роны: (а + Ь)а = aa+ba => a a = -b a => ab = Ьа.

Пример 40. Покажем, что кольцо из четырех элементов может быть не коммутативным. Введем группу по сложению, состоящую из двух элементов 0 и 1 . Нейтральным элементом является 0. Следова­ тельно, 1 + 1 = 0 .

Теперь рассмотрим множество из четырех элементов - пря­ мое произведение такой группы на себя. Оно состоит из пар (а,Ь), где каждая из компонент может принимать значение 0 или 1 : (0 ,0 ),

(0,1),(1,0),(1,1).

Зададим операцию умножения: (а + b)(c + d) = ((я + b)c,(a + b)d). Покажем ассоциативность:

(а + b)((c +d)(e +/)) = (а + b)((c + d)e,(c + d)f) = ((а + b)(c + d)e, (с + Ь)(с + ау).

С другой стороны,

((а + b)(c + d))(e +/) = ((а + b)c,(a + b)d)(ej) = (((а + Ь)с + (а + Ь) d)e,((a + Ь)с + (а + b)d)f) = ((а + Ь)(с + d)e,(a + Ь){с + d)f).

Аналогично показывается выполнение двух законов дистрибу­ тивности.

Но это кольцо не коммутативно. Действительно: (1,0X1,1) = ((1 + 0)1,(1 + 0)1) = (1,1),

(1,1X1,0) = ((1 +1)1,(1 +1)0) = (0 ,0 ).

В связи с вышеизложенным, возникает необходимость в сле­ дующем определении. Если ab = 0 при в ^ 0 и i ^ 0 в кольце К, то а называется левым, а Ь - правым делителем нуля (в коммутативных кольцах говорят просто о делителях нуля). Сам нуль в кольце Кф 0 - тривиальный делитель нуля. Если других делителей нуля нет, то К называется кольцом без делителей нуля. Коммутативное кольцо с единицей 1 Ф0 и без делителей нуля называют целостным кольцом (кольцом целостности или областью целостности).

Справедлива следующая теорема.

Теорема 8. Нетривиальное коммутативное кольцо К с единицей является целостным тогда и только тогда, когда в нем выполнен за­ кон сокращения: ab = ас, а Ф0 => Ь —с для всех а,Ь,с е К.

Доказательство. В самом деле, если в К имеет место закон со­ кращения, то из ab = 0 = « 0 следует, что либо а = 0 , либо а ф0 , но Ь = 0. Обратно, если К - область целостности, то ab = ac, аф 0 => ==> а(Ь - с) = 0 => b - c = 0=>b = c. Теорема доказана.

В кольце К с единицей естественно рассматривать множество обратимых элементов, т.е. aa~l = а ха = 1. Точнее, следовало бы гово­ рить об элементах, обратимых справа или слева, но в коммутативных кольцах, а также в кольцах без делителей нуля эти понятия совпадают. Действительно, из ab = 1 следует aba= а, откуда афа -1 ) = 0. Поскольку в ^ 0 ,тоЬа—1 = 0 ,т.е. ba = 1 .

Пример 41. В кольце М„ обратимые элементы-это в точности матрицы с отличным от нуля определителем.

Обратимый элемент а не может быть делителем нуля. Действи­ тельно, если ab = 0 , тогда

a'\ab) =0 => (а 1а)Ь = 0 => 1 й = 0 = > 6 = 0 (аналогично Ьа =0 => =>Ь =0). Неудивительно поэтому, что имеет место следующая

Теорема 9. Все обратимые элементы кольца К с единицей со­ ставляют группу U(K) по умножению.

Доказательство. Действительно, так как множество ЩК) со­ держит единицу, а ассоциативность по умножению в К выполнена, то нам нужно убедиться в замкнутости множества ЩК), т. е. прове­ рить, что произведение ab любых двух элементов а и А из ЩК) будет снова принадлежать ЩК). Но это очевидно, поскольку

(аЬ)~1 = Ь~ха~х, abb~xa~l —a{bb~x)d~x = a d 1 = 1

и, значит, ab обратим. Теорема доказана.

1.2.14. Поле

Понятие поля. В предыдущем разделе мы получили весьма ин­ тересный класс колец - так называемые кольца с делением, или тела, заменив в определении кольца аксиому (К2) на существенно более сильное условие (К1'): относительно операции умножения множест­ во Л* = Л\{0} является группой. Кольцо с делением, стало быть, все­ гда будет без делителей нуля, и каждый ненулевой элемент в нем обратим. Операции сложения и умножения в коммутативном кольце становятся почти полностью симметричными. В математике такая структура носит специальное название - поле. Итак, дадим его опре­ деление.

Поле Р - это коммутативное кольцо с единицей 1 ф 0, в котором каждый элемент а Ф0 обратим. Группа Р* = ЩК) называется мульти­ пликативной группой поля.

Поле представляет собой гибрид двух абелевых групп - адди­ тивной и мультипликативной, связанных законом дистрибутивности (теперь уже одним ввиду коммутативности). Произведение ab~xзапи­ сывается обычно в виде дроби (или отношения) а/b. Следовательно, дробь а/b, имеющая смысл только при b Ф0, является решением уравнения Ьх —а. Действия с дробями подчиняются нескольким пра­ вилам:

а/b = c/d о a d - be, b,dф О, а/b + c/d = (ad + bc)/bd, b,d Ф0, ЩаЛ) = ( - а/b) = (a/-b), ЬфО, (,a/b)(c/d) = (ac/bd) b,d Ф0, (a/b)~l = b/a, a,b Ф0.