Главная | Обратная связь

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

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

 

Подготовил:

Студент: Суворов Н.А.

Группа: ПС-308

 

Проверил:

*******

Оценка:____________

 

Челябинск 2012

Задание 1

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

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

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

 

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

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

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

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

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

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

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

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

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

(α² + 2)⁶ = 2α² + 5α + 4

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

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

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

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

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

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

(α² + 2)¹³ = 5α²+4

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

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

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

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

(α² + 2)¹⁸ = 6α²+5α +5

(α² + 2)¹⁹ = 4α²+6α + 5

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

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

(α² + 2)²² = 5α²+α +5

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

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

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

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

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

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

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

(α² + 2)³⁰ = 5α²+5α

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

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

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

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

(α² + 2)³⁵ = 6α²+2α+1

(α² + 2)³⁶ = 3α

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

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

(α² + 2)³⁹ = 2α²+6α

(α² + 2)⁴⁰ = 2α²+4α+1

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

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

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

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

(α² + 2)⁴⁵ = 6α²+5α+6

(α² + 2)⁴⁶ = 5α²+6α

(α² + 2)⁴⁷ = 5α²+α+1

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

(α² + 2)⁴⁹ = 4α+6

(α² + 2)⁵⁰ = 6α²+4α+1

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

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

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

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

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

(α² + 2)⁵⁶ = 6α²+6α+1

(α² + 2)⁵⁷ = 3

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

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

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

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

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

(α² + 2)⁶³ = 6α²+α+5

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

(α² + 2)⁶⁵ = 6α²+5α+2

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

(α² + 2)⁶⁷ = 5α+6

(α² + 2)⁶⁸ = 6α²+5α

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

(α² + 2)⁷⁰ = α²+5

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

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

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

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

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

(α² + 2)⁷⁶ = 5α²+4α+1

(α² + 2)⁷⁷ = 6α²+6α+5

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

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

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

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

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

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

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

(α² + 2)⁸⁵ = 5α²+4α

(α² + 2)⁸⁶ = 5α²+6α+3

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

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

(α² + 2)⁸⁹ = 6α+5

(α² + 2)⁹⁰ = 5α²+6α+4

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

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

(α² + 2)⁹³ = 2α

(α² + 2)⁹⁴ = 2α+5

(α² + 2)⁹⁵ = 5α²+2α+1

(α² + 2)⁹⁶ = 6α²+4α

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

(α² + 2)⁹⁸ = 2α²+6α+1

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

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

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

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

(α² + 2)¹⁰³ = α²+4α

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

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

(α² + 2)¹⁰⁶ = 5α+4

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

(α² + 2)¹⁰⁸ = α+1

(α² + 2)¹⁰⁹ = α²+α+1

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

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

(α² + 2)¹¹² = 5α²+2α+6

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

(α² + 2)¹¹⁴ = 2

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

(α² + 2)¹¹⁶ = 6α²+5α+1

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

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

(α² + 2)¹¹⁹ = 6α²+2α+5

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

(α² + 2)¹²¹ = 5α²+6α+6

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

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

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

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

(α² + 2)¹²⁶ = 4α²+4α+6

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

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

(α² + 2)¹²⁹ = 6α²

(α² + 2)¹³⁰ = 6α²+α

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

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

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

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

(α² + 2)¹³⁵ = 5α²+5

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

(α² + 2)¹³⁷ = 6α²+6α+4

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

(α² + 2)¹³⁹ = 5α²+4α+4

(α² + 2)¹⁴⁰ = 2α²+6α+4

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

(α² + 2)¹⁴² = α²+5α

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

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

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

(α² + 2)¹⁴⁶ = 4α+1

(α² + 2)¹⁴⁷ = α²+4α+5

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

(α² + 2)¹⁴⁹ = 5α²+4α+2

(α² + 2)¹⁵⁰ = 6α

(α² + 2)¹⁵¹ = 6α+1

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

(α² + 2)¹⁵³ = 4α²+5α

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

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

(α² + 2)¹⁵⁶ = 2α²+5α+2

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

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

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

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

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

(α² + 2)¹⁶² = 5α²+6α+2

(α² + 2)¹⁶³ = α+5

(α² + 2)¹⁶⁴ = 5α²+α+2

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

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

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

