Основы криптографии

Министерство образования и науки Российской Федерации Государственное образовательное учреждение высшего профессионального образования Научно-Исследовательский Университет «Южно-Уральский Государственный Университет»

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

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

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

Челябинск 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 Составить таблицу логарифма Якоби

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

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

abc = 101 111 010

А =

|A| = 1 * 1 * 1 = 1

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

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

f (л) = |A — лE| = = л³ + 0 + 1 — 0 — л — л = л³ + 1

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

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

л² + л + 1 = 0 — корней не имеет л + 1 = 0

л = 1

Ответ: 1.

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

А =

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

= л³ + 1

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

л³+1=0

л = 1

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

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

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

логарифм линейный уравнение вектор Ф.С.Р:

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

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

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

задание разложить многочлен есть, а самого многочлена в задании нет Найти элемент, обратный по умножению к элементу в поле 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 + б⁴ + б³ = 1

Проверка показала, что найденный элемент является искомым

Найти порядок элемента л (б) б⁷ = б³ + 1

б⁸ = б⁴ + б б⁹ = б⁵ + б²

б¹⁰ = б⁶ + б³

б¹¹ = б⁴ + б³ + 1

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

= б⁶ + б⁵ + б³ + б² + 1

л (б) = б²¹

Найти в какой степени элемент б^с станет равным элементу б б^с = б⁹

(б⁹)² = б⁶ + б⁴ + б³

(б⁹)⁴ = б⁶ + б⁵

(б⁹)⁸ = (б⁹)⁴ * (б⁹)⁴ = б⁶ + б⁵ + б⁴ + б³ + б

(б⁹)¹⁶ = (б⁹)⁸ * (б⁹)⁸ = б⁵ + б³ + б²

(б⁹)³² = (б⁹)¹⁶ * (б⁹)¹⁶ = б⁴ + б³

(б⁹)⁶⁴ = (б⁹)³² * (б⁹)³² = б⁶ + б⁴ + 1

(б⁹)⁹⁶ = (б⁹)⁶⁴ * (б⁹)³² = б⁶ + б² + б + 1

(б⁹)¹¹² = (б⁹)⁹⁶ * (б⁹)¹⁶ = б⁶ + б⁵ + б

(б⁹)¹¹³ = (б⁹)¹¹² * б⁹ = б

(б⁹)¹¹³ = б Ответ: в 113 степени.

Задание 3

s_n+b = s_n+b-2 + s_n

s_n+6 = s_n+4 + s_n

Нарисовать электронную схему последовательности.

Найти характеристический многочлен последовательности и разложить его на множители.

S_n+6 = S_n+4 + S_n

S_n+6 — S_n-4 — S_n = 0

В таком случае характеристическое уравнение будет иметь вид:

х⁶ — х⁴ — 1 = 0

Вероятнее всего (учитывая последующие задания и использование регистров сдвига для моделирования последовательности), все вычисления проводятся не в поле действительных (или комплексных) чисел, а в поле GF (2^k+1), то есть в поле GF (2⁷). В задании явно не указано, в каком поле проводить вычисления. Данный многочлен имеет в поле действительных чисел 2 корня, и 4 корня в поле комплексных чисел. Решение последующих заданий (а именно 3.4, 3.5, 3.6) возможно только в поле GF (2⁷), поэтому дальнейшее решение будет представлено для этого поля.

В таком случае характеристическое уравнение примет вид:

х⁶ + х⁴ + 1 = 0

И разложится на множители до неприводимых элементов:

(х³ + х² + 1)² = 0

Найти явную формулу для n-го члена рекуррентной последовательности Явная формула для n-го члена рекуррентной последовательности:

S_n = в₁ + в₂ + в₃ + в₄ + в₅ + в₆

Где б₁, б₂, б₃, б₄, б₅, б₆ — корни характеристического уравнения. В поле GF (2⁷) характеристическое уравнение решений не имеет, следовательно невозможно записать явное уравнение n-го члена через формулу. Для поля комплексных чисел, где могут быть найдены корни уравнения х⁶ — х⁴ — 1 = 0, можно записать явную формулу n-го члена. Корни уравнения будут:

б₁ = 1,211

б₂ = -1,211

б₃ = 0,74 + 0,53i

б₄ = 0,74 + 0,53i

б₅ = 0,74 — 0,53i

б₆ = 0,74 — 0,53i

Среди корней присутствуют кратные, значит явная формула n-го члена примет общий вид:

S_n =

в₁, в₂, в₃, в₄, в₅, в₆ находятся при решении системы уравнений:

Решить эту систему не представляется возможным, так как не известны первые k членов последовательности (S₀, S₁, S₂, S₃, S₄, S₅) — вектор инициализации. Явная формула n-го члена последовательности в таком случае будет иметь вид:

S_n =

Найти период последовательности «в лоб»

1 — шаг 1

10 — шаг 2

100 — шаг 3

1 001 — шаг 4

