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.


 

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

9508. Трагедия Фауст 72 KB
  Трагедия Фауст Из немецкой легенды о чернокнижнике 16 век. Кристофер Марло - пьеса. Вершина творчества Гете дело всей жизни (писал 60 лет) Замысел - штюрмерский период (1773) Набросок (найден через 100 лет, Пра-Фауст) Герой...
9509. Иоганн Вольфганг Гете 1749 - 1832 Johann Wolfgang Goethe 31.13 KB
  5 Иоганн Вольфганг Гете 1749 - 1832 Johann Wolfgang Goethe Общечеловеческий гений (Гомер, Шекспир) Разносторонний: красавец, долгожитель, светский человек, государственный деятель, ученый-натуралист, поэт, драматург, прозаик + актер, художник Совре...
9510. Дени Дидро 1713 – 1784 50.29 KB
  Дени Дидро 1713 – 1784 Родился в семье ремесленника. Духовная карьера – не стал. С 20 лет – интеллигент, бедняк. Разносторонние таланты, в том числе, организаторский. (Энциклопедия) Дидро дважды попадал в тюрьму (в 1749 и в 1...
9511. Лирика Иоганна Вольфганга Гёте 81.96 KB
  36 Лирика Иоганна Вольфганга Гёте Когда мы говорим о творчестве Гете, мы непременно подчеркиваем замечательный универсализм художника, проявившийся в создании им прекрасных образцов драмы, эпической поэмы, романа. Но наиболее велик, непререкаемо пре...
9512. Поэмы Оссиана Джеймса Макферсона 240.86 KB
  Поэмы Оссиана Джеймса Макферсона Осенью 1759 г. в курортный городок на юге Шотландии Моффат прибыл Томас Грэм (Graham), сын шотландского помещика, который в дальнейшем ста...
9513. Поэма Орлеанская девственница 36.11 KB
  1735 опубл. 1755 творчески перерабатывается сам жанр комической эпопеи, расширяется сфера комического, изменяется его социально-критическая функция в соответствии с просветительскими идеологическими задачами ПАРОД...
9514. Жан-Жак Руссо (1712 – 1778) 48.5 KB
  Жан-Жак Руссо (1712 – 1778) Швейцарец - фр гений Сложен, противоречив (история жизни – в Исповеди, факты верны, а освещение) Из демократических низов (как и многие просветители 2-го этапа): сын часовщика - сирота, бродяга, самообраз...
9515. Лоренс Стерн (Laurence Sterne, 1713 - 1768) 30.22 KB
  Лоренс Стерн (Laurence Sterne, 1713 - 1768) родился на юге Ирландии в семье пехотного офицера. В детстве вместе с семьей ему приходилось постоянно переезжать с места на место, скитаясь по казармам. Когда будущему писателю было 18 лет, умер отец. Бла...
9516. История зарубежной литературы XVIII века 572.35 KB
  История зарубежной литературы XVIII века Глава 1 История зарубежной литературы XVIII века Учебник для филологических специальностей вузов Под редакцией Л. В. Сидорченко Учебник рассматривает важнейшие закономерности развития литературы эпохи Просвещ...