(α² + 2)¹⁶⁸ = 2α²+α+6

(α² + 2)¹⁶⁹ = α²+6α+4

(α² + 2)¹⁷⁰ = 5α²+5α+2

(α² + 2)¹⁷¹ = 6

(α² + 2)¹⁷² = 6α²+5

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

(α² + 2)¹⁷⁴ = 4α+5

(α² + 2)¹⁷⁵ = 5α²+4α+6

(α² + 2)¹⁷⁶ = 4α²+6α+1

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

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

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

(α² + 2)¹⁸⁰ = 2α²+5α+5

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

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

(α² + 2)¹⁸³ = 5α²+5α+4

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

(α² + 2)¹⁸⁵ = 5α²+5α+6

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

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

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

(α² + 2)¹⁸⁹ = α²+2α+2

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

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

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

(α² + 2)¹⁹³ = 2α²+6α+2

(α² + 2)¹⁹⁴ = 4α²+4α+5

(α² + 2)¹⁹⁵ = 2α²+6

(α² + 2)¹⁹⁶ = α²+5α+5

(α² + 2)¹⁹⁷ = 6α²+4α+5

(α² + 2)¹⁹⁸ = 4α²+5α+6

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

(α² + 2)²⁰⁰ = 3α²+5α+6

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

(α² + 2)²⁰² = 2α²+5

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

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

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

(α² + 2)²⁰⁶ = α²+5α+6

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

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

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

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

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

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

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

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

(α² + 2)²¹⁵ = 2α²+4α+6

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

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

(α² + 2)²¹⁸ = 2α²+6α+6

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

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

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

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

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

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

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

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

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

(α² + 2)²²⁸ = 4

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

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

(α² + 2)²³¹ = 5α+1

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

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

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

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

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

(α² + 2)²³⁷ = 6α²+α+1

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

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

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

(α² + 2)²⁴¹ = 6α²+2

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

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

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

(α² + 2)²⁴⁵ = 5α²+4α+5

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

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

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

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

(α² + 2)²⁵⁰ = 6α²+4α+6

(α² + 2)²⁵¹ = 5α²+5α+1

(α² + 2)²⁵² = 6α²+4

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

(α² + 2)²⁵⁴ = 4α²+5α+1

(α² + 2)²⁵⁵ = 5α²+α+4

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

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

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

(α² + 2)²⁵⁹ = 6α²+1

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

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

(α² + 2)²⁶² = 5α²+6α+5

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

(α² + 2)²⁶⁴ = 5α

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

(α² + 2)²⁶⁶ = 2α²+5α+6

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

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

(α² + 2)²⁶⁹ = 5α²+α+6

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

(α² + 2)²⁷¹ = α²+6α+5

(α² + 2)²⁷² = 6α²+5α+4

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

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

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

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

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

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

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

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

(α² + 2)²⁸¹ = 5α²+6

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

(α² + 2)²⁸³ = 2α²+5α+1

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

(α² + 2)²⁸⁵ = 5

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

(α² + 2)²⁸⁷ = α²+2α+6

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

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

(α² + 2)²⁹⁰ = α²+5α+2

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

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

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

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

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

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

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

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

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

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

(α² + 2)³⁰¹ = α²+6α

(α² + 2)³⁰² = α²+5α+1

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

(α² + 2)³⁰⁴ = 6α²+2α+4

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

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

(α² + 2)³⁰⁷ = 4α²+5α+4

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

(α² + 2)³⁰⁹ = 4α²+5

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

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

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

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

(α² + 2)³¹⁴ = 6α²+3α+5

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

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

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

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

(α² + 2)³¹⁹ = α²+4α+1

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

(α² + 2)³²¹ = α

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

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

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

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

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

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

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

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

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

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

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

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

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

(α² + 2)³³⁵ = 2α²+6α+5

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

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

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

(α² + 2)³³⁹ = 5α²+6α+1

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

(α² + 2)³⁴¹ = 2α²+2α+5

(α² + 2)³⁴² = 1

 

 

1.4. Составить таблицу логарифма Якоби.

m	(m)
m	(m)
	-

 

 

 

1.5. В поле GF(pⁿ) решить систему линейных уравнений

Учитывая, что:

