46 (Вопросы по разным темам с ответами (программирование))

46. Поля Галуа и алгебра полиномов. Примеры применения в криптографии.

Непустое множество G с заданной на нём бинарной операцией называется группой, если выполнены следующие аксиомы:

1. Ассоциативность: для любых a, b и c из G верно (a · b) · c = a · (b · c).

2. Замкнутость: для любых a и b из G (a · b) принадлежит G.

3. Наличие нейтрального элемента: в G существует элемент e такой, что для всех a из G справедливо e · a = a · e = a.

4. Наличие обратного элемента: для любого a из G найдётся элемент a^-1 из G, называемый обратным, такой, что a · a^-1 = a^-1 · a = e.

Группа, для которой a·b = b·a выполнено для произвольных элементов a, b из G, называется коммутативной, или абелевой группой.

Подгруппа — подмножество H группы G, которое является группой относительно операции, определённой в G.

Порядок группы — мощность G (т.е. число её элементов).

Примеры:

Целые числа с операцией сложения.

Положительные рациональные числа с операцией умножения.

Циклические группы состоят из степеней a0 = e, a, a2, … одного элемента a. Такие группы всегда коммутативны. Пример: целые числа по сложению и группа корней из единицы.

Кольцо - непустое множество R, для элементов которого определены две операции - сложение и умножение, сопоставляющие любым двум элементам а, b из R, взятым в определённом порядке, один элемент а + b из R - их сумму и один элемент ab из R - их произведение, причём предполагаются выполненными следующие аксиомы:

1. Множество R является аддитивной абелевой группой относительно операции сложения.

2. Замкнутость для умножения: для любых a и b из R (a · b) принадлежит R.

3. Ассоциативность для умножения: для любых a, b и c из R верно (a · b) · c = a · (b · c).

4. Дистрибутивность: а (b + с) = ab+ac, (b + с) а = ba + са.

Примеры:

1) множество всех целых положительных, отрицательных чисел и нуля;

2) множество всех чётных чисел и вообще целых чисел, кратных данному числу n;

3) множество всех рациональных чисел;

4) всех действительных чисел;

5) всех комплексных чисел;

Если в кольце выполняется равенства ab = ba, то кольцо коммутативно (примеры 1-5).

Ассоциативное коммутативное тело принято называть полем (примеры 3 - 5).

Множество М элементов кольца R называют подкольцом, если М само является К. относительно операций, определённых в R.

Подгруппа H – некоторое подмножество элементов группы G, если оно удовлетворяет всем аксиомам группы.

Пусть H является подгруппой группы G. Два элемента g1 и g2 входят в один и тот же класс смежности по подгруппе H в G только тогда, когда произведение g1^-1*g2 принадлежит G.

Идеал I – подмножество элементов кольца со следующими свойствами:

1. I является подгруппой аддитивной группы кольца R;

2. Для любых элементов a из I и r из R произведения ra и ar лежат в I.

Смежные классы, образованные по идеалу – классы вычетов.

Элементы а и b кольца R называют сравнимыми по идеалу I, если а - b принадлежит I.

Всё кольцо разбивается на классы сравнимых элементов - классы вычетов по идеалу I.

Полем называется множество F с двумя бинарными операциями + (аддитивная операция или сложение) и * (мультипликативная операция или умножение), если оно (вместе с этими операциями) образует коммутативное ассоциативное кольцо c единицей, все ненулевые элементы которого обратимы.

Характеристика поля — наименьшее положительное целое число n, такое что сумма n копий единицы равна нулю: . Если такого числа не существует то характеристика равна 0 по определению. Количество элементов в конечном поле всегда равно pⁿ, степени простого числа

Поле Галуа – кольцо классов вычетов по модулю n, если n – простое число.

Пусть K — произвольное коммутативно-ассоциативное кольцо с единицей. Кольцо A (не обязательно ассоциативное) называется алгеброй над K или K-алгеброй, если для любых элементов , однозначно определено произведение , причем для всех и справедливы соотношения:

1) (k + l)a = ka + la;

2) k(a + b) = ka + kb;

3) k(la) = (kl)a;

4) если существует элемент такой, что ea = ae = a для всех , то e называется единицей алгебры A, а сама алгебра называется алгеброй с единицей;

5) k(ab) = (ka)b = a(kb).

Алгебра над полем. Если K является полем, то, по определению, K-алгебра является векторным пространством над K.

Алгебра полиномов.

Будем рассматривать многочлен от одной переменной x, у которого коэффиценты являются элементами некоторого поля.

Многочлен от одной переменной есть конечная формальная сумма вида

.

Основные свойства многочленов.

1. Многочлены образуют кольцо и обладают всеми свойствами кольца.

2. Многочлен, который можно представить в виде произведения многочленов низших степеней с коэффициентами из данного поля, называется приводимым (в данном поле), в противном случае — неприводимым. Неприводимые многочлены играют в кольце многочленов роль, сходную с ролью простых чисел в кольце целых чисел. Так, верна теорема: если произведение PQ делится на неприводимый многочлен R, a P на R не делится, то тогда Q должно делиться на R. Каждый М. степени, большей нуля, разлагается в данном поле в произведение неприводимых множителей единственным образом (с точностью до множителей нулевой степени). 3. Два многочлена взаимно просты, если их НОД равен 1.

4. Ненулевой полином степени 0 является элементом поля коэффициентов.

5. Если для двух многочленов Р(х) и Q(x) можно найти такой многочлен R(x), что Р = QR, то говорят, что Р делится на Q; Q называется делителем, a R - частным.

5. Если Р не делится на Q, то можно найти такие многочлены Р(х) и S(x), что Р = QR + S, причём степень S(x) меньше степени Q(x).

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

Теорема. Каждый класс вычетов по модулю многочлена f(x) в степени n содержит либо 0, либо многочлен степени меньшей n.

0 является элементом идеала,

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

Теорема. Классы вычетов многочленов по модулю f(x) степени n образуют линейное векторное пространство размерности n над полем коэффициентов.

Некоторые операции:

1. Умножение на скаляр определено как умножение на скаляр каждого коэффициента полинома.

2. Дистрибутивность и ассоциативность следуют из правил умножения и сложения.

3. Размерность пространства коэффициентов равна n.

4. n классов вычетов:

{1}, {x}, {x²},…, {x^n-1} – образующие – порождают все векторное пространство.

В качестве представителей классов вычетов используют полиномы меньшей степени.

Теорема.

Пусть p(x) многочлен над полем F (т. е. многочлен с коэффициентами из поля F). Алгебра многочленов над полем F по модулю p(x) является полем только тогда, когда p(x) неприводим в поле F.

Поле многочленов над полем по модулю неприводимого многочлена степени m называется полем Галуа GF(p^m).

Алгебра полиномов используется как аппарат для построения математического описания линейных переключательных схем (предполагается, что в линейных переключательных схемах информация представлена с помощью элементов поля GF(q)), которые в свою очередь используются в генераторах случайных последовательностей.

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

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

Схема умножения многочлена.

a(x) = a_nxⁿ + a_n-1x^n-1+…+ a₁x + a₀

y(x) = a(x) * h(x)

Схема деления

y(x) = a(x) / h(x).

Схема деления используется при получении кода CRC (кольцевой избыточный код), равный остатку от деления полинома на полином. Код предназначен для защиты файла от изменений.

Исходный полином F(x) делят на магический полином P(x): (F(x)*xⁿ) / P(x) = Q(x) + R(x)/P(x).

Результат: T(x) = F(x)*xⁿ + R(x) пересылают абоненту.

Абонент делит T(x) на P(x). При правильной передаче деление происходит без остатка.

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