Кольца и тела в абстрактной алгебре

⇐ ПредыдущаяСтр 9 из 10Следующая ⇒

В абстрактной алгебре кольцо – естественное обобщение целых чисел. Кольцо – это множество, на котором заданы две операции, «сложение» и «умножение», со свойствами, напоминающими сложение и умножение целых чисел.

Кольцо – это множество R, на котором заданы две бинарные операции: + и × (называемые сложение и умножение), со следующими свойствами:

2. – коммутативность сложения;

3. – ассоциативность сложения;

4. – существование нейтрального элемента относительно сложения;

5. – существование обратного элемента относительно сложения;

6. – дистрибутивность.

Кольца могут обладать следующими свойствами:

– ассоциативность умножения: (ассоциативное кольцо);

– наличие единицы: (кольцо с единицей);

– коммутативность умножения: (коммутативное кольцо);

– отсутствие делителей нуля: .

Обычно под кольцом понимают ассоциативное кольцо с единицей.

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

Таким образом, множество R с двумя бинарными ассоциативными операциями «+» и « » называется кольцом, если выполняются следующие условия:

1. Множество R с бинарным сложением «+» является абелевой группой.

2. Операция умножения « » удовлетворяет дистрибутивности относительно операции сложения «+», т.е. (a + b) c =
= a c + b c и a ( b + c ) = a b + a c.

Непустое подмножество называется подкольцом R, если A само является кольцом относительно операций, определенных в R.

Примеры:

– целые числа (с обычным сложением и умножением).

– кольцо вычетов по модулю натурального числа n (множество, образующее полную систему вычетов целых чисел по модулю n с операциями «+» и « » по модулю n – это коммутативное кольцо).

Конечные поля

Ассоциативное кольцо с единицей, в котором каждый ненулевой элемент обратим, называется телом. Тело – это кольцо, в котором ненулевые элементы образуют группу по умножению.

Коммутативное тело называется полем, т.е. поле – это коммутативное кольцо с единицей, отличной от нуля, в котором любой ненулевой элемент обратим. Таким образом, полем называется множество элементов, на котором определены две операции: одна из них называется сложением и обозначается «+», а другая – умножением и обозначается « », даже если эти операции не являются обычными операциями сложения и умножения чисел. Для того, чтобы множество элементов, на котором заданы операции сложения и умножения, было полем, необходимо, чтобы по каждой из этих операций выполнялись все групповые аксиомы, а также выполнялся дистрибутивный закон. Кроме того, по каждой операции группа должна быть коммутативной, а групповые свойства по операции умножения справедливы для всех ненулевых элементов поля.

Примеры:

– кольцо рациональных чисел, являющееся полем.

– кольцо вещественных чисел, являющееся полем.

– кольцо многочленов от n переменных над полем R.

– кольцо вычетов по модулю натурального числа n является полем в случае, когда n = p, т.е. n – простое число.

Поля с конечным числом элементов q называют полями Галуа по имени их первого исследователя Эвариста Галуа и обозначают GF(q).

Число элементов поля q называют порядком поля. Конечные поля используются для построения большинства известных кодов и их декодирования.

В зависимости от значения q различают простые или расширенные поля. Поле называют простым, если q – простое число. Для обозначения простых чисел будем использовать символ p. Простое поле образуют числа по модулю p: 0, 1, 2, …, p–1, а операции сложения и умножения выполняются по модулю p.

Наименьшее число элементов, образующих поле, равно 2. Такое поле должно содержать 2 единичных элемента: 0 относительно операции сложения и 1 относительно операции умножения. Это поле GF(2), или двоичное. Правила сложения и умножений для элементов GF(2)приводятся на рис. 3.1.

Рис. 3.1

GF(3) –троичное поле с элементами 0, 1, 2. Для него правила сложения и умножения приводятся на рис. 3.2.

Рис. 3.2

Формирование таблиц производится приведением результата сложения или умножения чисел, записанных во главе строк или столбцов, по модулю p, т.е. в качестве результата операции принимается остаток от деления полученного числа на p.

Анализируя состав таблиц, легко убедиться, что 0 и 1 как единичные элементы по операции сложения и умножения не изменяют значения других элементов поля по соответствующей операции. Кроме того, видно, что для каждого элемента по операции сложения и для ненулевых элементов по операции умножения имеются обратные.

