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

Ненулевые элементы поля. Таблица логарифма Якоби. Матрица системы линейных уравнений. Перепроверка по методу Евклида. Формула быстрого возведения. Определение матрицы методом Гаусса. Собственные значений матрицы. Координаты собственного вектора.

Рубрика Математика
Вид контрольная работа
Язык русский
Дата добавления 20.12.2012
Размер файла 192,1 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

Челябинск 2012

Задание 1

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

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

GF(pn) = {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; б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; 2б2; 2б2+1; 2б2+2; 2б2+3; 2б2+4; 2б2+5; 2б2+6; 2б2+б; 2б2+б +1; 2б2+б +2; 2б2+б +3; 2б2+б +4; 2б2+б +5; 2б2+б +6; 2б2+2б; 2б2+2б +1; 2б2+2б +2; 2б2+2б +3; 2б2+2б +4; 2б2+2б +5; 2б2+2б +6; 2б2+3б; 2б2+3б +1; 2б2+3б +2; 2б2+3б +3; 2б2+3б +4; 2б2+3б +5; 2б2+3б +6; 2б2+4б; 2б2+4б +1; 2б2+4б +2; 2б2+4б +3; 2б2+4б +4; 2б2+4б +5; 2б2+4б +6; 2б2+5б; 2б2+5б +1; 2б2+5б +2; 2б2+5б +3; 2б2+5б +4; 2б2+5б +5; 2б2+5б +6; 2б2+6б; 2б2+6б +1; 2б2+6б +2; 2б2+6б +3; 2б2+6б +4; 2б2+6б +5; 2б2+6б +6; 3б2; 3б2+1; 3б2+2; 3б2+3; 3б2+4; 3б2+5; 3б2+6; 3б2+б; 3б2+б +1; 3б2+б +2; 3б2+б +3; 3б2+б +4; 3б2+б +5; 3б2+б +6; 3б2+2б; 3б2+2б +1; 3б2+2б +2; 3б2+2б +3; 3б2+2б +4; 3б2+2б +5; 3б2+2б +6; 3б2+3б; 3б2+3б +1; 3б2+3б +2; 3б2+3б +3; 3б2+3б +4; 3б2+3б +5; 3б2+3б +6; 3б2+4б; 3б2+4б +1; 3б2+4б +2; 3б2+4б +3; 3б2+4б +4; 3б2+4б +5; 3б2+4б +6; 3б2+5б; 3б2+5б +1; 3б2+5б +2; 3б2+5б +3; 3б2+5б +4; 3б2+5б +5; 3б2+5б +6; 3б2+6б; 3б2+6б +1; 3б2+6б +2; 3б2+6б +3; 3б2+6б +4; 3б2+6б +5; 3б2+6б +6; 4б2; 4б2+1; 4б2+2; 4б2+3; 4б2+4; 4б2+5; 4б2+6; 4б2+б; 4б2+б +1; 4б2+б +2; 4б2+б +3; 4б2+б +4; 4б2+б +5; 4б2+б +6; 4б2+2б; 4б2+2б +1; 4б2+2б +2; 4б2+2б +3; 4б2+2б +4; 4б2+2б +5; 4б2+2б +6; 4б2+3б; 4б2+3б +1; 4б2+3б +2; 4б2+3б +3; 4б2+3б +4; 4б2+3б +5; 4б2+3б +6; 4б2+4б; 4б2+4б +1; 4б2+4б +2; 4б2+4б +3; 4б2+4б +4; 4б2+4б +5; 4б2+4б +6; 4б2+5б; 4б2+5б +1; 4б2+5б +2; 4б2+5б +3; 4б2+5б +4; 4б2+5б +5; 4б2+5б +6; 4б2+6б; 4б2+6б +1; 4б2+6б +2; 4б2+6б +3; 4б2+6б +4; 4б2+6б +5; 4б2+6б +6; 5б2; 5б2+1; 5б2+2; 5б2+3; 5б2+4; 5б2+5; 5б2+6; 5б2+б; 5б2+б +1; 5б2+б +2; 5б2+б +3; 5б2+б +4; 5б2+б +5; 5б2+б +6; 5б2+2б; 5б2+2б +1; 5б2+2б +2; 5б2+2б +3; 5б2+2б +4; 5б2+2б +5; 5б2+2б +6; 5б2+3б; 5б2+3б +1; 5б2+3б +2; 5б2+3б +3; 5б2+3б +4; 5б2+3б +5; 5б2+3б +6; 5б2+4б; 5б2+4б +1; 5б2+4б +2; 5б2+4б +3; 5б2+4б +4; 5б2+4б +5; 5б2+4б +6; 5б2+5б; 5б2+5б +1; 5б2+5б +2; 5б2+5б +3; 5б2+5б +4; 5б2+5б +5; 5б2+5б +6; 5б2+6б; 5б2+6б +1; 5б2+6б +2; 5б2+6б +3; 5б2+6б +4; 5б2+6б +5; 5б2+6б +6; 6б2; 6б2+1; 6б2+2; 6б2+3; 6б2+4; 6б2+5; 6б2+6; 6б2+б; 6б2+б +1; 6б2+б +2; 6б2+б +3; 6б2+б +4; 6б2+б +5; 6б2+б +6; 6б2+2б; 6б2+2б +1; 6б2+2б +2; 6б2+2б +3; 6б2+2б +4; 6б2+2б +5; 6б2+2б +6; 6б2+3б; 6б2+3б +1; 6б2+3б +2; 6б2+3б +3; 6б2+3б +4; 6б2+3б +5; 6б2+3б +6; 6б2+4б; 6б2+4б +1; 6б2+4б +2; 6б2+4б +3; 6б2+4б +4; 6б2+4б +5; 6б2+4б +6; 6б2+5б; 6б2+5б +1; 6б2+5б +2; 6б2+5б +3; 6б2+5б +4; 6б2+5б +5; 6б2+5б +6; 6б2+6б; 6б2+6б +1; 6б2+6б +2; 6б2+6б +3; 6б2+6б +4; 6б2+6б +5; 6б2+6б +6}

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

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

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

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

