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.


 

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

59299. Свято здоровя в літньому таборі 49.5 KB
  Зараз ми спробуємо поставити виставу €œПригоди Катрусі в країні Невмивайній Катруся і Бруднуля разом ти хто Бруднуля: Я Бруднуля Бруднулькун Знаменитий неуважний З вулиці Вантажної. Тут гарно живеться Катруся: А я сама не знаю як сюди потрапила.
59300. Гра-подорож у країну чистоти у порядку 31.5 KB
  Діти не чистять своє взуття не слідкують за одягом не вміють користуватися носовою хустиночкою. Хочу я напитись чаю Але що це Сам не знаю Самовар мій повний вщерть Утікає напереберть Що зробилось Діти чому в бруднулі всі речі повтікали...
59301. Котилася торба з великого горба 31 KB
  Хід гриподорожі Добрий день любідрузі Яке чудове привітання Добрий день це означає що над нами мирне небо що у нас хороше на серці. Добрий день це означає що всі ми бажаємо один одному добра. Треба дружно привітатись Добрий день Дружно голосно сказати: Добрий день...
59302. КОНКУРС-ЗМАГАННЯ «КОЗАЦЬКІ ЗАБАВИ» 62.5 KB
  Для боротьби ми не збирали ані рушниць ані гармат здоровя повен міх набрали вистачить його для всіх команд. Хлопчик 1 команда: Наша невелика команда і поки молодий у неї вік а Тараса ми вибрали за отамана бо він здоровий чоловік.
59303. Мама, тато і я – спортивна сімя 348.5 KB
  Члени кожної команди женуть мяч ногою від кубика до кубика, обходячи кожний то справа, то зліва. Спочатку вони рухаються в один бік, а потім в інший. Передавати мяч наступним гравцям потрібно також ногою.
59304. CЦЕНАРІЙ КВК ПО ХІМІЇ 67 KB
  Ведучий 1: Доброго дня шановні друзі Сьогодні на острові Хімляндії в Клубі веселих та кмітливих відбудеться зустріч двох команд хіміків і екологів. Ведучий 2. Ведучий 1: То ж запрошуємо на сцену для змагання дві команди.
59305. Казкова вікторина 135.5 KB
  Діти: Допоможемо Книгадівчина: Які ви молодці а то мені не впоратись самій. Дівчина –книга сідає на стілець. І під загадкову музику і мікрофон хтось каже: Книга відкривається казка починається Під веселу музику вбігає колобок і співає: Колобок: Я по засіку метений...
59306. Виховна година, присвячена Дню Збройних Сил України 45 KB
  Політичний, економічний, духовний розвиток України можливий за умови гарантування її державного суверенітету, політичної незалежності, збереження територіальної цілісності та недоторканості кордонів.
59307. ТУРНІР МАЙБУТНІХ СІМЕЙ. ВАЛЕОЛОГІЧНИЙ ВЕЧІР 37 KB
  Одружитися зовсім не важко важко бути одруженим. Так Тисячу разів повторюють це признання перед усім білим світом. Це вільна рівноправна спілка жінки та чоловіка укладена з дотриманням порядку та умов установлених законом яка утворює сім’ю і породжує взаємні особисті...