Лекции по прикладной алгебре. v1.1 (1127111), страница 2
Текст из файла (страница 2)
ϕ(n) — мультпликативная функция);dв общем случае ϕ(m · n) = ϕ(m) · ϕ(n) · ϕ(d),где d = НОД(m, n).11 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаФункция Эйлераϕ(n) — функция Эйлера т.е. количество чисел ряда изинтервала [ 1, . . . , n − 1 ], взаимно простых с n:ϕ(1) = 1 (по определению), ϕ(2) = 1, ϕ(3) = ϕ(4) = 2,ϕ(5) = 4, ϕ(6) = |{1, 5}| = 2, . .
.Свойства:ϕ(n) 6 n − 1 и ϕ(p) = p − 1, если p — простое;ϕ(nm ) = nm−1 ϕ(n), т.е. ϕ(pm ) = pm−1 (p − 1), если p —простое;если m и n взаимно просты, то ϕ(m · n) = ϕ(m) · ϕ(n)(т.е. ϕ(n) — мультпликативная функция);dв общем случае ϕ(m · n) = ϕ(m) · ϕ(n) · ϕ(d),где d = НОД(m, n).Примерϕ(15) = ϕ(3 · 5) = ϕ(3) · ϕ(5) = (3 − 1)(5 − 1) = 8.11 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКак найти примитивные элементы поля12 / 160Fp ?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКак найти примитивные элементы поляЕсли примарное разложение (p − 1) —12 / 160Fp ?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКак найти примитивные элементы поля12 / 160Fp ?Если примарное разложение (p − 1) —известно — элемент α ∈ Fp будет примитивным iffαp−1q6≡p 1 для каждого q | (p − 1).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКак найти примитивные элементы поля12 / 160Fp ?Если примарное разложение (p − 1) —известно — элемент α ∈ Fp будет примитивным iffp−1α q 6≡p 1 для каждого q | (p − 1).неизвестно — эффективного алгоритма нахожденияпримитивного элемента не найдено (используютвероятностные алгоритмы).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКак найти примитивные элементы поля12 / 160Fp ?Если примарное разложение (p − 1) —известно — элемент α ∈ Fp будет примитивным iffp−1α q 6≡p 1 для каждого q | (p − 1).неизвестно — эффективного алгоритма нахожденияпримитивного элемента не найдено (используютвероятностные алгоритмы).Если найден один примитивный элемент, остальные находятсявозведением его в степени, взаимно простые с числом p − 1 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочленыУтверждениеКольцо многочленов k[x] над полем k — евклидово.ТеоремаКаждый элемент евклидова кольца однозначно с точностью доперестановок разлагается в произведение простых элементов.
иделителей единицы.Простые (неразложимые) элементы k[x] — неприводимыемногочлены.Вопросы для полей12C, R, Q и Fp :какие многочлены над ними неприводимы?как находить неприводимые многочлены?13 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаСвойства корней многочленовУтверждениеОстаток от деления многочлена f на многочлен первой степени(x − a) равен f (a). В частности, f делится на (x − a) iff aявляется корнем f , т. е.
f (a) = 0.14 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаСвойства корней многочленовУтверждениеОстаток от деления многочлена 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.14 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа15 / 160Основная теорема алгебрыЛеммаМногочлен степени n имеет не более n корней. Если двамногочлена степени не выше n как функции различны, то ихзначения совпадают не более чем в n точках.⇒ Указанные многочлены «сильно отличаются один отдругого».Это свойство многочленов лежит в основе многих ихприменений в комбинаторике и в теоретической информатике.Теорема (основная теорема алгебры)Всякий многочлен положительной степени над полемкорень.C имеетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены надНеприводимые многочлены:16 / 160C, R и QПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над16 / 160C, R и QНеприводимые многочлены:в полеC— только многочлены 1-й степени;Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над16 / 160C, R и QНеприводимые многочлены:в полев полеCR— только многочлены 1-й степени;—1 многочлены 1-й степени,2 многочлены 2-й степени с отрицательнымдискриминантом;Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над16 / 160C, R и QНеприводимые многочлены:в полев полеCRв полеQ— только многочлены 1-й степени;—1 многочлены 1-й степени,2 многочлены 2-й степени с отрицательнымдискриминантом;— существуют неприводимые многочленыпроизвольной степени (надо показать).Вопрос о приводимости многочлена сводится квопросу о разложении на множители многочлена сцелыми коэффициентами.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКритерий Эйзенштейна — достаточное условиенеприводимости многочленов над QТеорема (критерий Эйзенштейна)Если для многочлена an xn + .
. . + a1 x + a0 с целымикоэффициентами существует такое простое p, что (1) p - an ,p | ai при i = 0, 1, . . . , n − 1 и (2) p2 - a0 , то этот многочленнеприводим.17 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКритерий Эйзенштейна — достаточное условиенеприводимости многочленов над 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).17 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа17 / 160Критерий Эйзенштейна — достаточное условиенеприводимости многочленов над 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 поПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены надслучай18 / 160Fp— основной для насПример (p = 2)Дано: поле F2 = h{0, 1}, +mod 2 , ·mod 2 i.Требуется: найти все неприводимые многочлены степеней 2, 3,4 над ним.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены надслучай18 / 160Fp— основной для насПример (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.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены надслучай18 / 160Fp— основной для насПример (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.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над19 / 160Fp ...Третья степень: x3 + ax2 + bx + 1 (почему свободный членне равен нулю?)Исключаем (как сделано ранее) делимость на x + 1 —получаем условие a + b 6= 0, т.е.a = 0, b = 1 ,a = 1, b = 0 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над19 / 160Fp ...Третья степень: 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 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над20 / 160Fp ...Четвёртая степень: x4 + ax3 + bx2 + cx + 1Исключение делимости на x + 1 приводит к условию a + b + c = 1,т.е.
имеется 4 варианта, которые дают 3 решения:a b0 00 11 01 1Откудаc многочлен1 x4 + x + 10 x4 + x2 + 1— приводимый0 x4 + x3 + 11 x4 + x3 + x2 + x + 1взялся ещё один приводимый многочлен?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над20 / 160Fp ...Четвёртая степень: x4 + ax3 + bx2 + cx + 1Исключение делимости на x + 1 приводит к условию a + b + c = 1,т.е.
имеется 4 варианта, которые дают 3 решения:a b c многочлен0 0 1 x4 + x + 10 1 0 x4 + x2 + 1— приводимый1 0 0 x4 + x3 + 11 1 1 x4 + x3 + x2 + x + 1Откуда взялся ещё один приводимый многочлен?Найдены многочлены, у которых нет линейных делителей (степени1). Но многочлен 4-й степени может разлагаться в произведениедвух неприводимых многочленов 2-й степени:x4 + x2 + 1 = (x2 + x + 1)2 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены надПолеF321 / 160F3= h {0, 1, 2}, +3 , ·3 i ⇒ кольцо многочленовF3 [x].Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над21 / 160F3Поле F3 = h {0, 1, 2}, +3 , ·3 i ⇒ кольцо многочленовМногочлены порядка 1:x2xx+12x + 1x+22x + 2Какие из них неприводимы?F3 [x].Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над21 / 160F3Поле F3 = h {0, 1, 2}, +3 , ·3 i ⇒ кольцо многочленовМногочлены порядка 1:x2xx+12x + 1x+22x + 2Какие из них неприводимы? Все!F3 [x].Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаНеприводимые многочлены над21 / 160F3Поле F3 = h {0, 1, 2}, +3 , ·3 i ⇒ кольцо многочленовМногочлены порядка 1:x2xx+12x + 1x+22x + 2Какие из них неприводимы? Все!Неприводимые многочлены порядка 2 вF3 [x]:x2 + 12x2 + 2x2 + x + 22x2 + x + 1x2 + 2x + 22x2 + 2x + 1F3 [x].Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа22 / 160Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.Fp существуетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа22 / 160Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.— докажем позже.Fp существуетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа22 / 160Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.— докажем позже.ВопросКак вFp [x] найти неприводимый многочлен?Fp существуетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа22 / 160Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.— докажем позже.ВопросКак вFp [x] найти неприводимый многочлен?Ответ: нет эффективных алгоритмовFp существуетПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа22 / 160Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.Fp существует— докажем позже.ВопросКак вFp [x] найти неприводимый многочлен?Ответ: нет эффективных алгоритмов(из таблиц, алгоритм из 5-й главы «Алгебры» Ван дерВардена, алгоритм Берлекемпа...)Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа22 / 160Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.Fp существует— докажем позже.ВопросКак вFp [x] найти неприводимый многочлен?Ответ: нет эффективных алгоритмов(из таблиц, алгоритм из 5-й главы «Алгебры» Ван дерВардена, алгоритм Берлекемпа...)Если многочлен не имеет корней, это ещё не значит,что он неприводим.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа23 / 160Построение конечных полей— с использованием неприводимых многочленов.1Выбираем простое p и фиксируем полеFp = h{ 0̄, 1̄, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