2 + 2)1 = б2 + 2

2 + 2)2 = 3б2 + 6б + 4

2 + 2)3 = 3б + 2

2 + 2)4 = 2б2+б +3

2 + 2)5 = 3б2 + б + 6

2 + 2)6 = 2б2 + 5б + 4

2 + 2)7 = 6б2 + 3б + 3

2 + 2)8 = 2б2 + 4б + 3

2 + 2)9 = 5б2 + 2б + 2

2 + 2)10 = 4б + 2

2 + 2)11 = 2б2 + 4б

2 + 2)12 = 2б2+2б+3

2 + 2)13 = 5б2+4

2 + 2)14 = 2б2+2б+1

2 + 2)15 = 3б2

2 + 2)16 = 3б2+4б

2 + 2)17 = 3б2+б +3

2 + 2)18 = 6б2+5б +5

2 + 2)19 = 4б2+6б + 5

2 + 2)20 = 2б2+2б+4

2 + 2)21 = 6б2+6

2 + 2)22 = 5б2+б +5

2 + 2)23 = 3б2+3б +2

2 + 2)24 = 5б2+1

2 + 2)25 = 6б2+2б +2

2 + 2)26 = б2+3б+2

2 + 2)27 = 3б2+2б+1

2 + 2)28 = 4б2+6б

2 + 2)29 = 4б2+2б+1

2 + 2)30 = 5б2+5б

2 + 2)31 = 5б+2

2 + 2)32 = 2б+4

2 + 2)33 = 4б2+2б+6

2 + 2)34 = 3б2+5б+3

2 + 2)35 = 6б2+2б+1

2 + 2)36 = 3б

2 + 2)37 = 3б+4

2 + 2)38 = 4б2+3б+5

2 + 2)39 = 2б2+6б

2 + 2)40 = 2б2+4б+1

2 + 2)41 = 3б2+2б+5

2 + 2)42 = б2+6б+1

2 + 2)43 = 2б2+5б+3

2 + 2)44 = 5б2+3б+1

2 + 2)45 = 6б2+5б+6

2 + 2)46 = 5б2+6б

2 + 2)47 = 5б2+б+1

2 + 2)48 = 6б2+3б+1

2 + 2)49 = 4б+6

2 + 2)50 = 6б2+4б+1

2 + 2)51 = 5б+5

2 + 2)52 = 5б2+5б+5

2 + 2)53 = 3б2+5

2 + 2)54 = б2+4б+3

2 + 2)55 = 4б2+3б+2

2 + 2)56 = 6б2+6б+1

2 + 2)57 = 3

2 + 2)58 = 3б2+6

2 + 2)59 = 2б2+4б+5

2 + 2)60 = 2б+6

2 + 2)61 = 6б2+2б+3

2 + 2)62 = 2б2+3б+4

2 + 2)63 = 6б2+б+5

2 + 2)64 = 4б2+2б+2

2 + 2)65 = 6б2+5б+2

2 + 2)66 = б2+6б+6

2 + 2)67 = 5б+6

2 + 2)68 = 6б2+5б

2 + 2)69 = 6б2+6б+2

2 + 2)70 = б2+5

2 + 2)71 = 6б2+6б+3

2 + 2)72 = 2б2

2 + 2)73 = 2б2+5б

2 + 2)74 = 2б2+3б+2

2 + 2)75 = 4б2+б+1

2 + 2)76 = 5б2+4б+1

2 + 2)77 = 6б2+6б+5

2 + 2)78 = 4б2+4

2 + 2)79 = б2+3б+1

2 + 2)80 = 2б2+2б+6

2 + 2)81 = б2+3

2 + 2)82 = 4б2+6б+6

2 + 2)83 = 3б2+2б+6

2 + 2)84 = 2б2+6б+3

2 + 2)85 = 5б2+4б

2 + 2)86 = 5б2+6б+3