а – количество букв в фамилии (Суворов) = 7 (mod 7) = 0

b – количество букв в имени (Никита) = 6

с – количество букв в отчестве (Андреевич) = 9 (mod 7) = 2

Система уравнений приобретает вид:

Решение:

1) x(α + 1) = 2

x = 2(α + 1)^-1 = 2(α²+6α+2) = 2α² + 5α + 4

2) 2x + 3z = 6 + α

z = (6 + α + 5x) * 3^-1 = (6 + α + 5(2α² + 5α + 4)) * 5 = (6 + α + 3α² + 4α + 6) *5 = = (3α² + 5α + 5) * 5 = α² + 4α + 4

3) x + 2y + z = 2

y = (2 + 6x + 6z) * 2^-1 = (2 + 6(2α² + 5α + 4) + 6(α² + 4α + 4)) * 4 = (2 + 5α² + 2α + 3 + + 6α² + 3α +3) * 4 = (4α² + 5α + 1) * 4 = 2α² + 6α + 4

Ответ: (2α² + 5α + 4, 2α² + 6α + 4, α² + 4α + 4)

 

1.6. В поле GF(pⁿ) найти элемент обратный по умножению к α + c (mod p) при помощи примитивного элемента и перепроверить по методу Евклида.

α + с = α + 2

(α + 2)^-1 = 4α² + 6α + 6

Проверка алгоритмом Евклида:

f(α) = α³ + α + 1

g(α) = α + 2

f(α) = (α²+5α+5) * g(α) + 5

g(α) = 3α * 5 + 2

5 = 2 * 2 + 1

1 = 5 - 2 * 2

2 = g(α) - 3α * 5

5 = f(α) - (α²+5α+5) * g(α)

1 = 5 - 2 * 2 = 5 - 2 * (g(α) - 3α * 5) = (6α+1) * 5 + 5 * g(α) = (6α+1) * (f(α) - (α²+5α+5) * * g(α)) + 5 * g(α) = (6α+1) * f(α) + (α³+5α²+5α+6α²+2α+2+5) * g(α) = 0 + (4α²+6α+6) * * g(α) = (g(α))^-1 * g(α)

(g(α))^-1 = 4α²+6α+6

 

1.7. В поле GF(pⁿ), используя примитивный элемент и логарифм Якоби, решить систему уравнений

При а = 7, b = 6, c = 9, система приобретает вид:

1) α²х + αу = α³

αх + у = α²

у = α² + 6αх

2) (α + 6)х + (α² +2 )у = 0

(α + 6)х + (α² +2 ) * (α² + 6αх) = 0

αх + 6х + α⁴ + 6α³х + 2α² + 5αх = 0

6α² + 6α + 5α + 5 + 2α² + 6αх + 6х = 0

α² + 4α + 5 + х * (6α + 6) = 0

х * (6α + 6) = 6α² + 3α + 2

х = (6α² + 3α + 2) * (6α + 6)^-1 = (6α² + 3α + 2) * (6α² + α + 5) = 2α² + 6α

у = α² + 6αх = α² + 5α³ + α² = 2α² + 2α + 2

Ответ: (2α² + 6α, 2α² + 2α + 2)

 

1.8. По формуле быстрого возведения в степень вычислить α^b+c (mod 701).

α⁶⁺⁹ = α¹⁵ = α * α² * α⁴ * α⁸

Вероятно, в задании под α подразумевался примитивный элемент в поле GF(701), так как число 701 не является степенью другого числа, то есть это поле не является расширением меньшего поля, и, следовательно, в нем не может быть элемента α. В таком случае, примитивный элемент для этого поля будет:

α = 2

α² = 4

α⁴ = 16

α⁸ = 256

α¹⁵ = α * α² * α⁴ * α⁸ = 2 * 4 * 16 * 256 (mod 701) = 522

 

 

Задание 2.

 

2.1. Над полем GF(2) методом Гаусса найти определитель матрицы А размера n x n, состоящей из младших разрядов двоичного разложения числа abс, сдвинутого циклически.

abc = 101111010

А =

|A| = 1 * 1 * 1 = 1

 

2.2. Методом Гаусса найти характеристический многочлен матрицы А.

 

Характеристический многочлен f(λ):

