Лекции по прикладной алгебре. v2.0 (1127112), страница 2

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

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

. , n − 1 ], взаимно простых с n:ϕ(1) = 1 (по определению), ϕ(2) = 1, ϕ(3) = ϕ(4) = 2,ϕ(5) = 4, ϕ(6) = {1, 5} = 2, . . .Свойства (p — простое число)ϕ(n) 6 n − 1 и ϕ(p) = p − 1;ϕ(nm ) = nm−1 ϕ(n), т.е. ϕ(pm ) = pm−1 (p − 1);dϕ(mn) = ϕ(m)ϕ(n) ϕ(d), где d = НОД(m, n),откуда: если m и n взаимно просты, тоϕ(mn) = ϕ(m)ϕ(n) (ϕ(·) — мультпликативная функция).12 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаФункция Эйлераϕ(n) — функция Эйлера — количество чисел из интервала[ 1, .

. . , n − 1 ], взаимно простых с n:ϕ(1) = 1 (по определению), ϕ(2) = 1, ϕ(3) = ϕ(4) = 2,ϕ(5) = 4, ϕ(6) = {1, 5} = 2, . . .Свойства (p — простое число)ϕ(n) 6 n − 1 и ϕ(p) = p − 1;ϕ(nm ) = nm−1 ϕ(n), т.е. ϕ(pm ) = pm−1 (p − 1);dϕ(mn) = ϕ(m)ϕ(n) ϕ(d), где d = НОД(m, n),откуда: если m и n взаимно просты, тоϕ(mn) = ϕ(m)ϕ(n) (ϕ(·) — мультпликативная функция).Пример:ϕ(15) = ϕ(3 · 5) = ϕ(3)ϕ(5) = (3 − 1)(5 − 1) = 8,ϕ(16) = ϕ(24 ) = 23 ϕ(2) = 8.12 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПервые 99 значений функции Эйлера и степенипримитивного элемента13 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа13 / 432Первые 99 значений функции Эйлера и степенипримитивного элементаДля примитивного элемента α мультипликативной группыF∗p :αp−1 = 1 ⇒ αp = α1 = α и α−1 = α−1 · αp−1 = αp−2 .Например, вF5 :α−1 6= α4 ,Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа13 / 432Первые 99 значений функции Эйлера и степенипримитивного элементаДля примитивного элемента α мультипликативной группыF∗p :αp−1 = 1 ⇒ αp = α1 = α и α−1 = α−1 · αp−1 = αp−2 .Например, вF5 :α−1 6= α4 , α−1 = α3 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКак найти примитивные элементы поля14 / 432Fp ?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКак найти примитивные элементы поляЕсли примарное разложение (p − 1) —14 / 432Fp ?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКак найти примитивные элементы поля14 / 432Fp ?Если примарное разложение (p − 1) —известно — элемент α ∈ Fp будет примитивным iffαp−1q6≡p 1 для каждого q | (p − 1).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКак найти примитивные элементы поля14 / 432Fp ?Если примарное разложение (p − 1) —известно — элемент α ∈ Fp будет примитивным iffαp−1q6≡p 1 для каждого q | (p − 1).неизвестно — эффективного алгоритма нахожденияпримитивного элемента не найдено (используютвероятностные алгоритмы).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКак найти примитивные элементы поля14 / 432Fp ?Если примарное разложение (p − 1) —известно — элемент α ∈ Fp будет примитивным iffαp−1q6≡p 1 для каждого q | (p − 1).неизвестно — эффективного алгоритма нахожденияпримитивного элемента не найдено (используютвероятностные алгоритмы).Если α — примитивный элемент поля Fp , то любой другой егопримитивный элемент может быть получен как степень αk , гдеk — целое число, взаимно простое с p − 1.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочленыУтверждениеКольцо многочленов k[x] над полем k — евклидово.ТеоремаКаждый элемент евклидова кольца однозначно с точностью доперестановок разлагается в произведение простых элементов.

иделителей единицы.Простые (неразложимые) элементы k[x] — неприводимыемногочлены.Вопросы для полей12C, R, Q и Fp :какие многочлены над ними неприводимы?как находить неприводимые многочлены?15 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаСвойства корней многочленовУтверждениеОстаток от деления многочлена 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 точках.⇒ указанные многочлены «сильно отличаются один отдругого».Это свойство многочленов лежит в основе многих ихприменений в комбинаторике и в теоретической информатике.Теорема (основная теорема алгебры)Всякий многочлен положительной степени над полемкорень.C имеетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены надНеприводимые многочлены:18 / 432C, R и QПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над18 / 432C, R и QНеприводимые многочлены:в полеC— только многочлены 1-й степени;Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над18 / 432C, R и QНеприводимые многочлены:Cв поле Rв поле— только многочлены 1-й степени;—12многочлены 1-й степени,многочлены 2-й степени с отрицательнымдискриминантом;Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над18 / 432C, R и QНеприводимые многочлены:Cв поле Rв поле— только многочлены 1-й степени;—12в полеQмногочлены 1-й степени,многочлены 2-й степени с отрицательнымдискриминантом;— существуют неприводимые многочленыпроизвольной степени (надо показать).Вопрос о приводимости многочлена сводится квопросу о разложении на множители многочлена сцелыми коэффициентами.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКритерий Эйзенштейна — достаточное условиенеприводимости многочленов над QТеорема (критерий Эйзенштейна)Если для многочлена an xn + .