2 + 2)87 = б2

2 + 2)88 = б2+6

2 + 2)89 = 6б+5

2 + 2)90 = 5б2+6б+4

2 + 2)91 = 2б2+б+2

2 + 2)92 = 4б2+6б+3

2 + 2)93 = 2б

2 + 2)94 = 2б+5

2 + 2)95 = 5б2+2б+1

2 + 2)96 = 6б2+4б

2 + 2)97 = 6б2+5б+3

2 + 2)98 = 2б2+6б+1

2 + 2)99 = 3б24б+3

2 + 2)100 = 6б2+б+2

2 + 2)101 = б2+2б+3

2 + 2)102 = 4б2+б+4

2 + 2)103 = б2+4б

2 + 2)104 = б2+3б+3

2 + 2)105 = 4б2+2б+3

2 + 2)106 = 5б+4

2 + 2)107 = 4б2+5б+3

2 + 2)108 = б+1

2 + 2)109 = б2+б+1

2 + 2)110 = 2б2+1

2 + 2)111 = 3б2+5б+2

2 + 2)112 = 5б2+2б+6

2 + 2)113 = 4б2+4б+3

2 + 2)114 = 2

2 + 2)115 = 2б2+4

2 + 2)116 = 6б2+5б+1

2 + 2)117 = 6б+4

2 + 2)118 = 4б2+6б+2

2 + 2)119 = 6б2+2б+5

2 + 2)120 = 4б2+3б+1

2 + 2)121 = 5б2+6б+6

2 + 2)122 = 4б2+б+6

2 + 2)123 = 3б2+4б+4

2 + 2)124 = б+4

2 + 2)125 = 4б2

2 + 2)126 = 4б2+4б+6

2 + 2)127 = 3б2+1

2 + 2)128 = 4б2+4б+2

2 + 2)129 = 6б2

2 + 2)130 = 6б2

2 + 2)131 = 6б2+2б+6

2 + 2)132 = 5б2+3б+3

2 + 2)133 = б2+5б+3

2 + 2)134 = 4б2+4б+1

2 + 2)135 = 5б2+5

2 + 2)136 = 3б2+2б+3

2 + 2)137 = 6б2+6б+4

2 + 2)138 = 3б2+2

2 + 2)139 = 5б2+4б+4

2 + 2)140 = 2б2+6б+4

2 + 2)141 = 6б2+4б+2

2 + 2)142 = б2+5б

2 + 2)143 = б2+4б+2

2 + 2)144 = 3б2+3б

2 + 2)145 = 3б2+4

2 + 2)146 = 4б+1

2 + 2)147 = б2+4б+5

2 + 2)148 = 6б2+3б+6

2 + 2)149 = 5б2+4б+2

2 + 2)150 = 6б

2 + 2)151 = 6б+1

2 + 2)152 = б2+6б+3

2 + 2)153 = 4б2+5б

2 + 2)154 = 4б2+б+2

2 + 2)155 = 6б2+4б+3

2 + 2)156 = 2б2+5б+2

2 + 2)157 = 4б2+3б+6

2 + 2)158 = 3б2+6б+2

2 + 2)159 = 5б2+3б+5

2 + 2)160 = 3б2+5б

2 + 2)161 = 3б2+2б+2

2 + 2)162 = 5б2+6б+2

2 + 2)163 = б+5

2 + 2)164 = 5б2+б+2

2 + 2)165 = 3б+3

2 + 2)166 = 3б2+3б+3

2 + 2)167 = 6б2+3

2 + 2)168 = 2б2+б+6

2 + 2)169 = б2+6б+4

2 + 2)170 = 5б2+5б+2

2 + 2)171 = 6

2 + 2)172 = 6б2+5

2 + 2)173 = 4б2+б+3

2 + 2)174 = 4б+5

2 + 2)175 = 5б2+4б+6

2 + 2)176 = 4б2+6б+1

2 + 2)177 = 5б2+2б+3

2 + 2)178 = б2+4б+4

2 + 2)179 = 5б2+3б+4

2 + 2)180 = 2б2+5б+5

2 + 2)181 = 3б+5

2 + 2)182 = 5б2+3б

2 + 2)183 = 5б2+5б+4

2 + 2)184 = 2б2+3

2 + 2)185 = 5б2+5б+6

2 + 2)186 = 4б2

2 + 2)187 = 4б2+3б

2 + 2)188 = 4б2+6б+4

2 + 2)189 = б2+2б+2

2 + 2)190 = 3б2+б+2

2 + 2)191 = 5б2+5б+3

2 + 2)192 = б2+1

2 + 2)193 = 2б2+6б+2

2 + 2)194 = 4б2+4б+5

2 + 2)195 = 2б2+6

2 + 2)196 = б2+5б+5

2 + 2)197 = 6б2+4б+5

2 + 2)198 = 4б2+5б+6

2 + 2)199 = 3б2

2 + 2)200 = 3б2+5б+6

2 + 2)201 = 2б2+2б

