12742

Основы теории конечных полей

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа 2 Основы теории конечных полей Цель работы Закрепить знания полученные на лекциях курса €œОсновы криптографии с открытым ключом€œ по разделу €œОсновы теории конечных полей€. Используемое программное обеспечение Для работы используется пр

Русский

2013-05-03

53 KB

21 чел.

Лабораторная работа 2

Основы теории конечных полей

Цель работы

Закрепить знания, полученные на лекциях курса “Основы криптографии с открытым ключом“ по разделу “Основы теории конечных полей”.

Используемое программное обеспечение

Для работы используется программа “Maxima” и дополнительные командные строки для решения каждой из задач. Описания всех лабораторных работ по курсу “Основы криптографии с открытым ключом” содержатся в каталоге ………….

Задание

1.Выполнить упражнения по факторизации многочленов, нахождению их наибольшего общего делителя(gcd(a(x),b(x))) и по нахождению канонического представления gcd при помощи расширенного алгоритма Евклида.
2.Произвести вычисления в конечных полях GF(q):
сложение, умножение и нахождение обратных элементов.
3.Определить неприводимость заданных полиномов над простым полем и рассчитать число неприводимых полиномов различной степени.
4.Проверить, что многочлен  является произведением всех неприводимых нормированных многочленов степени , которая делит .

Порядок

Для начала работы перейти в каталог, содержащий описание лабораторных работ и убедиться в установке пакета программ “Maxima”.
Прочитать описание лабораторной работы 2.
1.Перейти к пакету “Maxima”.
2.Задавшись не менее, чем двумя произвольными многочленами  с коэффициентами из поля GF(2) и степени не более 20 произвести их факторизацию, используя следующие команды:
f[x]: x^3+ x^2+x*12
modulus:2
factor(f[x])
Проверить правильность расчета на примере многочлена малой степени. Найти неприводимый многочлен третьей степени.
3.Найти gcd не менее чем двух пар произвольно выбранных многочленов a(x),b(x) степени не выше 15 при помощи следующей команды:
modulus:2
gcd(a[x],b[x])
Проверить правильность расчетов на примере пары многочленов малой степени.
4.Для найденных в п.3 двух gcd(a(x),b(x)), найти их канонические представления при помощи расширенного алгоритма Евклида, используя следующую команду:
gcdex(a[x],b[x])
Проверить правильность расчетов для многочленов малой степени.
5.Задавшись неприводимым над полем GF(2) многочленом степени 3, который  был получен с использованием п.2, найти сумму и произведение двух произвольных элементов  поля , при помощи команд:
mod(a[x]+b[x],2)
mod(a[x]*b[x],2)
modulus:2
g[x]:a[x]*b[x]
divide(g[x],f[x])
Примечание: в поле GF(2) противоположный элемент совпадает с исходным.
6.Найти обратные элементы для каждого из  элементов поля, выбранных в п.5 , используя команды из п.4.
7.Рассчитать число неприводимых многочленов степени , используя, следующие команды:
n:..
d:divisors(n); summ:0; q:..;
for di in d do summ:summ+moebius(di)*q^(n/di);
i:1/n*summ;
Выбрать 4 значения  не более 15. Проверить правильность расчетов для
8.Проверить, что многочлен  является произведением всех неприводимых над полем  многочленов, степени которых делят  при помощи следующей команды:
factor(x^(2^n)+x), modulus:2
Для расчетов выбрать 2 произвольных значения .

Отчет

1.Титульный лист.
2.Исходные данные и результаты вычислений по всем восьми пунктам порядка выполнения работы.
3.Выводы о возможности (или нет) быстрого выполнения операций в полях , а так же быстрого нахождения неприводимых многочленов произвольной степени.

Контрольные вопросы

1.Какое число элементов может содержать конечное поле?
2.Чем однозначно задается конечное поле и как в нем выполняются действия над элементами?
3.Что такое примитивный элемент поля? Всегда ли он существует?
4.Как находить неприводимые и примитивные многочлены в конечном поле?
5.Как рассчитать число неприводимых и примитивных многочленов заданной степени над конечным полем?
6.Для всех ли элементов конечного поля существуют обратные элементы ?

Литература

1.В.И.Коржик “Конспект лекций по курсу “Основы криптографии с открытым ключом”,www.sut-ru.ibts
2.В.И.Коржик, B.П.Просихин “Основы криптографии” , Учебное пособие,” Линк”, 2008
3.У.Питерсон, Э.Уэлдон, ”Коды, исправляющие ошибки”, ”Мир”, 1976.


 

А также другие работы, которые могут Вас заинтересовать

78976. КОНЦЕПЦИЯ НАУЧНЫХ РЕВОЛЮЦИЙ Т.КУНА 40 KB
  История науки по Куну: Согласно книге Структура научных революций Т.Куна историю науки можно представить следующей схемой: 1 При переходе к зрелой науке на основе идей одной или нескольких научных школ возникает общепринятая парадигма; 2 одно из главных направлений деятельности нормальной науки – обнаружение и объяснение фактов как фактов подтверждающих парадигму; 3 при таком исследовании часть фактов трактуется как аномалии – факты противоречащие парадигме; 4 в период кризиса доверие к парадигме в известной степени подорвано но...
78978. Особенности становления и основные принципы неклассической науки 43 KB
  Планк квантавая теория Резенфорд планетарная модель атома Ренген ренгеновские лучи Все эти открытия разрушили картину мира. Основные принципы: Установка на невозможность описать мир сам по себе Установлено различие в организации и развитии 3х уровней мира: макро микро мега. Нет качественной однородности в мега микро и макромирах Вероятностный детерменизм Признавалась роль случайностей. Случайность – равноценный фактор необходимости Объект исследования не вещи а процессы Принципиально невозможно найти первокирпичик мира т.
78979. Понятие рациональности, научной рациональности. Виды и типы научной рациональности 48 KB
  Понятие рациональности научной рациональности. Виды и типы научной рациональности. В самой идее рациональности можно увидеть символ современной научно-технической цивилизации со всеми ее особенностями и противоречиями. Ее началом является некоторый тип активно-преобразовательного отношения человека к миру с которым и связывается как правило сама идея рациональности.
78980. Пространство и время в современной и классической картине мира 35 KB
  Пространство и время в современной и классической картине мира. Пространство есть форма координации сосуществующих объектов состояний материи. Пространство и время это всеобщие формы существования координации объектов. Пространство и время в классической картине мира.
78981. Философское значение синергетики 41 KB
  В своей классической работе Синергетика он отмечал что во многих дисциплинах от астрофизики до социологии мы часто наблюдаем как кооперация отдельных частей системы приводит к макроскопическим структурам или функциям. Синергетика в ее нынешнем состоянии фокусирует внимание на таких ситуациях в которых структуры или функции систем переживают драматические изменения на уровне макромасштабов. По мнению ученого существуют одни и те же принципы самоорганизации различных по своей природе систем от электронов до людей а значит речь должна...
78982. Этос науки и императивы, регулирующие поведение ученого 32.5 KB
  Понятие Императив и Этос науки Императив лат. Этос науки набор внутренних социальных норм которых придерживаются ученые в научной деятельности и которые обеспечивают функционирование социального института науки. Нормы этоса науки Попытка кодификации социальных норм науки была предпринята Р.
78983. Научная специальность и основные этапы ее становления 40.5 KB
  С этой характеристикой тесно связана потребность в такого рода вознаграждении которое служило бы достаточным стимулом для профессионалов будучи в то же время подконтрольно не столько посторонним сколько самой профессии. Внутренний мотив – это познавательная потребность – информация заключенная в объекте на который направлено внимание человека. Познавательная потребность характеризуется следующими основными критериями: интенсивное стремление субъекта к знанию и к познавательной деятельности на основании чего избирается его...