Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Арифметика целых чисел и полей Галуа




Теория чисел, или высшая арифметика — раздел математики, изучающий целые числа и сходные объекты.

Множество целых чисел (-n, … -1, 0, 1, 2, …n)определяется как замыкание множества натуральных чисел относительно арифметических операцийсложения (+) и вычитания (−). Таким образом, сумма, разность и произведение двух целых чисел дает снова целые числа. Оно состоит из натуральных чисел (1, 2, 3…), чисел вида и числа ноль.

Группа целых чисел, последовательно пронумерованных от 0 до 2n - 1, содержащая 2n элементов, называется полем Галуа и обозначается GF(2n). Поле Галуа – конечное коммутативное поле.

В поле Галуа определены сложение, вычитание, умножение и деление на ненулевые элементы. Существует нейтральный элемент для сложения - 0 - и для умножения - 1.

Члены групп в обязательном порядке подчиняются ассоциативному (a + (b + c) = (a + b) + c), коммутативному (a + b = b + a) и дистрибьютивному (a × (b + c) = (a × b) + (a × c)) законам, иобрабатываются следующим образом:

1) сумма двух любых членов группы всегда присутствует в данной группе;

2) для каждого члена «а» группы существует тождественный (identity) ему член, обычно записываемый как «e», удовлетворяющий следующему условию: a + e = e + a = a;

3) для каждого члена «a» группы, существует обратный (inverse) ему член «-a», такой, что: a + –a = 0.

Если группа подчиняется коммутативному закону, то она называется Абелевой группой или коммутативной.

Сложение в полях Галуа осуществляется без учета переноса и сумма двух членов группы равна: c = (a + b) % 2n, где операция «%» обозначает взятие остатка. Например: (2 + 3) % 4 = 1. Математически это называется «сложением по модулю 4». Сложение по модулю два в полях Галуа тождественно вычитанию и реализуется битовой операцией XOR.

Результат деления одного члена группы на другой, не равный нулю, член в обязательном порядке должен присутствовать в данной группе (см. правило), то несмотря на то, что деление осуществляется в целых числах, оно всегда будет точным (и никогда не будет округленным). Следовательно, если c = a * b, то a = c/b. Другими словами, умножение и деление непротиворечивым образом определено для всех членов группы, за исключением невозможности деления на нуль, причем расширения разрядной сетки при умножении не происходит.

В вычислительной технике наибольшее распространение получили поля Галуа с основанием 2, что объясняется естественностью этих полей с точки зрения машинной обработки, двоичной по своей природе.

Умножение в полях Галуа определяется не через сложение. Функция «настоящего» умножения Галуа настолько сложна и ресурсоемка, что для упрощения ее реализации прибегают к временному преобразованию полиномов в индексную форму, последующему сложению индексов, выполняемому по модулю GF, и обратному преобразованию суммы индексов в полиномиальную форму. В конечном счете, при реализации функции умножения получают то же самое сложение только в профиль: a * b будет равно а, если b четно, и нулю, если b нечетно.

Индекс в данном случае – это показатель степени при основании два, дающий искомый полином. Например, индекс полинома 8 равен 3 (23 = 8), а индекс полинома 2 равен 1 (21 = 2). Легко показать, что a * b = 2i * 2j = 2(i+j). В частности, 8 * 2 = 23 * 21 = 2(3+1) = 24 = 16.

Т.е. арифметика Галуа не оперирует понятиями привычной нам арифметики: например, уравнения типа 2x = 3 в целых числах не разрешимы и ряд индексов не соответствует никаким полиномам! Но в силу того, что количество полиномов всякого поля Галуа равно количеству всевозможных индексов, мы можем определенным образом сопоставить их друг другу, не принимая во внимание тот факт, что с точки зрения обычной математики такое действие не имеет никакого смысла. Конкретная схема сопоставления может быть любой, главное - чтобы она была внутренне непротиворечивой, то есть удовлетворяла всем правилам групп, перечисленным выше.

Деление в полях Галуа осуществляется практически точно так, как и умножение, с той лишь разницей, что индексы не прибавляются, а вычитаются друг из друга: a/b = 2i/2j = 2(i-j). Деление на нуль не допускается.

Арифметика поля Галуа широко используется в криптографии. В нем работает вся теория чисел, поле содержит числа только конечного размера, при делении отсутствуют ошибки округления. Многие криптосистемы основаны на GF(p), где p - это большое простое число.

Чтобы еще более усложнить вопрос, криптографы также используют арифметику по модулю неприводимых многочленов степени n, коэффициентами которых являются целые числа по модулю q, где q - это простое число. Эти поля называются GF(qn). Используется арифметика по модулю p(x), где p(x) - это неприводимый многочлен степени n.

 







Дата добавления: 2015-04-19; просмотров: 1247. Нарушение авторских прав; Мы поможем в написании вашей работы!


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2021 год . (0.002 сек.) русская версия | украинская версия