f(λ) = |A - λE| = = λ³ + 0 + 1 – 0 – λ – λ = λ³ + 1

2.3. Разложить многочлен f(λ) над полем GF(2) на неприводимые множители и найти его корни.

f(λ) = λ³ + 1 = (λ² + λ + 1)( λ + 1)

λ² + λ + 1 = 0 – корней не имеет

λ + 1 = 0

λ = 1

Ответ: 1.

 

2.4. Найти собственные вектора для всех собственных значений матрицы А.

А =

Определим координаты собственного вектора:

= λ³ + 1

Находим корни:

λ³+1=0

λ = 1

Подставляем в систему:

Ранг матрицы системы линейных уравнений = 2, следовательно, зависимых переменных две, свободная одна.

Пусть – свободная переменная, тогда:

Ф.С.Р:

Таким образом, все собственные векторы матрицы А:

(1, 1, 0), (0, 0, 0)

 

 

2.5. Разложить на неприводимые множители над полем GF(2) многочлен f(x).

?задание разложить многочлен есть, а самого многочлена в задании нет

 

 

2.6. Найти элемент, обратный по умножению к элементу в поле GF(2⁷).

 

λ(α) = α⁷ + α⁶ + α⁹

Построим поле, используя элемент α⁷ + α³ + 1

f(x) = x⁷ + x³ + 1

f(x) ≠ 0

f(α) = 0

α⁷ + α³ + 1 = 0

α⁷ = α³ + 1

α⁸ = α⁴ + α

α⁹ = α⁵ + α²

α¹⁰ = α⁶ + α³

α¹¹ = α⁴ + α³ + 1

Элемент, которому ищем обратный, будет иметь вид:

λ(α) = α⁷ + α⁶ + α⁹ = α⁶ + α⁵ + α³ + α² + 1

Найдем обратный, используя алгоритм Евклида:

f(α) = (α + 1) * λ(α) + (α⁵ + α⁴ + α³ + α² + α)

λ(α) = α * (α⁵ + α⁴ + α³ + α² + α) + (α⁴ + 1)

(α⁵ + α⁴ + α³ + α² + α) = (α + 1) * (α⁴ + 1) + (α³ + α² + 1)

(α⁴ + 1) = (α + 1) * (α³ + α² + 1) + (α² + α)

(α³ + α² + 1) = α * (α² + α) + 1

1 = (α³ + α² + 1) + α * (α² + α)

1 = (α³ + α² + 1) + α * (α² + α) = (α³ + α² + 1) + α * [(α⁴ + 1) + (α + 1) * (α³ + α² + 1)] = = α * (α⁴ + 1) + (α² + α + 1) * (α³ + α² + 1) = α * (α⁴ + 1) + (α² + α + 1) * [(α⁵ + α⁴ + α³ + α² +

+ α) + (α + 1) * (α⁴ + 1)] = (α² + α + 1) * (α⁵ + α⁴ + α³ + α² + α) + (α³ + α + 1) * (α⁴ + 1) =

= (α² + α + 1) * (α⁵ + α⁴ + α³ + α² + α) + (α³ + α + 1) * [λ(α) + α * (α⁵ + α⁴ + α³ + α² + α)] =

= (α³ + α + 1) * λ(α) + (α⁴ + 1) * (α⁵ + α⁴ + α³ + α² + α) = (α³ + α + 1) * λ(α) + (α⁴ + 1) *

* [f(α) + (α + 1) * λ(α)] = (α⁴ + 1) * f(α) + (α⁵ + α⁴ + α³) * λ(α) = 0 + (α⁵ + α⁴ + α³) * λ(α) =

= (λ(α))^-1 * λ(α)

Обратный по умножению для α⁶ + α⁵ + α³ + α² + 1 будет α⁵ + α⁴ + α³

Проверка:

(α⁶ + α⁵ + α³ + α² + 1) * (α⁵ + α⁴ + α³) = α¹¹ + α¹⁰ + α⁸ + α⁷ + α⁵ + α¹⁰ + α⁹ + α⁷ + α⁶ +

+ α⁴ + α⁹ + α⁸ + α⁶ + α⁵ + α³ = α¹¹ + α⁴ + α³ = α⁴ + α³ + 1 + α⁴