2 + 2)202 = 2б2+5

2 + 2)203 = 5б+3

2 + 2)204 = 3б2+5б+1

2 + 2)205 = 4б2+2б+4

2 + 2)206 = б2+5б+6

2 + 2)207 = 4б

2 + 2)208 = 4б+3

2 + 2)209 = 3б2+4б+2

2 + 2)210 = 5б2

2 + 2)211 = 5б2+3б+6

2 + 2)212 = 4б2+5б+2

2 + 2)213 = 6б2+б+6

2 + 2)214 = 5б2+2б+4

2 + 2)215 = 2б2+4б+6

2 + 2)216 = б2+2б+1

2 + 2)217 = 2б2

2 + 2)218 = 2б2+6б+6

2 + 2)219 = б2+4б+6

2 + 2)220 = 3б+1

2 + 2)221 = б2+3б+6

2 + 2)222 = 2б+2

2 + 2)223 = 2б2+2б+2

2 + 2)224 = 4б2+2

2 + 2)225 = 6б2+3б+4

2 + 2)226 = 3б2+4б+5

2 + 2)227 = б2+б+6

2 + 2)228 = 4

2 + 2)229 = 4б2+1

2 + 2)230 = 5б2+3б+1

2 + 2)231 = 5б+1

2 + 2)232 = б2+5б+4

2 + 2)233 = 5б2+4б+3

2 + 2)234 = б2+6б+2

2 + 2)235 = 3б2+5б+5

2 + 2)236 = б2+2б+5

2 + 2)237 = 6б2+б+1

2 + 2)238 = 2б+1

2 + 2)239 = б2+2б

2 + 2)240 = б2+б+5

2 + 2)241 = 6б2+2

2 + 2)242 = б2+б+4

2 + 2)243 = 5б2

2 + 2)244 = 5б2+2б

2 + 2)245 = 5б2+4б+5

2 + 2)246 = 3б2+6б+6

2 + 2)247 = 2б2+3б+6

2 + 2)248 = б2+б+2

2 + 2)249 = 5б+1

2 + 2)250 = 6б2+4б+6

2 + 2)251 = 5б2+5б+1

2 + 2)252 = 6б2+4

2 + 2)253 = 3б2+б+1

2 + 2)254 = 4б2+5б+1

2 + 2)255 = 5б2+б+4

2 + 2)256 = 2б2+3б

2 + 2)257 = 2б2+б+4

2 + 2)258 = 6б2+6б

2 + 2)259 = 6б2+1

2 + 2)260 = б+2

2 + 2)261 = 2б2+1б+3

2 + 2)262 = 5б2+6б+5

2 + 2)263 = 3б2+б+4

2 + 2)264 = 5б

2 + 2)265 = 5б+2

2 + 2)266 = 2б2+5б+6

2 + 2)267 = б2+3б

2 + 2)268 = б2+2б+4

2 + 2)269 = 5б2+б+6

2 + 2)270 = 4б2+3б+4

2 + 2)271 = б2+6б+5

2 + 2)272 = 6б2+5б+4

2 + 2)273 = 3б2+6б+3

2 + 2)274 = 6б2+3б

2 + 2)275 = 6б2+4б+4

2 + 2)276 = 3б2+5б+4

2 + 2)277 = 2б+3

2 + 2)278 = 3б2+2б+4

2 + 2)279 = 6б+6

2 + 2)280 = 6б2+6б+6

2 + 2)281 = 5б2+6

2 + 2)282 = 4б2+2б+5

2 + 2)283 = 2б2+5б+1

2 + 2)284 = 3б2+3б+4

2 + 2)285 = 5

2 + 2)286 = 5б2+3

2 + 2)287 = б2+2б+6

2 + 2)288 = б+3

2 + 2)289 = 3б2+б+5

2 + 2)290 = б2+5б+2

2 + 2)291 = 3б2+4б+6

2 + 2)292 = 2б2+б+1

2 + 2)293 = 3б2+6б+1

2 + 2)294 = 4б2+3б+3

2 + 2)295 = 6б+3

2 + 2)296 = 3б2+6б

2 + 2)297 = 3б2+3б+1

2 + 2)298 = 4б2+6

2 + 2)299 = 3б2+3б+5

2 + 2)300 = б2

2 + 2)301 = б2+6б

2 + 2)302 = б2+5б+1

2 + 2)303 = 2б2+4б+4

2 + 2)304 = 6б2+2б+4

2 + 2)305 = 3б2+3б+6

2 + 2)306 = 2б2+2

2 + 2)307 = 4б2+5б+4

2 + 2)308 = б2+б+3

2 + 2)309 = 4б2+5

2 + 2)310 = 2б2+3б+3

2 + 2)311 = 5б2+б+3

2 + 2)312 = б2+3б+5

2 + 2)313 = 6б2+2б

2 + 2)314 = 6б2+3б+5

2 + 2)315 = 4б2+4б

2 + 2)316 = 4б2+3

2 + 2)317 = 3б+6

