поле вычетов по простому модулю
Инструменты сайта
Основное
Навигация
Информация
Действия
Содержание
Поля Галуа
Структура конечного поля
Существование конечных полей, т.е. полей, состоящих из конечного числа элементов установлено в пункте ☞ ПОЛЕ.
Нет ли противоречий в этих построенных таблицах?
В самом деле, возможно, что существует не найденная нами цепочка действий, которая приведет к противоречию с каким-то результатом из полученных таблиц. Ответ на этот вопрос оказывается отрицательным: противоречий мы не получим.
Пример. Рассмотрим множество, состоящее из квадратных матрицы второго порядка
Обобщенная теорема Ферма
Пример конечного поля
Ответ. Нет.
Подсказка: см. доказательство теоремы ☞ ЗДЕСЬ.
Пример. Для
Теорема. Конечные поля одинакового порядка изоморфны, т.е. между элементами этих полей можно установить такое взаимно-однозначное соответствие, которое сохраняет результаты сложения и умножения элементов.
Доказательства этой теоремы, приведенные в литературе, оказались трудны для моего понимания, поэтому я просто привожу проверку этого утверждения на примере ☞ ЗДЕСЬ.
Полиномы, неприводимые по модулю
В настоящем пункте под неприводимым полиномом понимается нормализованный неприводимый полином.
Непосредственным следствием теоремы 2 является
Доказательство (и критерий, часто позволяющий быстро отыскать такие корни) ☞ ЗДЕСЬ.
Полиномы над GF(2)
Заметим, что любой (не тождественно нулевой) полином из такого поля всегда нормализован.
Вывод. Поле Галуа одновременно обладает свойствами циклической группы, линейного пространства и алгебраического уравнения с целыми коэффициентами. С одной стороны, все ненулевые элементы поля можно представить как степени одного единственного. С другой стороны, операция сложения полиномов эквивалентна сложению векторов, составленных из их коэффициентов. Заметим, что в линейном пространстве не вводится аналога умножения векторов — такого, чтобы при умножении двух векторов получался снова вектор. С третьей стороны, все элементы поля разбиваются на подмножества, каждому из которых соответствует неприводимое алгебраическое уравнение — говорят, что элементы поля являются корнями неприводимых над GF(2) полиномов.
Решение ☞ ЗДЕСЬ.
Решение ☞ ЗДЕСЬ.
Полиномы над GF(p)
Источники
[1]. Чеботарев Н. Основы теории Галуа. Часть I. М.-Л.ОНТИ. 1934.
[2]. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.
[3]. Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.Мир. 1988.
[4]. Ротман Т. Короткая жизнь Эвариста Галуа. Scientific American. N 1, 1983, cc. 84-93. Текст ☞ ЗДЕСЬ.
Арифметика полей Галуа для кодирования информации кодами Рида-Соломона
Коды Рида-Соломона относятся к недвоичным, блочным, помехоустойчивым кодам и могут использоваться в области хранения информации для избегания потери поврежденной информации.
На хабре есть пост посвященный кодированию информации кодами Рида-Соломона, но для примера автор использует простое поле Галуа. В данной статье описывается работа с расширенными полями Галуа, в частности GF(2^m), которые рационально использовать для цифровой информации. С моей аналогичной реализацией кодирования, декодирования, исправления ошибки можно ознакомится здесь.
При работе с кодами Рида-Соломона процент избыточных символов в 2 раза больше восстанавливаемого объема данных. Объясню на примере: если мы имеем последовательность из 10 символов и хотим иметь возможность восстановить ошибки в 3-ех из них (30% исходной информации), то нам нужно хранить 10+3*2=16 символов. Назовем каждую переменную: n = 10, количество информационных символов; f = 3, количество восстанавливаемых символов; g = 16, длина закодированной последовательности. Таким образом, формулу можно записать так: g = n + f * 2.
Поля Галуа
Для работы с информацией при кодировании и декодировании данных все арифметические операции выполняются в полях Галуа. Применяется так называемая полиномиальная арифметика или арифметика полей Галуа. Таким образом, результат любой операции также является элементом данного поля. Конкретное поле Галуа состоит из фиксированного диапазона чисел. Характеристикой поля называют некоторое простое число p. Порядок поля, т.е. количество его элементов, является некоторой натуральной степенью характеристики pm, где m∈N. При m=1 поле называется простым. В случаях, когда m>1, для образования поля необходим еще порождающий полином степени m, такое поле называется расширенным. GF(p^m) – обозначение поля Галуа.
Для работы с цифровыми данными естественно использовать p=2 в качестве характеристики поля. При m=1 элементом кодовой последовательности будет бит, при m=8 – 8 бит, то есть байт. Собственно коды Рида-Соломона работающие с байтами и являются наиболее распространенными.
Перед тем как переходить к операциям кодирования и декодирования разберемся с арифметикой полей Галуа на примере GF(2^3). Данное поле состоит из чисел от 0 до 7.
Операция сложения
Самой простой является операция сложения, которая является простым побитовым сложение по модулю 2 (ХОR).
Операция умножения
К сожалению, операция умножения гораздо сложнее, чтобы ее осуществить, необходимо преобразовать числа в полиномиальную форму.
Как можно заметить число в полиномиальной форме представляет собой многочлен, коэффициентами которого являются значения разрядов в двоичном представлении числа.
Перемножим два числа в полиномиальной форме:
5∙7=(x^2+1)∙(x^2+x+1)=x^4+x^3+x^2+x^2+x+1=x^4+x^3+x+1=11011=27
Итак, во-первых, следует заметить, что даже в полиномиальной форме осуществляется сложение по модулю 2, поэтому x^2+x^2=0. Во-вторых, результат умножения 27 не входит в используемое поле GF(2^3) (оно же состоит из чисел от 0 до 7, как было сказано выше). Чтобы бороться с этой проблемой, необходимо использовать порождающий полином. Порождающий полином является неприводимым, то есть простым (по аналогии с простыми числами делится без остатка на 1 и на самого себя). В арифметике полей Галуа неприводимым полиномом является аналог простых чисел. Используем для примера порождающий полином f(x)=x^3+x+1.
Также предполагается, что x удовлетворяет уравнению f(x)=x^3+x+1=0
Вернемся к примеру с умножением:
Составим таблицу умножения:
Операция деления
Операцию деления в полиномиальной форме понять, возможно, но достаточно тяжело. Поэтому гораздо лучше осуществлять его по таблице умножения.
Большое значение имеет таблица степеней элементов поля Галуа. Возведение в степень также осуществляется в полиномиальной форме, аналогично умножению.
Таким образом, составим таблицу степеней:
Таблица степеней обладает цикличностью: седьмая степень соответствует нулевой, значит восьмая соответствует первой и т.д. При желании можно это проверить.
В полях Галуа существует понятие примитивного члена – элемент поля, чьи степени содержать все ненулевые элементы поля. Просмотрев таблицу степеней видно, что этому условию соответствуют все элементы (ну кроме 1 естественно). Однако это выполняется не всегда, для примера приведу таблицу степеней для GF(16).
Для полей, которые мы рассматриваем, то есть с характеристикой 2, в качестве примитивного члена всегда выбирают 2. Учитывая его свойство, любой элемент поля можно выразить через степень примитивного члена.
Пример: 5=26, 7=25
Воспользовавшись этим свойством, и учитывая цикличность таблицы степеней, попробуем снова перемножить числа:
5∙7=2^6∙2^5=2^(6+5)=2^11=2^(11 mod 7)=2^4=6
Результат совпал с тем, что мы вычислили раньше.
А теперь выполним деление:
6÷5=2^4÷2^6=2^(4-6)=2^(-2)=2^((-2)mod 7)=2^5=7
Полученный результат тоже соответствует действительности.
Ну и для полноты картины посмотрим на возведение в степень:
5^2=(〖2^6)〗^2=2^(6∙2)=2^12=2^(12 mod 7)=2^5=7
Опять неожиданно получился такой же результат.
Такой подход к умножению и делению гораздо проще, чем реальные операции с использование полиномов, и для них нет необходимости хранить большую таблицу умножения, а достаточно лишь строки степеней примитивного члена поля.
Сравнения, система вычетов, решение линейных систем по модулю
Содержание
Сравнения по модулю [ править ]
Будем рассматривать целые числа в связи с остатками от деления их на данное целое число m, которое назовем модулем. Каждому целому числу отвечает определенный остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются сравнимыми по модулю m.
Сравнимость для a и b записывается так :
[math]a \equiv b(mod \text < >m)[/math]
Сравнимость чисел a и b по модулю m равносильна:
Арифметика сравнений [ править ]
Свойства сравнений [ править ]
Полная и приведенная система вычетов [ править ]
Числа равноостаточные(сравнимые по модулю m) образуют класс чисел по модулю m. Из такого определения следует, что всем числам класса отвечает один остаток r, и мы получим все числа класса, если в форме [math]mt + r [/math] заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел.
Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.
Согласно 10 свойству сравнений, числа одного класса по модулю m имеют одинаковый НОД. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим приведенную систему вычетов по модулю m.
Решение линейных систем по модулю [ править ]
Примеры решения [ править ]
Дискретная математика. KursRab. Мультипликативно-обратные элементы в поле вычетов
Пояснительная записка к курсовой работе
по дискретной математике.
Мультипликативно обратные элементы в поле вычетов.
СОДЕРЖАНИЕ
ПРОВЕДЕНИЕ АНАЛИЗА СВОЙСТВ, ХАРАКТЕРИЗУЮЩИХ ЗАДАННУЮ ТЕМУ
Полем называется множество с двумя определёнными операциями — сложением и умножением, причем имеют место следующие аксиомы:
Поле с конечным числом элементов называют полями Галуа GF(q).
Для представителей можно ввести операции сложения и умножения по mod(4):
| 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | ||
| 0 | 0 | 1 | 2 | 3 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 3 | 2 | 1 | 0 | 1 | 2 | 3 |
| 2 | 2 | 3 | 0 | 1 | 2 | 0 | 2 | 3 | 1 |
| 3 | 3 | 2 | 1 | 0 | 3 | 0 | 3 | 1 | 2 |
Наибольший общий делитель двух заданных положительных чисел s и t может быть вычислен с помощью итеративного применения алгоритма деления. Эта процедура известна как алгоритм Евклида. Предположим, что t (1) t+t (1)
где остановка процесса наступает при получении нулевого остатка. Последний ненулевой остаток t ( n) равен наибольшему общему делителю. Этот факт будет доказан в следующей теореме. Матричные обозначения позволяют кратко записать шаги алгоритма Евклида в виде:
Теорема. (Алгоритм Евклида).[2][3] Для двух заданных положительных чисел s и t, где s>t, пусть s (0) =s и t (0) =t. Решение рекуррентных уравнений:
при r=1, …, n даётся величиной
где n равно наименьшему целому числу, для которого t ( n) =0.
Так как t ( r+1) ( r) и все остатки неотрицательны, то в конце концов наступит n, для которого t ( n) =0, так что завершение работы алгоритма произойдёт обязательно, легко проверить, что
так что s ( n) должно делить оба числа s и t и, следовательно, делит НОД[s, t]. Далее
Это завершает доказательство.
Из этой теоремы вытекает несколько важных следствий. Пусть
Тогда получаем следствие:
Для любых чисел s и t найдутся такие целые числа a и b, что
Достаточно доказать следствие для положительных s и t. Так как
и s ( n) =НОД[s, t], то утверждение выполняется при 
и 
.
Следствие 2:
Получаемые в процессе алгоритма Евклида матричные элементы 
и 
удовлетворяют равенствам:
Используя выписанные выше выражения для обратной матрицы и обращая первое равенство из доказательства прошлого следствия получаем
Утверждение вытекает отсюда непосредственно.
Доказательство.
Нахождение обратных элементов с использованием алгоритма Евклида[1]
Так как у поля модуль m – простое число, то для нахождения обратного элемента для элемента x можно найти уравнение ax+my=1. Тогда слагаемое my равно нулю (вычисления производятся по модулю m). Следовательно, элемент a является обратным к элементу x.
Нахождения обратных чисел можно реализовать с помощью малой теоремы Ферма.
ВЫВОДЫ
В соответствии с вышеописанными теоремами программа должна находить обратный элемент используя малую теорему Ферма или алгоритм Евклида. Программа должна работать для достаточно широкого спектра значений модуля, по которому производятся вычисления и элемента для которого вычисляется обратный элемент. То есть программа не должна вычислять обратный элемент, например, только для чисел, которые меньше 3 или 5 (для этих чисел обратный элемент в поле вычетов по такому маленькому модулю можно вычислить и без компьютера). То есть программа должна быть предназначена для вычисления обратного элемента для достаточно большого (в разумных пределах) числа. Также программа должна проверять корректность входных данных. То есть, в случае, если НОД введённого модуля и элемента должно равняться единице, в противном случае программа должна сообщать, о том, что данный элемент не имеет обратного.
ПОСТРОЕНИЕ ПРОГРАММНОЙ МОДЕЛИ
Напишем программу нахождения обратного числа для данного элемента в данном поле.
Поле возьмём по модулю простого числа.
Выбор метода
По началу кажется, что нахождение обратных элементов в поле проще всего реализовать с помощью малой теоремы Ферма. Но на практике из-за ограниченности разрядной сетки машины этот алгоритм использовать достаточно затруднительно. Например, для вычисления обратного элемента для 9 в поле по модулю 23:
9 21 =109418989131512359209.
Можно приводить числа по данному модулю после каждого умножения, что решит эту проблему для не очень больших чисел. Но для достаточно больших чисел эта проблема останется.
Причём значение имеет даже последняя девятка. хранения такого большого числа в компьютере и выполнения с ним операций вызывает определённые трудности. Следовательно, лучше реализовать алгоритм Евклида, работающий со стандартными типами данных, хотя для некоторых случаев (при небольших числах) алгоритм, построенный на следствии малой теоремы Ферма будет подходить больше.
Построение алгоритма программы
Напишем программу, реализующую нахождение обратного элемента с использованием алгоритма Евклида. По алгоритму Евклида (учитывая, что НОД[a, m]=1) выполняются следующие соотношения:
Для нахождения уравнения ax+my=1 выразим с помощью предпоследнего уравнения число 1 через t ( n-1) и t ( n-2) :
1= t (n-1) — Q (n+1) * (t (n-2)- Q (n) t (n-1) )
1= (1+Q (n+1) *Q (n) )*t (n-1) — Q (n+1) *t (n-2)
1= — Q (n+1) *t (n-2) + (1+Q (n+1) *Q (n) )*t (n-1)
Как отсюда видно множитель — Q ( n+1) «перешёл» из правого слагаемого (из слагаемого с большим) в левое слагаемое (с меньшим индексом). Проверим дальше. Теперь выразим 1 через t ( n-2) и t ( n-3) :
1= — Q (n+1) *t (n-2) + (1+Q (n+1) *Q (n) )*t (n-1)
1= — Q (n+1) *t (n-2) + (1+Q (n+1) *Q (n) )*( t (n-3) — Q (n-1) t (n-2) )
1= (1+Q (n+1) *Q (n) )*t (n-3) + ((1+Q (n+1) *Q (n) )*( — Q (n-1) ) — Q (n+1) )t (n-2) (1)
Как видно снова множитель из правого слагаемого перешёл в левое слагаемое. Правое слагаемое составилось из прошлого множителя правого слагаемого, умноженного на следующее частное, и прошлого левого слагаемого. То есть, если на данном шаге перед слагаемым t с меньшим индексом стоит множитель a, а перед другим слагаемым – b, то для следующего шага перед слагаемым с меньшим индексом будет стоять b, а перед другим слагаемым b*a-a.
Графическая схема алгоритма, осуществляющего нахождение НОД с помощью алгоритма Евклида:
Этот алгоритм при использовании для нахождения обратных элементов в качестве числа t должен получать модуль в котором производить вычисления, а в качестве числа s элемент, для которого необходимо найти обратный элемент. Тогда в выходной переменной s2 будет получаться обратный элемент для числа s. Естественно при получении входных данных модуль t должен быть таким, что полученная структура была бы полем. То есть число t должно быть простым. (когда t – простое, то НОД[t, s]=1 и в полученном выражении слагаемое с t сокращается).
Составление программы на BORLANDC++3.1
Для хранения модуля и введённого числа подходит тип long (для того, чтобы программа могла работать с более длинными числами).
Для реализации стека был составлен специальный модуль, в котором были реализованы стандартные процедуры работы со стеком (PUSH (добавление элемента в стек), POP (извлечение элемента из стека), EMPTY (проверка стека на пустоту)).
С использованием стека была разработана процедура, вычисляющая с помощью алгоритма Евклида НОД двух чисел и возвращающая также полученное уравнение.
ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ
Для проверки работоспособности программы достаточно вычисленный обратный элемент умножить на данный элемент и взять остаток от деления полученного числа на модуль, по которому производились вычисления. Если получится единица, то обратный элемент вычислен верно. Для сравнения были произведены вычисления с использованием малой теоремы Ферма и калькулятора.
(элемент, для которого находится обратный эдемент)
(модуль, по которому производятся вычисления)
для вычисленного с помощью программы:
1
Как видно в таблице весь последний столбец занят единицами, кроме той строки, для которой не существует обратного элемента. Следовательно, программа работает верно.
ВЫВОДЫ ПО ВСЕЙ КУРСОВОЙ РАБОТЕ
Анализируя составленную программу можно сделать вывод, что с помощью алгоритма Евклида можно достаточно быстро найти обратный к данному элемент по данному модулю. При тестировании программы работала с числами около одного или двух миллиардов практически мгновенно. Никакого замедления не было замечено.
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
Поле вычетов
Как было показано в разд.1.2.3, полная система вычетов является коммутативным кольцом.
Единицей мультипликативной полугруппы является класс 1, поскольку 1*a=a*1=(1a) mod n=a.
Однако делители нуля не имеют обратных элементов. Действительно, пусть n – составное число и a,b – делители нуля: a*b=b*a=0; a¹0, b¹0; и пусть a имеет обратный элемент c: a*c=c*a=1. Тогда b=b*1=b*(a*c)=(b*a)*c=0*c=0, что противоречит предположению b¹0.
Следовательно, мультипликативная полугруппа не образует группу и полная система вычетов не является полем.
Однако, если ввести ограничение, что n – простое число, то мультипликативная полугруппа без нуля образует коммутативную (абелеву) группу и полная система вычетов будет является полем.
Так как операция умножения на множестве Zn коммутативна, то для доказательства того, что является полем требуется доказать утверждение: если n – простое число, то для любого aÎ<1,2,…,n-1>, (a¹0), существует bÎ<1,2,…,n-1> (b¹0), такое что a*b=b*a=(ab) mod n =1.
Поскольку a является полем.
В этом случае можно ввести операцию деления, кроме деления на нуль