PA_full (1127144), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

иделителей единицы.Простые (неразложимые) элементы [x] � неприводимыемногочлены.Вопросы для полей12,,иp:какие многочлены над ними неприводимы?как находить неприводимые многочлены?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаСвойства корней многочленовУтверждениеОстаток от деления многочлена f на многочлен первой степени(x a) равен f (a). В частности, f делится на (x a) iff aявляется корнем f , т. е.

f (a) = 0.16 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаСвойства корней многочленовУтверждениеОстаток от деления многочлена f на многочлен первой степени(x a) равен f (a). В частности, f делится на (x a) iff aявляется корнем f , т. е. f (a) = 0.ДоказательствоРазделим f с остатком на x a.

Остаток должен иметьстепень 0, т.е. f (x) = q · (x a) + b, откуда f (a) = b.16 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа17 / 432Основная теорема алгебрыЛеммаМногочлен степени n имеет не более n корней. Если двамногочлена степени не выше n как функции различны, то ихзначения совпадают не более чем в n точках.) указанные многочлены �сильно отличаются один отдругого�.Это свойство многочленов лежит в основе многих ихприменений в комбинаторике и в теоретической информатике.Теорема (основная теорема алгебры)Всякий многочлен положительной степени над полемкорень.имеетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены надНеприводимые многочлены:18 / 432,иПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над18 / 432,иНеприводимые многочлены:в поле� только многочлены 1-й степени;Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над18 / 432,иНеприводимые многочлены:в поле� только многочлены 1-й степени;в поле�12многочлены 1-й степени,многочлены 2-й степени с отрицательнымдискриминантом;Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над18 / 432,иНеприводимые многочлены:в поле� только многочлены 1-й степени;в поле�12в полемногочлены 1-й степени,многочлены 2-й степени с отрицательнымдискриминантом;� существуют неприводимые многочленыпроизвольной степени (надо показать).Вопрос о приводимости многочлена сводится квопросу о разложении на множители многочлена сцелыми коэффициентами.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКритерий Эйзенштейна � достаточное условиенеприводимости многочленов надТеорема (критерий Эйзенштейна)Если для многочлена an xn + .

. . + a1 x + a0 с целымикоэффициентами существует такое простое p, что (1) p - an ,p | ai при i = 0, 1, . . . , n 1 и (2) p2 - a0 , то этот многочленнеприводим.19 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКритерий Эйзенштейна � достаточное условиенеприводимости многочленов надТеорема (критерий Эйзенштейна)Если для многочлена an xn + . . . + a1 x + a0 с целымикоэффициентами существует такое простое p, что (1) p - an ,p | ai при i = 0, 1, .

. . , n 1 и (2) p2 - a0 , то этот многочленнеприводим.Пример2x4 6x3 + 15x2 + 21 неприводим по критерию Эйзенштейна(p = 3).19 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа19 / 432Критерий Эйзенштейна � достаточное условиенеприводимости многочленов надТеорема (критерий Эйзенштейна)Если для многочлена an xn + . . . + a1 x + a0 с целымикоэффициентами существует такое простое p, что (1) p - an ,p | ai при i = 0, 1, .

. . , n 1 и (2) p2 - a0 , то этот многочленнеприводим.Пример2x4 6x3 + 15x2 + 21 неприводим по критерию Эйзенштейна(p = 3).Пример (существование надмногочленов любой степени)неприводимыхМногочлен xn 2 для всякого n > 0 неприводим надкритерию Эйзенштейна для p = 2.поПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены надслучай20 / 432p� основной для насПример (p = 2)Дано: поле 2 = h {0, 1}, +mod 2 , ·mod 2 i.Требуется: найти все неприводимые многочлены степеней 2, 3,4 над ним.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены надслучай20 / 432p� основной для насПример (p = 2)Дано: поле 2 = h {0, 1}, +mod 2 , ·mod 2 i.Требуется: найти все неприводимые многочлены степеней 2, 3,4 над ним.Вторая степень: x2 + ax + bЯсно, что b = 1, иначе x2 + ax = x(x + a).Ищем неприводимый многочлен в виде x2 + ax + 1.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены надслучай20 / 432p� основной для насПример (p = 2)Дано: поле 2 = h {0, 1}, +mod 2 , ·mod 2 i.Требуется: найти все неприводимые многочлены степеней 2, 3,4 над ним.Вторая степень: x2 + ax + bЯсно, что b = 1, иначе x2 + ax = x(x + a).Ищем неприводимый многочлен в виде x2 + ax + 1.Если a = 0, то x2 + 1 = (x + 1)2 .При a = 1 получаем неприводимый многочлен.) над 2 существует единственный неприводимый многочленстепени 2: x2 + x + 1.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над21 / 432p ...Третья степень: x3 + ax2 + bx + 1(почему свободный член не равен нулю?)Исключая, как сделано ранее, делимость на x + 1, получаемусловие a + b 6= 0, т.е.a = 0, b = 1 ,a = 1, b = 0 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над21 / 432p ...Третья степень: x3 + ax2 + bx + 1(почему свободный член не равен нулю?)Исключая, как сделано ранее, делимость на x + 1, получаемусловие a + b 6= 0, т.е.a = 0, b = 1 ,a = 1, b = 0 .) надэто2существует два неприводимых многочлена степени 3:x3 + x2 + 1 и x3 + x + 1 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над22 / 432p ...Четвёртая степень: x4 + ax3 + bx2 + cx + 1Исключение делимости на x + 1 приводит к условию a + b + c = 1,т.е.

