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.


 

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

23380. Определение коэффициента трения качения методом наклонного маятника 2.35 MB
  Орлова Определение коэффициента трения качения методом наклонного маятника Методические указания к выполнению лабораторной работы № 12 по курсу механики молекулярной физики и термодинамики. Цель работы: экспериментальное изучение основных закономерностей возникающих при трении качения и определение коэффициента трения качения методом наклонного маятника. Сплошь и рядом силы трения являются вредными. Таковы например силы трения возникающие между осью и втулкой а также между другими деталями машины.
23381. Определение коэффициента внутреннего трения жидкости касторового масла по методу Стокса 381 KB
  Нехаенко Определение коэффициента внутреннего трения жидкости по методу Стокса Методические указания к выполнению лабораторной работы № 13 по курсу механики молекулярной физики и термодинамики. Внутреннее трение вязкость это свойство реальных жидкостей оказывать сопротивление перемещению одной части жидкости относительно другой. При перемещении одних слоев реальной жидкости относительно других возникают силы внутреннего трения направленные по касательной к поверхности слоев. и зависит от того насколько быстро меняется скорость...
23382. Определение ускорения свободного падения при помощи физического маятника 664 KB
  Китаева Определение ускорения свободного падения при помощи физического маятника Методические указания к выполнению лабораторной работы № 14 по курсу механики молекулярной физики и термодинамики. Цель работы: определение ускорения свободного падения при помощи физического маятника. Запишем основное уравнение динамики вращательного движения относительно неподвижной оси : 6 где момент инерции физического маятника...
23383. Определение коэффициента динамической вязкости воздуха 535 KB
  Нехаенко Определение коэффициента динамической вязкости воздуха Методические указания к выполнению лабораторной работы № 15 по курсу механики молекулярной физики и термодинамики. Цель работы заключается в определении коэффициента динамической вязкости воздуха методом истечения воздуха через капилляр. Сила внутреннего трения между двумя слоями газа подчиняется закону Ньютона: 1 где коэффициент динамической вязкости газа...
23384. Определение погрешностей при измерении периода колебаний математического маятника 1.3 MB
  Цель работы изучить характер распределения погрешностей прямых измерений и оценить их величину при определении периода колебания математического маятника. В задачу измерений кроме определения измеряемой величины входит оценка допущенных погрешностей. Систематические погрешности обусловлены ограниченной точностью измерительных приборов неточностью метода измерений неточностью изготовления объекта измерений. Оценка случайных погрешностей прямых измерений.
23385. Определение ускорения свободного падения с помощью прибора (машины) Атвуда 653 KB
  Прибор Атвуда предназначен для изучения прямолинейного равномерного и равномерноускоренного движения а в частности для определения ускорения свободного падения тел. 1 закон Ньютона: любое тело сохраняет состояние покоя или равномерного и прямолинейного движения до тех пор пока воздействие со стороны других тел не заставит его изменить это состоянии то есть: если 1 где равнодействующая всех сил действующих на тело. Запишем II закон Ньютона в виде:...
23386. Определение коэффициента поверхностного натяжения жидкости 276 KB
  Нехаенко Определение коэффициента поверхностного натяжения жидкости Методические указания к выполнению лабораторной работы № 3 по курсу молекулярной физики. Каждая молекула жидкости в течение некоторого времени колеблется около определённого положения равновесия после чего скачком переходит в новое положение отстоящее от исходного на расстоянии порядка межатомного. На молекулу жидкости со стороны окружающих её молекул действуют силы взаимного притяжения которые с расстоянием быстро убывают. Выделим внутри жидкости какуюлибо молекулу А...
23387. Экспериментальное определение момента инерции маятника Максвелла 433 KB
  Определение момента инерции маятника Максвелла Методические указания к выполнению лабораторной работы № 4 по курсу механики молекулярной физики и термодинамики. Целью данной работы является экспериментальное определение момента инерции маятника Максвелла. Момент инерции тела относительно заданной оси и угловая скорость позволяют вычислить кинетическую энергию вращательного движения этого тела: 5 Экспериментальное...
23388. Определение логарифмического декремента затухания и коэффициента затухания колебательной системы 246 KB
  Во всех реальных колебательных системах энергия колебаний расходуется на работу против сил сопротивления и сил внутреннего трения что является причиной затухания свободных колебаний. Тогда основное уравнение динамики поступательного движения колебательной системы в проекции на ось ОХ имеет вид: или 1 1 дифференциальное уравнение свободных затухающих колебаний где где коэффициент затухания. Решением дифференциального...