2 + 2)318 = 6б2+3б+2

2 + 2)319 = б2+4б+1

2 + 2)320 = 2б2+3б+5

2 + 2)321 = б

2 + 2)322 = б+6

2 + 2)323 = 6б2+б+4

2 + 2)324 = 3б2+2б

2 + 2)325 = 3б2+6б+5

2 + 2)326 = б2+3б+4

2 + 2)327 = 5б2+2б+5

2 + 2)328 = 3б2+4б+1

2 + 2)329 = 4б2+б+5

2 + 2)330 = 2б2+4б+2

2 + 2)331 = 4б2+2б

2 + 2)332 = 4б2+5б+5

2 + 2)333 = 2б2+б+5

2 + 2)334 = 6б+2

2 + 2)335 = 2б2+6б+5

2 + 2)336 = 4б+4

2 + 2)337 = 4б2+4б+4

2 + 2)338 = б2+4

2 + 2)339 = 5б2+6б+1

2 + 2)340 = 6б2+б+3

2 + 2)341 = 2б2+2б+5

2 + 2)342 = 1

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

m

(m)

0

114

1

81

2

325

3

165

4

74

5

199

6

180

7

225

8

303

9

177

10

208

11

40

12

20

13

135

14

223

15

127

16

328

17

263

18

45

19

82

20

341

21

129

22

269

23

166

24

31

25

61

26

104

27

161

m

(m)

28

176

29

64

30

251

31

286

32

94

33

331

34

276

35

25

36

220

37

181

38

157

39

98

40

330

41

83

42

234

43

6

44

230

45

68

46

339

47

164

48

318

49

207

50

141

51

67

52

185

53

58

54

178

55

294

56

69

57

228

58

15

59

215

60

93

61

304

62

320

63

213

64

105

65

97

66

301

67

264

68

116

69

71

70

88

71

137

72

110

73

283

74

310

75

154

76

149

77

280

78

309

79

26

80

201

81

338

82

28

83

324

84

140

85

76

86

90

87

109

88

300

89

279

90

262

91

261

92

188

93

238

94

60

95

9

96

50

97

272

98

193

99

123

100

340

101

268

102

329

103

319

104

326

105

205

106

51

107

307

108

260

109

248

110

306

111

34

112

244

113

337

114

57

115

202

116

65

117

89

118

92

119

131

120

55

121

46

122

125

123

226

124

163

125

75

126

315

127

138

128

113

129

259

130

237

131

313

132

179

133

232

134

128

135

281

136

278

137

77

138

249

139

245

140

335

141

155

142

302

143

54

144

297

145

53

146

10

147

219

148

274

149

233

150

151

151

334

152

169

153

254

154

173

155

275

156

43

157

187

158

273

159

211

160

204

161

136

162

86

163

322

164

311

165

37

166

284

167

252

168

217

169

271

170

191

171

-

172

21

173

102

174

49

175

85

176

118

177

214

178

147

179

159

180

266

181

317

182

44

183

52

184

115

185

30

186

229

187

120

188

19

189

101

190

17

191

183

192

1

193

84

194

126

195

72

196

206

197

250

198

153

199

253

200

160

201

14

202

195

203

106

204

111

205

282

206

142

207

146

208

336

209

99

210

47

211

182

212

107

213

130

214

327

215

11

216

189

217

292

218

39

219

103

220

3

221

267

222

277

223

12

224

316

225

314

226

291

227

87

228

285

229

224

230

132

231

265

232

196

233

139

234

152

235

200

236

287

237

100

238

222

239

216

240

227

241

167

242

240

243

24

244

95

245

175

246

296

247

256

248

308

249

145

250

96

251

170

252

172

253

190

254

212

255

22

256

4

257

333

258

56

259

241

260

288

261

257

262

121

263

289

264

231

265

203

266

73

267

79

268

236

269

210

270

38

271

66

272

18

273

2

274

48

275

197

276

235

277

32

278

41

279

150

280

258

281

243

282

33

283

156

284

299

285

171

286

13

287

239

288

124

289

5

290

133

291

16

292

91

293

158

294

270

295

117

296

293

297

23

298

186

299

305

300

192

301

42

302

290

303

59

304

119

305

144

306

184

307

332

308

242

309

298

310

62

311

255

312

221

313

35

314

148

315

134

316

78

317

36

318

7

319

143

320

247

321

108

322

321

323

63

324

27

325

246

326

312

327

112

328

209

329

122

330

8

331

29

332

198

333

168

334

295

335

218

336

174

337

194

338

70

339

162

340

323

341

80

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

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

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

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

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

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

Решение:

1) x(б + 1) = 2

x = 2(б + 1)-1 = 2(б2+6б+2) = 2б2 + 5б + 4

2) 2x + 3z = 6 + б

z = (6 + б + 5x) * 3-1 = (6 + б + 5(2б2 + 5б + 4)) * 5 = (6 + б + 3б2 + 4б + 6) *5 = = (3б2 + 5б + 5) * 5 = б2 + 4б + 4

