Математические основы криптологии и криптографические методы и средс
..pdfфизма/ от изоморфизма заключается в наличии нетривиального ядра Кег / являющегося мерой неинъективности/ Если же 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.