12742

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

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

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

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

Русский

2013-05-03

53 KB

23 чел.

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


 

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

22220. СОЕДИНЕНИЯ ДЕРЕВЯННЫХ ЭЛЕМЕНТОВ 735.5 KB
  Соединения являются наиболее ответственными деталями деревянных конструкций. Разрушение деревянных конструкций начинается в большинстве случаев в соединениях. Более сложно решаются соединения изгибаемых элементов в которых для передачи усилий требуются рабочие связи.
22221. Дощатые и клеефанерные настилы покрытий 2.93 MB
  Клеефанерные панели выполняют функции настила прогонов водо и пароизоляции. По форме поперечного сечения клеефанерные панели могут быть следующих видов: 1 коробчатые; 2 ребристые обшивкой вверх; 3 ребристые обшивкой вниз Коробчатую клеефанерную панель применяют в утепленных покрытиях с рулонной кровлей и гладким потолком Она имеет двухсторонние обшивки образующие вместе с ребрами ряд полостей в которые по слою пароизоляции укладывают утеплитель. Наиболее распространенными являются коробчатые клеефанерные панели которые используют не...
22222. Балки и прогоны цельного сечения. Составные балки на податливых связях 3.02 MB
  Балки и прогоны цельного сечения Основное функциональное назначение балок и прогонов в том что они служат несущими конструкциями покрытий. Балки и прогоны цельного сечения выполняются из досок на ребро брусьев и бревен чаще окантованных с двух сторон. Ввиду ограниченности размеров сечений и длины лесоматериалов такие балки применяют при пролетах до 6 м.
22223. Государство и право в период нэпа 22.6 KB
  Еще в годы гражданской войны Зиновьев Каменев Бухарин говорили о диктатуре уже не пролетариата а о диктатуре партии. Троцкий диктатура партии при содействии красной армии национализация средств производства монополия внешней торговли. С одной стороны речь идет о диктатуре партии. Большинство соратников Ленина придерживались позиции диктатуры партии.
22224. Право в периода новой экономической политики 21.33 KB
  Как поднять доходы налоги. Налоги. Мы говорили что государство может существовать без каких то отношений но сказать то мы можем не собирать налоги невозможно Первым декретов в 1918 г. Эти налоги падали на в прошлом господствующие классы.
22225. Гражданское право. Семейное право 20.13 KB
  Государство ограничивает субъекта правоотношений какими-то рамками. С самого начала был поставлен первый принцип что у нас не должно быть ничего частного государство может вмешаться в любые имущественные отношения. Первый советский гражданский кодекс первый момент государство может вмешаться в любые правоотношения. Государство вводило нэп чтобы поднять экономику.
22226. Советская государственная система в 30х годах ХХ столетия 21.98 KB
  МИЛИЦИЯ УЖЕ ОФИЦИАЛЬНО ВХОДИТ в состав угпу до этого было секретное постановление. Постановление ЦИК СССР. 17 ноября снк СССР принимает постановление где констатируется что при упрошенном ведение дела в 1937 1938г. Этим постановление осуждалась практика массовых арестов.
22227. Государство диктатуры пролетариата 22.61 KB
  советские нпа б. дооктябрьские нпа в. Нпа советского государства основной источник Нормы дооктябрьского права Правосознание Именно нпа советского госва будет постоянно расширяться. Советы всех уровней принимали нпа.