3) x + 2y + z = 2

y = (2 + 6x + 6z) * 2-1 = (2 + 6(2б2 + 5б + 4) + 6(б2 + 4б + 4)) * 4 = (2 + 5б2 + 2б + 3 + + 6б2 + 3б +3) * 4 = (4б2 + 5б + 1) * 4 = 2б2 + 6б + 4

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

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

б + с = б + 2

(б + 2)-1 = 4б2 + 6б + 6

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

f(б) = б3 + б + 1

g(б) = б + 2

f(б) = (б2+5б+5) * g(б) + 5

g(б) = 3б * 5 + 2

5 = 2 * 2 + 1

1 = 5 - 2 * 2

2 = g(б) - 3б * 5

5 = f(б) - (б2+5б+5) * g(б)

1 = 5 - 2 * 2 = 5 - 2 * (g(б) - 3б * 5) = (6б+1) * 5 + 5 * g(б) = (6б+1) * (f(б) - (б2+5б+5) * * g(б)) + 5 * g(б) = (6б+1) * f(б) + (б3+5б2+5б+6б2+2б+2+5) * g(б) = 0 + (4б2+6б+6) * * g(б) = (g(б))-1 * g(б)

(g(б))-1 = 4б2+6б+6

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

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

1) б2х + бу = б3

бх + у = б2

у = б2 + 6бх

2) (б + 6)х + (б2 +2 )у = 0

(б + 6)х + (б2 +2 ) * (б2 + 6бх) = 0

бх + 6х + б4 + 6б3х + 2б2 + 5бх = 0

2 + 6б + 5б + 5 + 2б2 + 6бх + 6х = 0

б2 + 4б + 5 + х * (6б + 6) = 0

х * (6б + 6) = 6б2 + 3б + 2

х = (6б2 + 3б + 2) * (6б + 6)-1 = (6б2 + 3б + 2) * (6б2 + б + 5) = 2б2 + 6б

у = б2 + 6бх = б2 + 5б3 + б2 = 2б2 + 2б + 2

Ответ: (2б2 + 6б, 2б2 + 2б + 2)

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

б6+9 = б15 = б * б2 * б4 * б8

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

б = 2

б2 = 4

б4 = 16

б8 = 256

б15 = б * б2 * б4 * б8 = 2 * 4 * 16 * 256 (mod 701) = 522

Задание 2

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

abc = 101111010

А =

|A| = 1 * 1 * 1 = 1

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

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

f(л) = |A - лE| = = л3 + 0 + 1 - 0 - л - л = л3 + 1

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

f(л) = л3 + 1 = (л2 + л + 1)( л + 1)

л2 + л + 1 = 0 - корней не имеет

л + 1 = 0

л = 1

Ответ: 1.

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

А =

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

= л3 + 1

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

л3+1=0

л = 1

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

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

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

логарифм линейный уравнение вектор

Ф.С.Р:

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

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

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

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

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

л(б) = б7 + б6 + б9

Построим поле, используя элемент б7 + б3 + 1

f(x) = x7 + x3 + 1

f(x) ? 0

f(б) = 0

б7 + б3 + 1 = 0

б7 = б3 + 1

б8 = б4 + б

б9 = б5 + б2

б10 = б6 + б3

б11 = б4 + б3 + 1

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

л(б) = б7 + б6 + б9 = б6 + б5 + б3 + б2 + 1

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

f(б) = (б + 1) * л(б) + (б5 + б4 + б3 + б2 + б)

л(б) = б * (б5 + б4 + б3 + б2 + б) + (б4 + 1)

5 + б4 + б3 + б2 + б) = (б + 1) * (б4 + 1) + (б3 + б2 + 1)

4 + 1) = (б + 1) * (б3 + б2 + 1) + (б2 + б)

3 + б2 + 1) = б * (б2 + б) + 1

1 = (б3 + б2 + 1) + б * (б2 + б)

1 = (б3 + б2 + 1) + б * (б2 + б) = (б3 + б2 + 1) + б * [(б4 + 1) + (б + 1) * (б3 + б2 + 1)] = = б * (б4 + 1) + (б2 + б + 1) * (б3 + б2 + 1) = б * (б4 + 1) + (б2 + б + 1) * [(б5 + б4 + б3 + б2 +

+ б) + (б + 1) * (б4 + 1)] = (б2 + б + 1) * (б5 + б4 + б3 + б2 + б) + (б3 + б + 1) * (б4 + 1) =

= (б2 + б + 1) * (б5 + б4 + б3 + б2 + б) + (б3 + б + 1) * [л(б) + б * (б5 + б4 + б3 + б2 + б)] =

= (б3 + б + 1) * л(б) + (б4 + 1) * (б5 + б4 + б3 + б2 + б) = (б3 + б + 1) * л(б) + (б4 + 1) *

* [f(б) + (б + 1) * л(б)] = (б4 + 1) * f(б) + (б5 + б4 + б3) * л(б) = 0 + (б5 + б4 + б3) * л(б) =

