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

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

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





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

Множество целых чисел (-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; просмотров: 1856. Нарушение авторских прав; Мы поможем в написании вашей работы!




Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


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


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...


Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Опухоли яичников в детском и подростковом возрасте Опухоли яичников занимают первое место в структуре опухолей половой системы у девочек и встречаются в возрасте 10 – 16 лет и в период полового созревания...

Способы тактических действий при проведении специальных операций Специальные операции проводятся с применением следующих основных тактических способов действий: охрана...

Искусство подбора персонала. Как оценить человека за час Искусство подбора персонала. Как оценить человека за час...

Типовые ситуационные задачи. Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт. ст. Влияние психоэмоциональных факторов отсутствует. Колебаний АД практически нет. Головной боли нет. Нормализовать...

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

Признаки классификации безопасности Можно выделить следующие признаки классификации безопасности. 1. По признаку масштабности принято различать следующие относительно самостоятельные геополитические уровни и виды безопасности. 1.1. Международная безопасность (глобальная и...

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