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.


 

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

9798. Принятие решений в условиях риска, Эффективность выпуска новых видов продукции 66 KB
  Принятие решений в условиях риска. Элементы неопределенности, присущие функционированию и развитию многих экономических процессов, обуславливают появление ситуаций, не имеющих однозначного исхода (решения). Это обстоятельство усложняет процесс...
9799. Принятие решений в условиях неопределенности 72 KB
  Принятие решений в условиях неопределенности. При принятии решений в условиях неопределенности, когда вероятности возможных вариантов обстановки неизвестны, может быть использованы ряд критериев, выбор каждого из которых, наряду с характером решаем...
9800. Проблемы сравнительной оценки вариантов решений с учетом риска 273.5 KB
  Проблемы сравнительной оценки вариантов решений с учетом риска. Как отмечалось ранее, на методы принятия решений в условиях риска существенное влияние оказывает многообразие критериев и показателей, посредством которых оценивается уровень риска. В р...
9801. Учет риска при инвестировании капитальных вложений 86 KB
  Учет риска при инвестировании капитальных вложений. В условиях рыночной экономики, особенно в период ее становления, инвестирование развития сопряжено с риском неполучения ожидаемых результатов в установленные (желаемые) сроки. В связи с этим возник...
9802. Система критериев принятия рискового решения 133.5 KB
  Система критериев принятия рискового решения. Принятие рискового решения на ведение конкретной операции (сделки) в предпринимательской деятельности является заключительной процедурой на стадии анализа риска в технологии риск-менеджмента. Объективная...
9803. Критерии принятия решения в условиях определенности 77.5 KB
  Критерии принятия решения в условиях определенности. В условиях определенности неблагоприятные последствия рисковой ситуации однозначно и адекватно оцениваются значениями показателей риска. В данном случае используются детерминированные модели и мет...
9804. Критерии принятия решения в условиях стохастической неопределенности 32 KB
  Критерии принятия решения в условиях стохастической неопределенности. В условиях стохастической (частичной) неопределенности (риска) исходы предполагаемого результата деятельности имеют вероятностный характер и взаимосвязи между критериями и показат...
9805. Критерии принятия решения в условиях нестохастической неопределенности 24 KB
  Критерии принятия решения в условиях нестохастической неопределенности. В условиях неопределенности нестохастической природы значения ожидаемого результата не могут быть описаны в рамках вероятностных моделей. Между критериями и оценками риска сущес...
9806. Эвристические правила принятия рискового решения 113 KB
  Эвристические правила принятия рискового решения. В случаях когда риск рассчитать невозможно, принятие рисковых решений основывается на эвристике, представляющей собой совокупность логических приемов и методических правил отыскания истины. Рис...