= (л(б))-1 * л(б)

Обратный по умножению для б6 + б5 + б3 + б2 + 1 будет б5 + б4 + б3

Проверка:

6 + б5 + б3 + б2 + 1) * (б5 + б4 + б3) = б11 + б10 + б8 + б7 + б5 + б10 + б9 + б7 + б6 +

+ б4 + б9 + б8 + б6 + б5 + б3 = б11 + б4 + б3 = б4 + б3 + 1 + б4 + б3 = 1

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

Найти порядок элемента л(б)

б7 = б3 + 1

б8 = б4 + б

б9 = б5 + б2

б10 = б6 + б3

б11 = б4 + б3 + 1

б12 = б5 + б4 + б

б20 = (б6 + б3) * (б6 + б3) = б12 + б9 + б9 + б6 = б6 + б5 + б4 + б

б21 = б20 * б = (б6 + б5 + б4 + б) * б = б7 + б6 + б5 + б2 = б3 + 1 + б6 + б5 + б2 =

= б6 + б5 + б3 + б2 + 1

л(б) = б21

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

бс = б9

9)2 = б6 + б4 + б3

9)4 = б6 + б5

9)8 = (б9)4 * (б9)4 = б6 + б5 + б4 + б3 + б

9)16 = (б9)8 * (б9)8 = б5 + б3 + б2

9)32 = (б9)16 * (б9)16 = б4 + б3

9)64 = (б9)32 * (б9)32 = б6 + б4 + 1

9)96 = (б9)64 * (б9)32 = б6 + б2 + б + 1

9)112 = (б9)96 * (б9)16 = б6 + б5 + б

9)113 = (б9)112 * б9 = б

9)113 = б

Ответ: в 113 степени.

Задание 3

sn+b = sn+b-2 + sn

sn+6 = sn+4 + sn

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

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

Sn+6 = Sn+4 + Sn

Sn+6 - Sn-4 - Sn = 0

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

х6 - х4 - 1 = 0

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

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

х6 + х4 + 1 = 0

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

3 + х2 + 1)2 = 0

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

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

Sn = в1 + в2 + в3 + в4 + в5 + в6

Где б1, б2, б3, б4, б5, б6 - корни характеристического уравнения. В поле GF(27) характеристическое уравнение решений не имеет, следовательно невозможно записать явное уравнение n-го члена через формулу. Для поля комплексных чисел, где могут быть найдены корни уравнения х6 - х4 - 1 = 0, можно записать явную формулу n-го члена. Корни уравнения будут:

б1 = 1,211

б2 = -1,211

б3 = 0,74 + 0,53i

б4 = 0,74 + 0,53i

б5 = 0,74 - 0,53i

б6 = 0,74 - 0,53i

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

Sn =

в1, в2, в3, в4, в5, в6 находятся при решении системы уравнений:

Решить эту систему не представляется возможным, так как не известны первые k членов последовательности (S0, S1, S2, S3, S4, S5) - вектор инициализации. Явная формула n-го члена последовательности в таком случае будет иметь вид:

Sn =

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

0000001 - шаг 1

0000010 - шаг 2

0000100 - шаг 3

0001001 - шаг 4

0010010 - шаг 5

0100100 - шаг 6

1001001 - шаг 7

0010011 - шаг 8

0100110 - шаг 9

1001101 - шаг 10

0011010 - шаг 11

0110100 - шаг 12

1101001 - шаг 13

1010011 - шаг 14

0100111 - шаг 15

1001111 - шаг 16

0011110 - шаг 17

0111101 - шаг 18

1111011 - шаг 19

1110111 - шаг 20

1101110 - шаг 21

1011100 - шаг 22

0111000 - шаг 23

1110000 - шаг 24

1100001 - шаг 25

1000011 - шаг 26

0000111 - шаг 27

0001111 - шаг 28

0011111 - шаг 29

0111111 - шаг 30

1111111 - шаг 31

1111110 - шаг 32

1111100 - шаг 33

1111000 - шаг 34

1110001 - шаг 35

1100011 - шаг 36

1000111 - шаг 37

0001110 - шаг 38

0011101 - шаг 39

0111011 - шаг 40

1110110 - шаг 41

1101100 - шаг 42

1011000 - шаг 43

0110001 - шаг 44

1100010 - шаг 45

1000101 - шаг 46

0001010 - шаг 47

0010100 - шаг 48

0101001 - шаг 49

1010010 - шаг 50

0100101 - шаг 51

1001011 - шаг 52

0010111 - шаг 53

0101111 - шаг 54

1011111 - шаг 55

0111110 - шаг 56

1111101 - шаг 57

1111010 - шаг 58

1110101 - шаг 59

1101010 - шаг 60

1010101 - шаг 61

0101010 - шаг 62

1010100 - шаг 63

0101000 - шаг 64

1010000 - шаг 65

0100001 - шаг 66

1000010 - шаг 67

0000101 - шаг 68

