Построение поля Галуа. Умножение полинома на фиксированный элемент поля. Деление полинома на фиксированный элемент поля

Содержание

Введение

Испокон веков не было ценности большей, чем информация. ХХ век - век информатики и информатизации. Технология дает возможность передавать и хранить все большие объемы информации. Это благо имеет и оборотную сторону. Информация становится  более уязвимой по разным причинам:

·  возрастающие объемы хранимых и передаваемых данных;

·  расширение круга пользователей, имеющих доступ к ресурсам ЭВМ, программам и данным;

·  усложнение режимов эксплуатации вычислительных систем.

Поэтому все большую важность приобретает проблема защиты информации от несанкционированного доступа (НСД) при передаче и хранении. Сущность этой проблемы - постоянная борьба специалистов по защите информации со своими "оппонентами". В настоящее время большое развитие получил процесс защиты информации заключающийся в том, что информация должна быть передана в виде специальных шифров (кодов), которые формируются по определенному правилу и зная это правило на приемной стороне можно провести дешифрование информации.

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

В системах передачи данных дискретное сообщение представляет собой последовательность символов из заданного конечного алфавита. Требования взаимной однозначности кодирования и декодирования при отсутствии ошибок или их наличии обладают особыми ограничениями на конечный выбор символов. Наиболее значимые успехи кодирования, когда использованный алфавит являлся конечным, проявил знаменитый французский математик Эваристо Галуа, он давал определение поля, что поле -  есть множество, элементы которого можно складывать, вычитать, умножать и делить, при этом выполняются обычные правила арифметики. Классическими примерами являются поля рациональных, действительных и комплексных чисел. Среди всевозможных полей встречаются так называемые конечные поля, то есть поля с конечным числом элементов. Они впервые были введены и исследованы ученым Галуа, в связи с чем их ещё называют полями Галуа и обозначают GF(q). В дальнейшем сфера применения конечных полей неизмеримо расширилась. В настоящее время их теория представляет собой фундамент теоретической информатики, на который опираются многочисленные приложения: теория кодирования, криптография, теория быстрых умножителей, теория разделения сигналов от нескольких источников, теория генераторов случайных чисел и т.д.

Далее, построение поля Галуа рассмотрим более подробно.

Построение поля Галуа GF()

Поле – называется множество элементов в котором определены две операции сложение и умножение, причем имеют место следующие аксиомы:

1.  Множество образует абелеву группу по сложению.

2.  Поле замкнуто относительно умножения, и множество ненулевых элементов образует абелеву группу по умножению.

3.  Закон дистрибутивности.

Все эти поля содержат бесконечное множество элементов. Мы интересуемся полями, содержащими конечное число элементов.

Поле с q элементами, если оно существует называется конечным полем или полем Галуа GF(q). Любые действия конечных порядков требуют конкретного задания поля, изображение или представление всех элементов поля и определение его арифметики. При фиксированном значении q=const, все способы задания конечного поля изоморфны.  

Для построения конечных полей необходимо знать их конструкцию, на практике используют 2 конструкции.

- простое поле, где p- простое число F(q)= GF(p);

- расширенное поле GF().