10 010 — шаг 5

100 100 — шаг 6

1 001 001 — шаг 7

10 011 — шаг 8

100 110 — шаг 9

1 001 101 — шаг 10

11 010 — шаг 11

110 100 — шаг 12

1 101 001 — шаг 13

1 010 011 — шаг 14

100 111 — шаг 15

1 001 111 — шаг 16

11 110 — шаг 17

111 101 — шаг 18

1 111 011 — шаг 19

1 110 111 — шаг 20

1 101 110 — шаг 21

1 011 100 — шаг 22

111 000 — шаг 23

1 110 000 — шаг 24

1 100 001 — шаг 25

1 000 011 — шаг 26

111 — шаг 27

1 111 — шаг 28

11 111 — шаг 29

111 111 — шаг 30

1 111 111 — шаг 31

1 111 110 — шаг 32

1 111 100 — шаг 33

1 111 000 — шаг 34

1 110 001 — шаг 35

1 100 011 — шаг 36

1 000 111 — шаг 37

1 110 — шаг 38

11 101 — шаг 39

111 011 — шаг 40

1 110 110 — шаг 41

1 101 100 — шаг 42

1 011 000 — шаг 43

110 001 — шаг 44

1 100 010 — шаг 45

1 000 101 — шаг 46

1 010 — шаг 47

10 100 — шаг 48

101 001 — шаг 49

1 010 010 — шаг 50

100 101 — шаг 51

1 001 011 — шаг 52

10 111 — шаг 53

101 111 — шаг 54

1 011 111 — шаг 55

111 110 — шаг 56

1 111 101 — шаг 57

1 111 010 — шаг 58

1 110 101 — шаг 59

1 101 010 — шаг 60

1 010 101 — шаг 61

101 010 — шаг 62

1 010 100 — шаг 63

101 000 — шаг 64

1 010 000 — шаг 65

100 001 — шаг 66

1 000 010 — шаг 67

101 — шаг 68

1 011 — шаг 69

10 110 — шаг 70

101 101 — шаг 71

1 011 011 — шаг 72

110 111 — шаг 73

1 101 111 — шаг 74

1 011 110 — шаг 75

111 100 — шаг 76

1 111 001 — шаг 77

1 110 011 — шаг 78

1 100 111 — шаг 79

1 001 110 — шаг 80

11 100 — шаг 81

111 001 — шаг 82

1 110 010 — шаг 83

1 100 101 — шаг 84

1 001 010 — шаг 85

10 101 — шаг 86

101 011 — шаг 87

1 010 110 — шаг 88

101 100 — шаг 89

1 011 001 — шаг 90

110 011 — шаг 91

1 100 110 — шаг 92

1 001 100 — шаг 93

11 000 — шаг 94

110 000 — шаг 95

1 100 000 — шаг 96

1 000 001 — шаг 97

11 — шаг 98

110 — шаг 99

1 101 — шаг 100

11 011 — шаг 101

110 110 — шаг 102

1 101 101 — шаг 103

1 011 010 — шаг 104

110 101 — шаг 105

1 101 011 — шаг 106

1 010 111 — шаг 107

101 110 — шаг 108

1 011 101 — шаг 109

111 010 — шаг 110

1 110 100 — шаг 111

1 101 000 — шаг 112

1 010 001 — шаг 113

100 011 — шаг 114

1 000 110 — шаг 115

1 100 — шаг 116

11 001 — шаг 117

110 010 — шаг 118

1 100 100 — шаг 119

1 001 000 — шаг 120

10 001 — шаг 121

100 010 — шаг 122

1 000 100 — шаг 123

1 000 — шаг 124

10 000 — шаг 125

100 000 — шаг 126

1 000 000 — шаг 127

1 — шаг 128

В теоретическом материале было указано, что наибольший период получается при векторе инициализации (0, 0, 0, 0, 0, 0, 1). Такой вектор называется импульсной функцией. При использовании данного вектора инициализации, период получается равен 127, что является наибольшим возможным периодом для данного регистра сдвига (2⁷-1).

Найти, в какой степени матрица последовательности станет равной единичной Предположим, что начальное состояние последовательности (0, 0, 0, 0, 0, 0, 1), которое соответствует максимальному периоду рекуррентной последовательности.

Матрица при данных начальных условиях будет иметь вид:

A =

Найдем степень, в которой матрица, А станет равной единичной, то есть А^m = E

A² =

A³ =

A⁴ =

Найти в какой степени элемент б станет равным 1

Элемент б в нашем регистре будет иметь запись (0, 0, 0, 0, 0, 1, 0)

Элемент 1 в нашем регистре будет иметь запись (0, 0, 0, 0, 0, 0, 1)

Следовательно, надо найти на каком шаге регистр, при векторе инициации б даст 1. Учитывая, что период последовательности = 127, а элемент б следует сразу же за элементом 1, можно утверждать что б¹²⁶ = 1.