Криптография. Неприводимый многочлен n-й степени над полем GF(p). Проверка его примитивности

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение высшего профессионального образования

Научно-Исследовательский Университет «Южно-Уральский Государственный Университет»

Факультет «Приборостроительный»

Кафедра «Безопасность Информационных Систем»

Курсовая работа

По дисциплине «Криптография»

Подготовил:

Студент:

Группа: ПС-308

Проверил:

Оценка:____________

Челябинск 2012

Задание 1

p=5, n=3, найти неприводимый многочлен n-й степени над полем GF(p) и проверить его примитивность.

1.1  В поле GF(pⁿ) выписать все элементы.

GF(pⁿ) = {0;1;2;3;4; α ; α +1; α +2; α +3; α +4; 2α ;2α +1; 2α+2; 2α+3; 2α+4; 3α+1; 3α+2; 3α+3; 3α+4; 4α; 4α+1; 4α+2; 4α+3; 4α+4; α² ; α² +1; α² +2; α² +3; α² +4; α² + α ; α² + α+1; α² + α+2; α² + α+3; α² + α+4; α² + 2α; α² + 2α+1; α² + 2α+2; α² + 2α+3; α² + 2α+4; α² + 3α; α² + 3α+1; α² + 3α+2; α² + 3α+3; α² + 3α+4; α² + 4α; α² + 4α+1; α² + 4α+2; α² + 4α+3; α² + 4α+4; 2α²; 2α²+1; 2α²+2; 2α²+3; 2α²+4; 2α²+ α; 2α²+ α+1; 2α²+ α+2; 2α²+ α+3; 2α²+ α+4; 2α²+ 2α; 2α²+ 2α+1; 2α²+ 2α+2; 2α²+ 2α+3; 2α²+ 2α+4; 2α²+ 3α; 2α²+ 3α+1; 2α²+ 3α+2; 2α²+ 3α+3; 2α²+ 3α+4; 2α²+ 4α; 2α²+ 4α+1; 2α²+ 4α+2; 2α²+ 4α+3; 2α²+ 4α+4; 3α²; 3α²+ 1; 3α²+ 2; 3α²+ 3; 3α²+ 4; 3α²+ α; 3α²+ α+1; 3α²+ α+2; 3α²+ α+3; 3α²+ α+4; 3α²+ 2α; 3α²+ 2α+1; 3α²+ 2α+2; 3α²+ 2α+3; 3α²+ 2α+4; 3α²+ 3α; 3α²+ 3α+1; 3α²+ 3α+2; 3α²+ 3α+3; 3α²+ 3α+4; 3α²+ 4α; 3α²+ 4α+1; 3α²+ 4α+2; 3α²+ 4α+3; 3α²+ 4α+4; 4α²; 4α²+1; 4α²+2; 4α²+3; 4α²+4; 4α²+ α; 4α²+ α+1; 4α²+ α+2; 4α²+ α+3; 4α²+ α+4; 4α²+ 2α; 4α²+ 2α+1; 4α²+ 2α+2; 4α²+ 2α+3; 4α²+ 2α+4; 4α²+ 3α; 4α²+ 3α+1; 4α²+ 3α+2; 4α²+ 3α+3; 4α²+ 3α+4; 4α²+ 4α; 4α²+ 4α+1; 4α²+ 4α+2; 4α²+ 4α+3; 4α²+ 4α+4}

1.2. В поле GF(pⁿ) найти примитивный элемент.

Построение поля ведем по элементу α³+3α +2.

Примитивным будет элемент 2α+3.

1.3. Представить все ненулевые элементы поля GF(pⁿ) в виде степеней примитивного элемента.

(2α+3)¹ = 2α+3

(2α+3)² = 4α² + 2α + 4

(2α+3)³ = α² + 1

(2α+3)⁴ = 3α²+α +4

(2α+3)⁵ = α² +3α

(2α+3)⁶ = 4α² + 3α + 1

(2α+3)⁷ = 3α² + 2α + 2

(2α+3)⁸ = 3α² + 2α + 4

(2α+3)⁹ = 3α² + α

(2α+3)¹⁰ = α² + 3

(2α+3)¹¹ = 3α²

(2α+3)¹² = 4α² + 2α + 3

(2α+3)¹³ = α² + 3α + 3

(2α+3)¹⁴ = 4α² + 4α

(2α+3)¹⁵ = 3α + 4

(2α+3)¹⁶ = α² + 2α + 2

(2α+3)¹⁷ = 2α² + 4α + 2