0001011 - шаг 69

0010110 - шаг 70

0101101 - шаг 71

1011011 - шаг 72

0110111 - шаг 73

1101111 - шаг 74

1011110 - шаг 75

0111100 - шаг 76

1111001 - шаг 77

1110011 - шаг 78

1100111 - шаг 79

1001110 - шаг 80

0011100 - шаг 81

0111001 - шаг 82

1110010 - шаг 83

1100101 - шаг 84

1001010 - шаг 85

0010101 - шаг 86

0101011 - шаг 87

1010110 - шаг 88

0101100 - шаг 89

1011001 - шаг 90

0110011 - шаг 91

1100110 - шаг 92

1001100 - шаг 93

0011000 - шаг 94

0110000 - шаг 95

1100000 - шаг 96

1000001 - шаг 97

0000011 - шаг 98

0000110 - шаг 99

0001101 - шаг 100

0011011 - шаг 101

0110110 - шаг 102

1101101 - шаг 103

1011010 - шаг 104

0110101 - шаг 105

1101011 - шаг 106

1010111 - шаг 107

0101110 - шаг 108

1011101 - шаг 109

0111010 - шаг 110

1110100 - шаг 111

1101000 - шаг 112

1010001 - шаг 113

0100011 - шаг 114

1000110 - шаг 115

0001100 - шаг 116

0011001 - шаг 117

0110010 - шаг 118

1100100 - шаг 119

1001000 - шаг 120

0010001 - шаг 121

0100010 - шаг 122

1000100 - шаг 123

0001000 - шаг 124

0010000 - шаг 125

0100000 - шаг 126

1000000 - шаг 127

0000001 - шаг 128

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

Найти, в какой степени матрица последовательности станет равной единичной

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

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

A =

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

A2 =

A3 =

A4 =

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

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

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

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

Размещено на Allbest.ru


Подобные документы

  • Расчет произведения заданных матриц. Решение системы линейных алгебраических уравнений по формулам Крамера, матричным методом и методом Гаусса. Координаты вектора в базисе. Определение ранга заданной матрицы. Система с базисом методом Жордана-Гаусса.

    контрольная работа [88,2 K], добавлен 19.01.2014

  • Вычисление и построение матрицы алгебраических дополнений. Решение системы линейных уравнений по формулам Крамера, с помощью обратной матрицы и методом Гаусса. Определение главной и проверка обратной матрицы. Аналитическая геометрия на плоскости.

    контрольная работа [126,9 K], добавлен 20.04.2016

  • Разложение определителя 4-го порядка. Проверка с помощью функции МОПРЕД() в программе Microsoft Excel. Нахождение обратной матрицы. Решение системы линейных уравнений методом обратной матрицы и методом Гаусса. Составление общего уравнения плоскости.

    контрольная работа [138,7 K], добавлен 05.07.2015

  • Линейные операции над матрицами. Умножение и вычисление произведения матриц. Приведение матрицы к ступенчатому виду и вычисление ранга матрицы. Вычисление обратной матрицы и определителя матрицы, а также решение систем линейных уравнений методом Гаусса.

    учебное пособие [658,4 K], добавлен 26.01.2009

  • Понятие матрицы. Метод Гаусса. Виды матриц. Метод Крамера решения линейных систем. Действия над матрицами: сложение, умножение. Решение систем линейных уравнений методом Гаусса. Элементарные пребразования систем. Математические перобразования.

    лекция [45,4 K], добавлен 02.06.2008

  • Выполнение действий над матрицами. Определение обратной матрицы. Решение матричных уравнений и системы уравнений матричным способом, используя алгебраические дополнения. Исследование и решение системы линейных уравнений методом Крамера и Гаусса.

    контрольная работа [63,2 K], добавлен 24.10.2010

  • Основные правила решения системы заданных уравнений методом Гаусса с минимизацией невязки и методом простых итераций. Понятие исходной матрицы; нахождение определителя для матрицы коэффициентов. Пример составления блок-схемы метода минимизации невязок.

    лабораторная работа [264,1 K], добавлен 24.09.2014

  • Правила произведения матрицы и вектора, нахождения обратной матрицы и ее определителя. Элементарные преобразования матрицы: умножение на число, прибавление, перестановка и удаление строк, транспонирование. Решение системы уравнений методом Гаусса.

    контрольная работа [462,6 K], добавлен 12.11.2010

  • Метод Гаусса - последовательное исключение переменных из системы уравнений. Определение понятия расширенной матрицы. Метод Крамера, расчет определителя системы. Метод обратной матрицы. Расчет алгебраических дополнений для элементов полученной матрицы.

    презентация [184,4 K], добавлен 21.09.2013

  • Матричные уравнения, их решение и проверка. Собственные числа и собственные векторы матрицы А. Решение системы методом Жорданa-Гаусса. Нахождение пределов и производных функции, ее градиент. Исследование функции методами дифференциального исчисления.

    контрольная работа [287,0 K], добавлен 10.02.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.