12742

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

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

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

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

Русский

2013-05-03

53 KB

24 чел.

Лабораторная работа 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.


 

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

32043. Управління маркетинговою діяльністю підприємства (на прикладі ТОВ «Місто - Д») 579.68 KB
  Пропонуємо нову методику маркетингового аналізу та аудиту підприємства та застосування маркетингу, яка апробована при аналізі підприємства ТОВ «Місто - Д», провести модернізацію організаційної структури підприємства, провести вихід підприємства на ринки сусідніх областей, ввести ефективну систему маркетингового контролю. Це збільшить ефективність і швидкість роботи, збільшить прибутки, оптимізує загрузку на всіх працівників маркетингової служби, розширить діяльність підприємства.
32044. Формування маркетингової стратегії підприємства 889.5 KB
  Тема дипломної роботи: Формування маркетингової стратегії підприємства Затверджена наказом по університету № 127дс від 25 грудня 2009 р. Цільова установка та загальний напрямок дипломної роботи для робіт технічного профілю також вихідні дані: проаналізувати особливості формування маркетингової стратегії організації та запропонувати заходи з її вдосконалення. Теоретичні основи формування маркетингової стратегії 1. Етапи розробки маркетингової стратегії Розділ 2.
32045. Соотношение корня слова и основы слова 22 KB
  Соотношение корня слова и основы слова Все морфемы можно разделить на два больших класса: корни и аффиксы ffixus от лат прикрепленный. Основа может состоять из одного корня например дом из корня со словообразовательным суффиксом одним или несколькими например домик красный ый окончание красненький ий окончание; из корня и приставки например пригород ; из корня приставки и суффикса например сделать ть суффикс инфинитива не входящий в основу выражает роль которую играет глагол в предложении.
32046. Организация Web-доступа в среде zLinux на сервере z9 BC 657 KB
  Целью работы является обеспечить webдоступ на сервер z9 BC используя программное обеспечение установленное на IBM z9 BC а именно HTTP сервер pche. Webсервер pche будет предоставлять доступ к ресурсам сервера пользователям подключенным к внутренней сети. Webсервер pche [7.1 Описание webсервера pche [7.
32047. Подготовка и защита выпускных квалификационных работ 328.5 KB
  Состав дипломной работы и требования к её выполнению. Выполнение исследовательских задач и написание основных разделов дипломной работы.40 Изложение и оформление дипломной работы.42 Оформление дипломной работы.
32048. Возникновение иудаизма, основные этапы его развития 37 KB
  Дальнейшая история Завета делится на 7 периодов которые отражают стадии религиознообщественного становления народа древнего Израиля: Эпоха патриархов от Авраама до Моисея которая заканчивается египетским пленом. Эпоха Моисея и Иисуса Навина в которую сбываются обетования Бога Аврааму. Эпоха судей. Эпоха ранней монархии при Сауле Давиде Соломоне и частично Ровоаме.
32049. Новый Завет 137 KB
  Новый Завет из 27 книг которые можно поделить на следующие разделы: евангелия основная часть Нового Завета тексты написанные учениками Иисуса Христа. историческая книга книга Деяния святых апостолов приписываемая евангелисту Луке: исторический рассказ о подвижничестве последователей Христа распространявших христианскую веру и о росте и усилении древней церкви. пророческая книга Откровение Апокалипсис откровение Святого апостола Иоанна Богослова полученное от Бога: антихрист второе пришествие Христа конец света...
32050. Коран и коранистика 49 KB
  Он приказал разрушить капища места жертвоприношений языческих богов бросить в Днепр их статуи и построить христианские церкви. Строились церкви: Десятинная церковь в Киеве Пресвятой Богородицы в Полоцке в 1037 г. церковные иерархии и князья начали борьбу за независимость русской церкви от Византии. Фактически через Синод император контролировал и жизнь Церкви.