(2α+3)¹⁸ = 4α² + 4α + 3

(2α+3)¹⁹ = 4α + 3

(2α+3)²⁰ = 3α² + 3α + 4

(2α+3)²¹ = 4α

(2α+3)²² = 3α² + 2α

(2α+3)²³ = 3α² + 3α + 3

(2α+3)²⁴ = 2α + 2

(2α+3)²⁵ = 4α² + 1

(2α+3)²⁶ = 2α² + 3α + 2

(2α+3)²⁷ = 2α² + α + 3

(2α+3)²⁸ = 3α² + 2α + 1

(2α+3)²⁹ = 3α² + 1

(2α+3)³⁰ = 4α² + 4α + 1

(2α+3)³¹ = 2

(2α+3)³² = 4α + 1

(2α+3)³³ = 3α² + 4α + 3

(2α+3)³⁴ = 2α² + 2

(2α+3)³⁵ = α² + 2α + 3

(2α+3)³⁶ = 2α² + α

(2α+3)³⁷ = 3α² + α + 2

(2α+3)³⁸ = α² + 4α + 4

(2α+3)³⁹ = α² + 4α + 3

(2α+3)⁴⁰ = α² + 2α

(2α+3)⁴¹ = 2α² + 1

(2α+3)⁴² = α²

(2α+3)⁴³ = 3α² + 4α + 1

(2α+3)⁴⁴ = 2α² + α + 1

(2α+3)⁴⁵ = 3α² + 3α

(2α+3)⁴⁶ = α + 3

(2α+3)⁴⁷ = 2α² + 4α + 4

(2α+3)⁴⁸ = 4α² + 3α + 4

(2α+3)⁴⁹ = 3α² + 3α + 1

(2α+3)⁵⁰ = 3α + 1

(2α+3)⁵¹ = α² + α + 3

(2α+3)⁵² = 3α

(2α+3)⁵³ = α² + 4α

(2α+3)⁵⁴ = α² + α + 1

(2α+3)⁵⁵ = 4α + 4

(2α+3)⁵⁶ = 3α² + 2

(2α+3)⁵⁷ = 4α² + α + 4

(2α+3)⁵⁸ = 4α² + 2α + 1

(2α+3)⁵⁹ = α² + 4α + 2

(2α+3)⁶⁰ = α² + 2

(2α+3)⁶¹ = 3α² + 3α + 2

(2α+3)⁶² = 4

(2α+3)⁶³ = 3α + 2

(2α+3)⁶⁴ = α² + 3α + 1

(2α+3)⁶⁵ = 4α² + 4

(2α+3)⁶⁶ = 2α² + 4α + 1

(2α+3)⁶⁷ = 4α² + 2α

(2α+3)⁶⁸ = α² + 2α + 4

(2α+3)⁶⁹ = 2α² + 3α + 3

(2α+3)⁷⁰ = 2α² + 3α + 1

(2α+3)⁷¹ = 2α² + 4α

(2α+3)⁷² = 4α² + 2

(2α+3)⁷³ = 2α²

(2α+3)⁷⁴ = α² + 3α + 2

(2α+3)⁷⁵ = 4α² + 2α + 2

(2α+3)⁷⁶ = α² + α

(2α+3)⁷⁷ = 2α + 1

(2α+3)⁷⁸ = 4α² + 3α + 3

(2α+3)⁷⁹ = 3α² + α + 3

(2α+3)⁸⁰ = α² + α + 2

(2α+3)⁸¹ = α + 2

(2α+3)⁸² = 2α² + 2α + 1

(2α+3)⁸³ = α

(2α+3)⁸⁴ = 2α² + 3α

(2α+3)⁸⁵ = 2α² + 2α + 2

(2α+3)⁸⁶ = 3α + 3

(2α+3)⁸⁷ = α² + 4

(2α+3)⁸⁸ = 3α² + 2α + 3

(2α+3)⁸⁹ = 3α² + 4α + 2

(2α+3)⁹⁰ = 2α² + 3α + 4

(2α+3)⁹¹ = 2α² + 4

(2α+3)⁹² = α² + α + 4

(2α+3)⁹³ = 3

(2α+3)⁹⁴ = α + 4

(2α+3)⁹⁵ = 2α² + α + 2

(2α+3)⁹⁶ = 3α² + 3

(2α+3)⁹⁷ = 4α² + 3α + 2

(2α+3)⁹⁸ = 3α² + 4α

(2α+3)⁹⁹ = 2α² + 4α + 3