Алrебраические структуры над множеством многочленов
Алrебраические структуры над множеством многочленов - Лекция, раздел Математика, Материалы лекций Математические основы криптологии
Кольцо Многочленов Над Полем Gf(P)
...
Кольцо многочленов над полем GF(p)
Определение 1.17. Кольцо, образованное многочленами над полем GF(p), называется кольцом многочленов над конечным по
Для кольца GF[x] справедливы арифметические операции сложения, умножения, сравнения, деления с остатком, делимость.
Два многочлена f(x) и g(x) ÎGF[x] над полем GF(p) считаются
равными тогда и только тогда, когда
f (x)
n
=å
i =0
i
ai x
,g ( x)
n
=å
i=0
i
bi x и
аi. = bi, 0 ≤ i < n .
Сумма многочленов f(x) и g(x) определяется равенством:
n
f ( x) +g ( x) =å(ai
i
+ b ) xi ,
Произведение многочленов
i=0
таких, что
f (x)
n
=å
i =0
i
ai x
,g ( x)
n
=å
i=0
i
bi x
f (x) g ( x)
n+m
=å
k
ck x
,ck =
åaibj
k =0
i+ j =k
0 ≤ i ≤ n,, 0 ≤ j ≤ m.
Деление: g(x) ÎGF[x] делит f(x) ÎGF[xJ, если существует многочлен
h(x) ÎGF[x], такой, что f(x) = g(x)h(x).
Деление с остатком. Пусть g(x)≠0 ÎGF[x], тогда для каждого f(x) Î
GF[x] существуют такие q(x) и h(X) ÎGF[x], что
f(x)=q(x)g(x)+h(x), где deg(h)< deg(g) .
В отмеченных равенствах операции сложения и умножения коэффициентов α и β выполняются по модулю простого числа р.
При этом коэффициенты полиномов, являющихся результатом применения операций над полиномами, принадлежат полю GF(p) .
Конечное поле многочленов над GF(p)
Рассмотрим тип поля GF( p n ), n > 1, который основывается на операциях сложения и умножения по модулю неприводимых многочленов
над GF(p) степени n.
В таком поле число элементов равно
p n , а элементы описываются
многочленами над GF(p) степени не выше n -1 в форме
g(x) =
a0 +a1x1 +... +an-1x
n-1
,
где aj ÎGF(p), i = 0,n -1.
Наивысшая степень элемента х равна n -1 , так как операции сложения и умножения многочленов g(x) определены по модулю неприводимого многочлена f(x) над GF(p) степени n. При этом сложение и умножение элементов aj выполняется по модулю р.
Пример .Построим поле GF( p n ) = GF( 22 ). Возьмем неприводимый
многочлен f(x) =
x2 + х + 1 над полем GF(2). Тогда поле GF( 22
= 4) будет
иметь 4 элемента, описываемых многочленами: 0, 1, х, х + 1 (т.е. все многочлены степени, меньшей 2).
Определение 1.18. Два поля GF( p n ), отличающиеся лишь обозначениями элементов, называются изоморфными.
Все поля GF( p n ) изоморфны полю многочленов над GF(p)
по модулю неприводимого многочлена степени n над полем GF(p) [2].
Любое поле GF( p n ) изоморфно конечному полю, полученному
Алгоритм передачи секретного ключа по открытому каналу
В середине 70-х годов произошел настоящий прорыв в современной
криптографии – появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь от
Алгоритм Евклида
Алгоритм Евклида дает правило вычисления наибольшего общего делителя
(НОД) 2-х натуральных чисел. (a,b)= d , где d – НОД НОК – наименьшее общее кратное
Получение простых чисел.
По мере того как мы будем изучать курс «Математические основы криптологии» мы будем возвращаться к этой теме.
Задача получение простых чисел во многом зависит от того как с
Проверка простоты чисел Мерсенна
Числами Мерсенна называются числа вида М(p) = 2p - 1, pÎN.
Задача для чисел Мерсенна - поиск в ряду э
Алгоритм Бухштаба
Данный алгоритм приведен из книги Бухштаба А.А. "Теория чисел" [4]. Пусть задано натуральное нечетное число n, n ≥ 9, которое необходимо разложить на 2
Алгоритм Ферма
Алгоритм Ферма похож на алгоритм Бухштаба и является эффективным, если у раскладываемого числа n есть делитель (который
Функция Эйлера
Имеется целое, положительное число m. Оно может быть как составным, так и простым.
Функцию Эйлера принято обозначать, практически во всех учебниках как:
Мультипликативная функция
Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по фо
Числовая функция
Это функция устанавливающая целую часть от некоторого рационального числа
[a] – обозначение
может быть как положительное, так и отрицательное число
Сравнимость по модулю. Модулярная арифметика
Понятие «модулярная арифметика» ввел немецкий ученый Гаусс.
Модульная арифметика аналогична обычной арифметике: она коммутативна, ассоциатив
Свойства операций сравнения
В криптографии существуют шифры и по простому модулю и по составному модулю.
Нужно знать когда применять простой модуль, а когда состав
Кольца и поля
Алгебраические структуры с двумя бинарными операциями - сложение и умножение.
Определение 1.7. Множество S называется кольцом, е
Характеристика поля
Определение 1.12. Если в поле Fq все ненулевые элементы имеют аддитивный порядок k, то говорят, что поле Fq имеет характеристику k. Обозначение. р - простое число.
Вычисление обратных элементов
В арифметике действительных чисел просто вычислить обратную величину a−1 для ненулевого a:
a-1 = 1/a или a? a-1 = 1.
Расширение полей
Рассмотрим, какова связь полей GF(p) и GF( p n ).
Пусть F - поле. Подмножество К поля Р, которое само является полем относительно операций поля Р, на
Pound; b£ n-1
Если для каждого простого делителя p числа n-1 справедливы следующие утверждения:
(1) bn-1≡ 1(mod n),
Числа Кармайкла
Может ли составное нечетное число n быть псевдопростым по всем взаимно-простым с ним основаниям b? Забегая вперед, скачем, что «да».
Заметим
Процедура получения устойчивых простых чисел
1. Генерируются простые числа s,t
2. Получаем простое число r такое что, (r-1) делит t без остатка: r-1|t
На основе этих двух операций получаем про
Алгоритм асимметричного шифрования RSA
Алгоритм RSA предложили в 1978 г. 3 автора: Райвест (Rivest), Шамир (Shamir) и Адлеман (Adleman). RSA является алгоритмом с открытым ключом, работающим в режимах шифрования данных и
Раунд преобразования алгоритма RIJNDAEL
RIJNDAEL выполняет серию однотипных раундов преобразования шифруемого блока. Шифруемый блок и его промежуточные состояния в ходе преобразования представляются в виде квадратной матр
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов