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.


 

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

73670. Блоки і поліспасти у ВПМ 259 KB
  Якщо нерухомий блок служить тільки для зміни напряму гнучкого елементу то рухомий блок служить як для виграшу в силі так і швидкості. Гнучкі елементи вживані в ВПМ не є абсолютно гнучкими тілами а володіють певною жорсткістю яка виражається у тому що набігаюча гілка гнучкого елементу не відразу укладається на блоці а збігаюча гілка не відразу випрямляється на що потрібна витрата додаткового зусилля. У реальних умови з урахуванням цих втрат або тут Gгр вага вантажу що розуміється...
73671. Деталі для навівки і звивання гнучких елементів 440.5 KB
  Барабани для багатошарової навівки каната застосовуються у виняткових випадках при вельми великих довжинах навиваного каната коли при одношаровій навівки потрібен надзвичайно великі розміри барабана. У гладких барабанах завжди є бурти. Нижній шар каната при багатошаровій навівки стикається з циліндровою поверхнею барабана по лінії унаслідок чого виникають високі контактні напруги...
73672. Механізми вантажопідйомних машин 338.5 KB
  Залежно від типу вантажопідйомної машини її призначення можуть бути різні комбінації механізмів основним з яких є механізм підйому. Механізми підйому ГПМ Механізми підйому служать для вертикального переміщення вантажів. Залежно від типу приводу розрізняють механізми підйому з ручним і машинним приводом – будівельна лебідка мал.
73673. Механізми пересування 351.5 KB
  У вантажопідйомних машинах загального призначення механізми пересування по конструктивній ознаці розрізняють: а механізми пересування з ручним приводом б механізми пересування з машинним приводом електричний і ДВС. По конструкції опорноходової частини механізми пересування підрозділяються: а на рейкові б на без рейкові. За принципом роботи механізми пересування підрозділяються на дві принципові схеми: а механізми у яких переміщення здійснюється за рахунок сил зчеплення приводних ходових коліс з рейкою або грунтом б механізми у...
73674. Вимоги до антен по параметрах електромагнітної сумісності 370 KB
  Вимоги до антен по параметрах електромагнітної сумісності Розвиток супутникових систем звязку супроводжується зростаючим завантаженням діапазонів радіочастот. Передумови для рішення проблеми ЭМС створюють відомі просторова й частотна вибірковості антен. При аналізі діаграми спрямованості апертурних антен широко застосовуваних у супутниковому...
73675. Розрахунок механізму пересування з тяговим елементом 242 KB
  Ходові колеса кранів і рейки У вантажопідйомних машинах загального призначення залежно від типу машини призначення а також величини навантаження і швидкості пересування ходові колеса виготовляються сталевими і чавунними з циліндровим і конічним ободом. Як рейки у вантажопідйомних машинах застосовується квадратна або смугова сталь а також залізничні рейки
73676. Механізми повороту 471.5 KB
  Конструкція механізмів повороту визначається призначенням і конструкцією вантажопідйомної машини умовами експлуатації діючими навантаженнями і іншими особливостями крана. У вантажопідйомних машинах залежно від конструктивного виконання механізму повороту крана можуть бути дві принципово відмінні схеми приводу механізму повороту. По першій схемі прівод механізму повороту розташовується на неповоротній частині вантажопідйомної машини мал.
73677. Механізми зміни вильоту стріли 249.5 KB
  В цьому випадку приймають середню вантажопідйомність крана з перевантаженнямпо перекидаючому моменту в межах 1520 На практиці зміна вильоту стріли виробляється в двох випадках: Настановна зміна вильоту стріли. Маневрова зміна вильоту стріли. Зміна вильоту стріли виробляється в процесі роботи крана для горизонтального радіального переміщення оброблюваного вантажу.
73678. Стаціонарні поворотні крани 426 KB
  Верхня опора зміцнюється в стіні будівлі або в колоні іноді встановлюється на гнучких розтяжках при повороті крана на 360 градусів. Противага служить для зменшення перекидаючого моменту отже для полегшення опорних елементів крана зменшення ваги і розмірів фундаменту а також колони крана. Залежно від розташування наполегливого підшипника можливі дві схеми навантаження колони крана мал. Якщо ферма крана спирається на верхню шпильку колони в якій встановлений наполегливий підшипник то верхня опора сприймає не тільки горизонтальні...