имеется 4 варианта, которые дают 3 решения:a0011b0101c1001многочленx4 + x + 1x4 + x2 + 1x4 + x3 + 1x4 + x3 + x2 + x + 1� приводимыйПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над22 / 432p ...Четвёртая степень: x4 + ax3 + bx2 + cx + 1Исключение делимости на x + 1 приводит к условию a + b + c = 1,т.е. имеется 4 варианта, которые дают 3 решения:a0011b0101c1001многочленx4 + x + 1x4 + x2 + 1x4 + x3 + 1x4 + x3 + x2 + x + 1� приводимыйОткуда взялся ещё один приводимый многочлен?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над22 / 432p ...Четвёртая степень: x4 + ax3 + bx2 + cx + 1Исключение делимости на x + 1 приводит к условию a + b + c = 1,т.е.

имеется 4 варианта, которые дают 3 решения:a0011b0101c1001многочленx4 + x + 1x4 + x2 + 1x4 + x3 + 1x4 + x3 + x2 + x + 1� приводимыйОткуда взялся ещё один приводимый многочлен?Найдены многочлены, у которых нет линейных делителей(степени 1). Но многочлен 4-й степени может разлагаться впроизведение двух неприводимых многочленов 2-й степени:x4 + x2 + 1 = (x2 + x + 1)2 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над 3⌦↵Поле 3 = {0, 1, 2}, +3 , ·3 ) кольцо многочленов23 / 4323 [x].Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа23 / 432Неприводимые многочлены над 3⌦↵Поле 3 = {0, 1, 2}, +3 , ·3 ) кольцо многочленовМногочлены порядка 1:x2xx+12x + 1x+22x + 2Какие из них неприводимы?3 [x].Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа23 / 432Неприводимые многочлены над 3⌦↵Поле 3 = {0, 1, 2}, +3 , ·3 ) кольцо многочленовМногочлены порядка 1:x2xx+12x + 1x+22x + 2Какие из них неприводимы? Все!3 [x].Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа23 / 432Неприводимые многочлены над 3⌦↵Поле 3 = {0, 1, 2}, +3 , ·3 ) кольцо многочленовМногочлены порядка 1:x3 [x].2xx+12x + 1x+22x + 2Какие из них неприводимы? Все!Неприводимые многочлены порядка 2 в3 [x]:x2 + 12x2 + 2x2 + x + 22x2 + x + 1x2 + 2x + 22x2 + 2x + 1Запомним, что многочлен x2 + 1 � неприводим над3.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 432Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.pсуществуетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 432Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.� докажем позже.pсуществуетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 432Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.� докажем позже.ВопросКак вp [x]найти неприводимый многочлен?pсуществуетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 432Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.� докажем позже.ВопросКак вp [x]найти неприводимый многочлен?Ответ: нет эффективных алгоритмовpсуществуетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 432Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.pсуществует� докажем позже.ВопросКак вp [x]найти неприводимый многочлен?Ответ: нет эффективных алгоритмов(из таблиц, алгоритм из 5-й главы �Алгебры� Ван дерВардена, алгоритм Берлекемпа...)Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 432Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.pсуществует� докажем позже.ВопросКак вp [x]найти неприводимый многочлен?Ответ: нет эффективных алгоритмов(из таблиц, алгоритм из 5-й главы �Алгебры� Ван дерВардена, алгоритм Берлекемпа...)Если многочлен не имеет корней, это ещё не значит,что он неприводим.

Характеристики

Список файлов лекций