. . + a1 x + a0 с целымикоэффициентами существует такое простое p, что (1) p - an ,p | ai при i = 0, 1, . . . , n − 1 и (2) p2 - a0 , то этот многочленнеприводим.19 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКритерий Эйзенштейна — достаточное условиенеприводимости многочленов над QТеорема (критерий Эйзенштейна)Если для многочлена 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Критерий Эйзенштейна — достаточное условиенеприводимости многочленов над QТеорема (критерий Эйзенштейна)Если для многочлена 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).Пример (существование над Q неприводимыхмногочленов любой степени)Многочлен xn − 2 для всякого n > 0 неприводим надкритерию Эйзенштейна для p = 2.Q поПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены надслучай20 / 432Fp— основной для насПример (p = 2)Дано: поле F2 = h {0, 1}, +mod 2 , ·mod 2 i.Требуется: найти все неприводимые многочлены степеней 2, 3,4 над ним.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены надслучай20 / 432Fp— основной для насПример (p = 2)Дано: поле F2 = 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 / 432Fp— основной для насПример (p = 2)Дано: поле F2 = 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 получаем неприводимый многочлен.∴ над F2 существует единственный неприводимый многочленстепени 2: x2 + x + 1.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над21 / 432Fp ...Третья степень: x3 + ax2 + bx + 1(почему свободный член не равен нулю?)Исключая, как сделано ранее, делимость на x + 1, получаемусловие a + b 6= 0, т.е.a = 0, b = 1 ,a = 1, b = 0 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над21 / 432Fp ...Третья степень: x3 + ax2 + bx + 1(почему свободный член не равен нулю?)Исключая, как сделано ранее, делимость на x + 1, получаемусловие a + b 6= 0, т.е.a = 0, b = 1 ,a = 1, b = 0 .∴ надэтоF2 существует два неприводимых многочлена степени 3:x3 + x2 + 1 и x3 + x + 1 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над22 / 432Fp ...Четвёртая степень: 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 / 432Fp ...Четвёртая степень: 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 / 432Fp ...Четвёртая степень: 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 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над F3Поле F3 = {0, 1, 2}, +3 , ·3 ⇒ кольцо многочленов23 / 432F3 [x].Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа23 / 432Неприводимые многочлены над F3Поле F3 = {0, 1, 2}, +3 , ·3 ⇒ кольцо многочленовМногочлены порядка 1:x2xx+12x + 1x+22x + 2Какие из них неприводимы?F3 [x].Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа23 / 432Неприводимые многочлены над F3Поле F3 = {0, 1, 2}, +3 , ·3 ⇒ кольцо многочленовМногочлены порядка 1:x2xx+12x + 1x+22x + 2Какие из них неприводимы? Все!F3 [x].Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа23 / 432Неприводимые многочлены над F3Поле F3 = {0, 1, 2}, +3 , ·3 ⇒ кольцо многочленовМногочлены порядка 1:xF3 [x].2xx+12x + 1x+22x + 2Какие из них неприводимы? Все!Неприводимые многочлены порядка 2 вF3 [x]:x2 + 12x2 + 2x2 + x + 22x2 + x + 1x2 + 2x + 22x2 + 2x + 1Запомним, что многочлен x2 + 1 — неприводим надF3 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 432Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.Fp существуетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 432Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.— докажем позже.Fp существуетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 432Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.— докажем позже.ВопросКак вFp [x] найти неприводимый многочлен?Fp существуетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 432Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.— докажем позже.ВопросКак вFp [x] найти неприводимый многочлен?Ответ: нет эффективных алгоритмовFp существуетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 432Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.Fp существует— докажем позже.ВопросКак вFp [x] найти неприводимый многочлен?Ответ: нет эффективных алгоритмов(из таблиц, алгоритм из 5-й главы «Алгебры» Ван дерВардена, алгоритм Берлекемпа...)Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 432Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.Fp существует— докажем позже.ВопросКак вFp [x] найти неприводимый многочлен?Ответ: нет эффективных алгоритмов(из таблиц, алгоритм из 5-й главы «Алгебры» Ван дерВардена, алгоритм Берлекемпа...)Если многочлен не имеет корней, это ещё не значит,что он неприводим.

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

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