Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Бинарные отношения 2 страница
|
|
Положив G = G' в определении изоморфизма, мы получим изоморфное отображение φ: G → G группы G на себя. Оно называется автоморфизмом группы G.
2.3.2. Гомоморфизмы
Пусть G и G' – группыс операциями ∙ и *. Отображение f: G→ G' группы (G, ∙) в (G', *) называется гомоморфизмом, если f(a∙ b) = f(a) * f(b), для любых a, b Î G (другими словами, в определении изоморфизма опущено свойство 2).
Пример 12. Гомоморфизм мультипликативной группы (R+, *, 1) положительных вещественных чисел в аддитивную группу (R, +, 0) вещественных чисел можно задать log: (R+, *, 1) → (R, +, 0). Известное свойство логарифма
log ab = log a + log b моделирует свойство (1) в определении изоморфизма. Обратным служит отображение exp: (R, +, 0) → (R+, *, 1) – гомоморфизм аддитивной группы вещественных чисел в мультипликативную группу положительных вещественных чисел. ▲
Биективный гомоморфизм φ: G→ G' называется изоморфизмом групп G и G', группы G и G' называются изоморфными; обозначаются G @ G'
Гомоморфное отображение группы в себя (φ: G→ G)называется эндоморфизмом.
Множество элементов группы G, которое при гомоморфизме φ: G→ G' переходит в единичный элемент, называется ядром гомоморфизма φ и обозначается Ker(φ). Как любое отображение, гомоморфизм имеет образ (который может не совпадать с G'). Образ гомоморфизма обозначается Im(φ).
Пример 13. В качестве наглядного примера гомоморфизма - отображение множества точек участка земной поверхности на множество точек карты. Для нас существенно то что, чем выше точки земной поверхности над уровнем моря, тем в более коричневые точки карты они отображаются. Таким образом, мы рассматриваем не просто множества элементов. В первом случае здесь между элементами множества существует отношение " выше", а во втором - коричневее". Где выше в первом - там коричневее во втором. " Выше" и " коричневее" – это отношения, заданные на своих множествах. ▲
2.4. Коммутативные кольца
Теория колец позволяет обращаться с различными на первый взгляд множествами, такими как целые числа, рациональные функции, ряды, отображения групп, с использованием одинаковых правил. Аппарат теории коммутативных колец широко применяется при разработке и исследовании криптографических алгоритмов.
Кольцом называется непустое множество R, на котором определены две операции – " сложение" и " умножение", – сопоставляющие каждым двум элементам a и b их сумму a + b Î R и произведение a ∙ b Î R. Операции должны удовлетворять следующим условиям:
1. Все элементы по сложению образуют модуль (аддитивную абелеву группу) с нулевым элементом 0.
2. Умножение дистрибутивно относительно сложения (слева и справа) (a +b) ∙ c = a ∙ c + b ∙ c; c ∙ (a + b) = c ∙ a + c ∙ b.
В определении кольца на операцию умножения не накладывается никаких ограничений, кроме дистрибутивности. Однако часто рассматривают кольца, в которых умножение удовлетворяет тем или иным дополнительным требованиям:
3. Ассоциативность умножения: (a ∙ b) ∙ c = a ∙ (b ∙ c).
4. Коммутативность умножения: a ∙ b = b ∙ a.
5. Существование единичного элемента е такого, что а ∙ е = е ∙ а = а для любого элемента а (при этом элемент е может отличаться от числа 1).
Если в кольце выполняется условие 3, то говорят, что кольцо ассоциативно; если выполняется условие 4, то кольцо коммутативно; если выполняется условие 5, то говорят о кольце с единичным элементом. Если в кольце выполнены требования 3-5, то элементы кольца образуют коммутативный моноид по умножению.
Кольцо называется целостным кольцом (или областью целостности), если оно является коммутативным кольцом с единичным элементом e ≠ 0, в котором равенство a ∙ b = 0 влечет за собой a = 0 или b = 0.
Два элемента кольца a ≠ 0 и b ≠ 0 называются делителями нуля, если их произведение a ∙ b = 0.
Пример 14. а) Множество целых чисел с обычными операциями сложения и умножения являются кольцом (обозначаются Z, +, ∙). Множество mZ целых чисел, делящихся на m, является в Z подкольцом (при m > 1 без единицы). Аналогично кольцами с единицей являются Q и R, причем естественные включения Z Ì Q Ì R определяют цепочки подколец кольца R.
б) Рассмотрим кольцо классов вычетов Zm по модулю m. Оно состоит из элементов 0, 1, 2,...m-1. Выполняем обычное умножение чисел и берем остаток от деления на m. Если m составное, то есть m = a ∙ b, делителями нуля будут a и b. В частности при a = 10, b = 21, m = 35 тогда a ∙ b = 210 º 0 (mod 35). ▲
Кольцо R называется телом если R ≠ {0} и ненулевые элементы в R образуют группу относительно операции умножения (∙). Другими словами тело – это кольцо с единицей, в котором для каждого элемента a ≠ 0 существует обратный по умножению элемент a-1 такой, что a ∙ (a-1) = 1.
Многие свойства колец являются аналогичными соответствующим свойствам групп и вообще – множеств с одной ассоциативной операцией. Например, am an = am+n, (am)n = amn для всех неотрицательных целых m, n и всех a Î R.
Как мы уже знаем, два целых числа a и b называются сравнимыми помодулю m, если при делении на m они дают одинаковые остатки. Пишут
a ≡ b(mod m), а число m называют модулем сравнения.
Таким образом, получается разбиение множества целых чисел Z на классы чисел, сравнимых между собой по mod m и называемых классами вычетов по mod m.
Каждый класс вычетов имеет вид: {r}m = r + mZ = {r + mk | kÎ Z},
так что Z = {0}mÈ {1}mÈ …È {m -1}m.
Таким образом, каждым двум классам {k}m и {l}m, независимо от выбора в них представителей k, l, можно сопоставить классы, являющиеся их суммой, разностью или произведением, т.е. на множестве Zm = Z/mZ классов вычетов по модулю m однозначным образом выполняют операции ⊕ и ⊗ (операции сложения и умножения в поле F2):
{k}m Å {l}m = {k+l}m, {k}m Ä {l}m = {k∙ l}m.
Так как определение этих операций сводится к соответствующим операциям над числами из классов вычетов, т.е. над элементами из Z, то {Zm, Å, Ä } будет также коммутативным кольцом с единицей {1}m = 1+mZ.
Оно называется кольцом классов вычетов по модулю m.
Пример 15. Приведем два простейших примера, указывая отдельно таблицы сложения и умножения:
для Z2 для Z3
| + | 0 | 1 | . | 0 | 1 | + | 0 | 1 | 2 | . | 0 | 1 | 2 | |||
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 0 | |||
| 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 2 | 0 | 1 | 0 | 1 | 2 | |||
| 2 | 2 | 0 | 1 | 2 | 0 | 2 | 1 |
▲
Так как в кольце классов вычетов определена операция умножения, то там можно совершенно естественно определить операцию возведения в степень, а именно: a*a*…*a = ak. Все это, естественно, сравнивается с модулем m.
2.5. Гомоморфизмы и идеалы колец
На кольца распространяются понятия гомоморфизма и изоморфизма.
Пусть {R, +, ∙ } и { R', Å, Ä } – кольца. Отображение f: R → R' называется гомоморфизмом, если выполняются равенства:
f(a+b) = f(a) Å f(b); f(a∙ b) = f(a) Ä f(b).
При этом конечно, f(0) = 0'; f(n∙ a) = n∙ f(a), n Î Z.
Подмножество S кольца R называется подкольцом этого кольца, если оно замкнуто относительно операций сложения (+) и умножения (∙) и образует кольцо относительно этих операций. (Замкнутость – это условие, когда результат операций a + b и a ∙ b над a, b Î S также Î S).
Подмножество L кольца R называется идеалом этого кольца, если оно является подкольцом кольца R и для всех a Î L и r Î R имеет место a·r Î L, r·a Î L.
Множество элементов группы G (а значит и кольца R), которое при гомоморфизме переходит в единичный элемент, называется ядром гомоморфизма f и обозначается Ker f ( Ker f = {a Î R | f (a) = е }).
Ker f – подкольцо в R. Но это не произвольное подкольцо. Действительно, если L = Ker f Î R, то L∙ x Í L (поскольку f(l∙ x) = f(l) Ä f(x) = 0 Ä f(x) = 0' для всех l Î L) и x∙ L Í L для всех x Î R. Стало быть, L∙ R Í L и R ∙ L Í L. Подкольцо L, обладающее этими свойствами, является идеаломкольца R. Ядра гомоморфизмов всегда являются идеалами.
Ядро гомоморфизма R ® R колец является идеалом в R, а полные прообразы элементов из R являются классами вычетов по этому идеалу.
Пример 16. Пусть R - поле рациональных чисел (вида a/b, b и a, – целые числа, b ≠ 0). Тогда множество целых чисел Z (вида – n, n, 0; n – целые числа > 0) является его подкольцом, но не идеалом т.к., например a = 1 Î Z, r = 1/2 Î R, но a ∙ r = 1 ∙ 1/2 = 1/2 Ï Z. ▲
Каждый идеал L кольца R определяет некоторое разбиение множества R на смежные классы по аддитивной подгруппе L, называемые классами вычетов кольца R по модулю идеала L. Класс вычетов кольца R по модулю L, содержащий элемент a Î R обозначают через [a] = a + L, т.к. он состоит из всех элементов R вида a + c, где c Î L. Элементы a, b Î R, принадлежащие одному и тому же классу вычетов по модулю L (т.е. такие, что a - b Î L), называют сравнимыми по модулю L и обозначают a ≡ b(mod L). Для них справедливо:
Если a ≡ b (mod L), то a + r ≡ b + r (mod L) ,
если a ∙ r ≡ b ∙ r (mod L), то r ∙ a ≡ r ∙ b (mod L) ,
n ∙ a ≡ n ∙ b(mod L) " n Î Z, r Î R .
Кроме того, если r ≡ s mod L, то a + r ≡ b + s (mod L) и a ∙ r ≡ b∙ s (mod L).
Множество классов вычетов кольца R по модулю идеала L образует кольцо относительно операций + и ∙. Эти операции определяются равенствами:
(a + L) + (b + L) = (a + b) + L (2.1)
(a + L) ∙ (b + L) = a∙ b + L (2.2)
Определение. Кольцо классов вычетов кольца R по модулю идеала L относительно операций (2.1), (2.2) называется фактор - кольцом кольца R по идеалу L и обозначается R/L.
Пример 17. Фактор - кольцо (или кольцо вычетов) 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 целых чисел по главному идеалу, порожденному простым числом Р, является полем (см. далее п. 2.7).
Идеал L кольца R называется главным, если существует элемент a Î R, такой что L = (a). Здесь, для коммутативного кольца R, величина (a) = {r∙ a + n∙ a | r Î R, n Î Z} – наименьший идеал, содержащий данный элемент a Î R. Если кольцо имеет единицу, то (a) = {ra | r Î R} (a – главный идеал).
Таким образом, каждому гомоморфизму соответствует идеал, являющийся его ядром. Гоморфный образ кольца R по идеалу L называется кольцом классоввычетов R по L, или фактор - кольцом.
Пример 18. Пусть p = 3 простое число. Тогда фактор - кольцо состоит из трех элементов [0], [1], [2]. Операции в этом кольце можно задать таблицами, аналогичными таблицам Кэли конечных групп
| + | [0][1][2] | * | [0][1][2] | |
| [0] [1] [2] | [0][1][2] [1][2][0] [2][0][1] | [0] [1] [2] | [0][0][0] [0][1][2] [0][2][1] |
▲
Приведенный пример является первым рассматриваемым нами образцом конечного поля, т.е. поля, содержащего конечное число элементов, которые играют основную роль в современной криптографии.
2.6. Типы колец
В хорошо известных числовых кольцах Z, Q и R из того, что
a∙ b = 0, следует, что-либо a = 0, либо b = 0. Но кольцо квадратных матриц Mn этим свойством уже не обладает. Используя матрицы Eij, состоящие из нулей всюду, кроме элемента, стоящего на пересечении i – строки и j – го столбца (равного 1), получаем что Eij ∙ Ekl = 0 при j ≠ k, хотя, конечно, Eij ≠ 0 и Ekl ≠ 0. Заметим, что Eik∙ Ekl ≠ 0. Можно было бы приписать столь необычный для элементарной арифметики феномен некоммутативности кольца Mn, но это не так. Рассмотрим еще несколько примеров.
Пример 19. Числовые пары (a, b) (a, b Î Z, Q или R) со сложением и
умножением, определенными формулами:
(a1, b1) + (a2, b2) = (a1+a2, b1+b2),
(a1, b1) ∙ (a2, b2) = (a1∙ a2, b1∙ b2),
образуют коммутативное кольцо с единицей (1, 1), в котором
мы снова встречаемся с тем же явлением: (1, 0) ∙ (0, 1) = (0, 0) = 0. ▲
Пример 20. В кольце RR вещественных функций, функции f: x→ |x| + x и g: x→ |x| - x таковы, что f(x) = 0 для x ≤ 0 и g(x) = 0 для x ≥ 0, а поэтому их поточечным произведением f∙ g будет нулевая функция, хотя f ≠ 0 и g ≠ 0. ▲
Пример 21. Если кольцо состоит из 3 и менее элементов, то это кольцо коммутативное.
1) Если элемент один, тогда он равен нулю.
2) Если два элемента, тогда a∙ a = a ≠ 0.
3) Если три элемента, тогда a+b = 0, так как третий элемент не совпадает ни с a, ни с b. Следовательно, a∙ b = - a∙ a. Это следует из такого рассуждения:
a∙ (a + b) = a∙ a + a∙ b = 0 Þ a∙ a = - a∙ b;
Но с другой стороны: (a+b)∙ a = a∙ a + b∙ a; Þ a∙ a = -b∙ a Þ a∙ b = b∙ a. ▲
Пример 22. Покажем, что кольцо из четырех элементов может быть не коммутативным. Введем группу по сложению, состоящую из двух элементов 0 и 1. Нейтральным элементом является 0. Следовательно, 1+1 = 0. Теперь рассмотрим множество из четырех элементов – прямое произведение такой группы на себя. Оно состоит из пар (a, b), где каждая из компонент может принимать значение 0 или 1: (0, 0), (0, 1), (1, 0), (1, 1).
Зададим операцию умножения: (a+b) ∙ (c+d) = ((a+b)∙ c, (a+b)∙ d).
Покажем ассоциативность:
(a + b) ∙ ((c + d) ∙ (e + f)) = (a + b) ∙ ((c + d) ∙ e, (c + d) ∙ f) =
= ((a + b) ∙ (c + d) ∙ e, (a + b) ∙ (c + d) ∙ f).
С другой стороны,
((a + b) ∙ (c + d)) ∙ (e + f) = ((a + b) ∙ c, (a + b) ∙ d)(e∙ f) = (((a + b) ∙ c + (a + b) ∙ d) e, ((a + b) ∙ c + (a + b) ∙ d) ∙ f) = ((a + b) ∙ (c + d) ∙ e, (a + b) ∙ (c + d) ∙ f).
Аналогично показывается выполнение двух законов дистрибутивности.
Но это кольцо не коммутативно. Действительно:
(1, 0) ∙ (1, 1) = ((1+0) ∙ 1, (1+0) ∙ 1) = (1, 1)
(1, 1) ∙ (1, 0) = ((1+1) ∙ 1, (1+1) ∙ 0) = (0, 0). ▲
2.7. Поле
2.7.1. Основные понятия
Коммутативное кольцо называется полем, если его ненулевые элементы образуют группу относительно операции умножения. Всякое поле содержит не менее двух элементов.
Поскольку основной алгебраической структурой, которая будет использоваться в дальнейшем, является поле, рассмотрим более подробно его определения.
Поле есть множество F, на котором заданы две операции, называемые сложением + и умножением *, и которое содержит два выделенных элемента 0 и е, причем 0 ≠ е. Поле – это абелева группа по сложению, единичным элементом которой является 0, а элементы из F отличные от нуля, образуют абелеву группу по умножению, единичным элементом которой является е. Операции сложения и умножения в поле связаны законом дистрибутивности a∙ (b+c) = a∙ b + a∙ c. Второй закон дистрибутивности (b+c)∙ a = b∙ a + c∙ a выполняется автоматически в силу коммутативности операции умножения. Элемент 0 называется нулевым, а элемент е – единицей, т.е. е = 1.
Свойство поля, появляющееся из определения целостности кольца, т.е. равенство a∙ b = 0 влечет a = 0 или b = 0, выражают словами «отсутствуют делители нуля». Другими словами, в коммутативном кольце ненулевой элемент а называют делителем нуля, если существует другой ненулевой элемент b такой, что a∙ b = 0. Если в кольце нет делителей нуля, то оно называется кольцом без делителей нуля или областью целостности. Никакой делитель нуля не может иметь обратного по умножению элемента. Поэтому никакое поле и тело не содержат делителей нуля.
Поле представляет собой гибрид двух абелевых групп – аддитивной и мультипликативной, связанных законом дистрибутивности (теперь уже одним ввиду коммутативности). Произведение a∙ b-1 записывается обычно в виде дроби (или отношения) a / b. Следовательно, дробь a / b, имеющая смысл только при b ≠ 0, является решением уравнения b∙ x = a. Действия с дробями подчиняются нескольким правилам:
a/b = c/d Û a∙ d = b∙ c, b, d ≠ 0,
a/b+c/d = (a∙ d+b∙ c)/b∙ d, b, d ≠ 0,
-(a/b) = (-a/b) = (a/-b), b ≠ 0,
(a/b) ∙ (c/d) = (a∙ c/b∙ d) b, d ≠ 0,
(a/b)-1 = b/a, a, b ≠ 0.
Это обычные школьные правила, но их надо не запоминать, а выводить из аксиом поля. Посмотрим, как это делается для второго правила.
Пусть x = a/b и y = c/d – решения уравнений b∙ x = a и d∙ y = c.
Из этого следует:
d∙ b∙ x = d∙ a и b∙ d∙ y = b∙ c ⇒ b∙ d∙ (x+y) = d∙ a+b∙ c ⇒ t = x+y = (d∙ a+b∙ c)/b∙ d – единственное решение уравнения b∙ d∙ t = d∙ a+b∙ c.
Подполем F поля P называется подкольцо в P, само являющееся полем.
Пример 23. Поле рациональных чисел Q есть подполе поля вещественных чисел R. ▲