На рис. 3.3 приведены правила сложения и умножения для элементов GF(4) при попытке построить это поле из чисел 0, 1, 2, 3 по предыдущей конструкции.

Из рис. 3.3 б видно, что для элемента 2 по операции умножения отсутствует обратный, т.е. набор чисел 0, 1, 2, 3 не является полем при введении операции по модулю 4. Такой результат объясним тем, что 4 не является простым числом. Для поля GF(5) с элементами 0, 1, 2, 3, 4 правила сложения и умножения приводятся на рис. 3.4.

Рис. 3.3

Рис. 3.4

Изучим возможность построения полей с элементами в виде последовательностей чисел.

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

Рассмотрим последовательности длины 4 с элементами из GF(2). Такие последовательности можно складывать как векторы, и нулевым элементом по операции сложения является 0000. Для задания операции умножения сопоставим каждой последовательности многочлен от α:

Умножение таких многочленов может дать степень, большую чем 3, т.е. последовательность, не принадлежащую рассматриваемому множеству.

Для того чтобы свести ответ к многочлену степени не более 3, положим, что α удовлетворяет уравнению степени 4, например,

= 1 + α + α ⁴ = 0,

или

α ⁴ = 1 + α.

Тогда

α ⁵ = α + α ², α ⁶ = α ² + α ³;

1 + α + α ⁴ + α ⁶=1 + α + 1 + α + α ² + α ³ = α ² + α ³.

Это эквивалентно делению на многочлен 1 + α + α ⁴ и нахождению остатка от деления:

Таким образом, имеет место аналогия при формировании поля из чисел и последовательностей чисел (многочленов). Эта аналогия распространяется и на то, что для обратимости введенной операции умножения (чтобы система элементов в виде последовательностей длины m или многочленов степени, меньшей m, образовывала поле) многочлен должен быть неприводим над полем своих коэффициентов (неприводимый многочлен над полем k – многочлен p(x₁, x₂, ..., x_n) от n переменных над полем k, являющийся простым элементом кольца k[x₁, x₂, ..., x_n], то есть непредставимый в виде произведения p = qr, где q и r – многочлены с коэффициентами из k, отличные от константы).

Поле, образованное многочленами над полем GF(р) по модулю неприводимого многочлена p(x) степени m, называется расширением поля степени m над GF(p) или расширенным полем. Оно содержит p^m элементов и обозначается GF(p^m).

Поле, образованное шестнадцатью двоичными последовательностями длины 4, или многочленами степени 3 и менее с коэффициентами из GF(2) по модулю многочлена x⁴ + x + 1, неприводимого над GF(2), является примером расширенного поля GF(24), которое может быть обозначено также GF(16).

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

Группа, которая состоит из всех степеней одного из ее элементов, называется циклической группой.

Из рассмотренного свойства конечных полей вытекают два важных следствия:

1. Многочлен x^q^–1–1 имеет своими корнями все q–1 ненулевых элементов поля GF(q), т.е.

В поле GF(q) элемент α, имеющий порядок e = q–1, называется примитивным. Отсюда следует, что любой ненулевой элемент GF(q) является степенью примитивного элемента.

2. Любое конечное поле GF(q) содержит примитивный элемент, т.е. мультипликативная группа GF(q) является циклической.

В прикладных целях обычно используются задания конечных полей в виде кольца вычетов целых чисел по простому модулю p (поле GF(p)) или факторкольца кольца многочленов над полем GF(p)по модулю неприводимого многочлена (поля GF(p^t), t > 1).

Наличие в конечном поле примитивного элемента α позволяет ввести понятие логарифма для ненулевых элементов этого поля. Логарифм элемента β по основанию α определяется как наименьшее целое неотрицательное число k удовлетворяющее равенству β = α ^k.

В настоящее время задача вычисления логарифма в конечном поле в общем случае не имеет достаточно эффективных алгоритмов решения и по этой причине, наряду с задачей разложения на множители, используется при построении стойких криптографических алгоритмов и протоколов.

⇐ Предыдущая 1 2 3 4 5 6 7 8910 Следующая ⇒