Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Поле, конечное поле, расширение конечного поля.
Поля. Множество S называется полем, если + и * определены для "(α, β) элементов из S и выполняются следующие аксиомы. 1) Замкнутость по двум операциям (сложения и умножения). 2) Множество S является абелевой группой относительно +. 3) Множество S является абелевой группой относительно * 4) Выполняется дистрибутивность: для любых α,β,уÎS α(β+y)=βα+yα . Примером поля являются множество Q рациональных чисел, множество R - действительных чисел. Отметим важное свойство поля - разрешимость линейных уравнений в поле. Линейным уравнением относительно X над полем F называется выражение вида αх+β=0, где 0,α,βÎF. Если α≠0, то линейное уравнение αх+β=0 имеет единственное решение в F. Конечные поля. Поле Fq называется конечным, если множество его элементов конечно. Число q называется порядком конечного поля. Так как поле Fq, по определению, является мультипликативной группой, то каждый ненулевой элемент α поля Fq имеет мультипликативный порядок. Примитивным элементом поля Fq называется элемент, у которого мультипликативный порядок точно равен q-1. Любое поле Fq* содержит примитивный элемент. Мультипликативная группа Fq ненулевых элементов произвольного конечного поля Fq циклическая. Примитивный элемент поля Fq является образующим элементом циклической группы F*q. Если существует целое kÎN, такое, что ka=0, α ÏFq, то k называется аддитивным порядком элемента α. Ненулевые элементы поля Fq имеют один и тот же аддитивный порядок. Теорема о существовании и единственности конечных полей. Для каждого простого числа q и каждого натурального числа n существует конечное поле GF(qn) из qn элементов. Поле GF(qn) является расширением поля GF(q). qn называется порядком поля GF(qn), натуральное число n - степенью поля, а простое число q - характеристикой поля GF(qn).
Способы нахождения обратных элементов I . a) Выполняется перебор возможных значений в интервале a-1= , до тех пор, пока не будет найдено такое a-1, что будет выполняться (a*a-1)modm=1. б)Вариантом переборного алгоритма также является следующий алгоритм. Если НОД (a,m) = 1, то существует а-1 и a*a−1modm=(1 + m*t) mod m, где Шаги алгоритма. 1. Если НОД(a, m) ≠1, то обратный элемент не существует. 2. Для любого t Î[0, ¥) вычисляются следующие действия. а. Если значение выражения не является натуральным числом, то переход к пункту 2. б. Иначе это выражение задает обратный элемент: a-1=( )mod m, выход. Алгоритм будет конечен в том случае, когда выполняется условие условие существования обратного элемента. II Можно вычислить для элемента a обратный элемент a-1 и при знании функции Эйлера φ(m), где (a,m) = 1. Так как aj(m)modm 1 и (a·a−1)modm≡1, то aj(m)modm=(a*a-1)modm=> |
Последнее изменение этой страницы: 2019-04-21; Просмотров: 198; Нарушение авторского права страницы