Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 52
Текст из файла (страница 52)
г[ . и) многочлена 1. Шварц (БсЬзнагх [11!) показал, числа о„удовлетворяют следующей системе линейных уравне ~ НОД (1, г[) о„= и — !гт, 1' = — 1, 2, ..., и, л=! где Лз — ранг матрицы  — У. Частные случаи такой си ! рассматривались раньше в статьях )[еде! [9! и БсЬтчагх [41, 1 С помощью этой системы в статье Сзцп)1, Агпоп [1 ! был постр ' алгоритм для определения чисел ол. В статье 5сЬзнагх 1131 числа оа получено следующее сравнение по модулю харак стики р поля г[о„= ~ р(г(В) Тг(В )(шог[р), ыа где р — функция Мебиуса, Тг (В') — след матрицы В', а су распространяется на все положительные делители 1 числ»,:.
Частный случай этого сравнения для г[ =- 1 был получен в статье ЯсЛчеагх ! 31. В этой последней статье содержатся и дру сравнения по модулю р для чисел о„, выраженные с помо л ~ и-матрицы А =- (аы), где а;, =- з;, и з, обозначает сум, г-х степеней корней многочлена Г. В статье БсЬчгагх [141 были лучены формулы, выражающие числа ои через ранги матр связанных с матрицей А. В работе Нога[гота, 5сЛзнагх [11 прк дятся формулы, выражающие числа оа через ранги циркулянтн ' матриц, образованных коэффициентами многочлена 7'; по это поводу см. также %агг[ [10!.
Связи между свойствами мно члена 1 и соответствующей ему матрицы В были исследованы та в работах СЛеп, [.! [11 и Т'и [1). Упомянем еще об использо нии матрицы В в общем алгоритме разложения Кемпферта (Ке !ег1 [1)) и в полученных Симсом (ЯЛпз 11 !) условиях, при кото коммутативная конечномерная алгебра над конечным полем' является полем. Комментария Отметим следующий полезный результат о числе неприводимых сомножителей многочлена. Пусть над полем [Р нечетной характеристики задан многочлен 7 степени п ) 2 с дискриминаном г! ~ 0 (см. определение !.92) и й — число его но!змированиых неприводимых сомножителей; тогда г! (0) = ( — 1)", где»)— квадратичный характер поля р» (см.
пример 5.!О). Впервые это показал (для простых полей) Пелле (РеИе! [21), а затем в общем виде доказал Штикельбергер (5!!с[»е]Ьегяег [21); в литературе этот результат известен как теорема четности Штикельбергера. Доказательство этого результата можно также найти в следующих работах: Вег!е1»агпр 14, сЬ. 6], Саг1Их [671, СЫ!»[з [1, раг! П], сЬ !51, Ра!еп [11„Непзе! [21, ].цЬе!з]»! [21, йе»[е! [61, [!О, сй. ! 11, ВсЬкагх [31, Бейте [101, Я»о!егп [5], 8»»ап [1] и Вороной [21, а один частный случай этой теоремы был рассмотрен в статье Р!с[»хоп [9]. Различные варианты теоремы четности Шгикельбергера для случая поля ]г характеристики 2 даются а работах Я!с!»е!Ьегдег [21, Саг! Их [441, Вейте [!О! и Вег!е[»агпр [4, сЬ.
61, [!О1, Еще Пелле (Ре!!е! [21) заметил, что теорему четности Штикельбергера можно применить для доказательства квадратичного закона взаимности (см. теорему 5.17); см. также работы Вег!е1»агпр [4, сЬ. 6), СЫЫз [1, раг! П[, сЬ. 161, М!г[- »папо!1, Непзе! 111, йене! [!О, сЬ. !!1 и Ваап 1!1. Мы уже встречались с разложениями многочленов из некоторых специальных классов.
Так, в $ 4 гл. 2 рассматривались круговые многочлены, в $ 4 гл. 3 — линеаризованиые и аффинные многочлены и в 9 5 гл. 3 — двучлены и трехчлены. По вопросу о числе корней многочлена (а значит, и о числе его линейных сомножителей) мы отсылаем читателя к $ ! гл. 6. Таблицы разложений миогочлеиов и списки неприводимых многочленов представлены в гл, !О, Вопрос о разложимости многочленов четвертой степени изучался в работах СагИ!з [701, [731, О!ц»Ис[, Магяай1!о [!1, [.еопаг»[ [31, [.еопагб, %И!!агпз 111, Я»о!егп [41 и Гребенюк [1). Р зложимость многочленов вида 7 (х') для неприводимых много"'енов 7 рассматривалась в статьях Адов [!О], [111, ВЫ!ег [21 и Рейс! 11!. Результаты о степенях делителей многочленов вида ~ (х) — а, полученные Оре (Оге [21), были обобщены в статьях РеИегзоп (11, [21, [3), где изучались многочлены вида 7 (й (х) ) для неприводимых многочленов 7' и им подобные композиции.
разложения многочленов вида 7 (7. (х)), где 7' — иеприводимый, ~ — линеаризованный многочлены, изучались в работах Адов [!91, [201, ].опй [31, [41, [.опд, ЧацйЬап [! 1, [21 и Варшамов [31, [5]; аналогичные вопросы для многочлеиов от нескольких [ ременных рассматривались в статьях СагИ!е, [.Опй [!1 и ! Опя В статье Рау[г!п [31 находятся степени и число неприводи- !~ за», м» Гл. 4, Разложение многонленов на множители ~П мых сомножителей многочлена вида (сх + д) х' — (ах + Ь),'*,з полем ге, В работе %[!]!агпз К. 5. 125! получено разлож так назйваемых многочленов Диксона (см. Э 2 гл.
7), а в Сергеева ] ! 1 — разложение миогочленов близкого к ним в ' Некоторые результаты о разложении многочленов Эйл Бернулли над конечным простым полем получены в статье Вг!)г' ' [! ]. В работе Сго]от[з, Бегпре! 1! ] изучалось разложение м членов, задаваемых рекуррентным соотношением второго поря Фейт и Рис (Ге[1, Кеез [! ]) получили критерий разложи ' многочлена ) ~ Г [х] на линейные сомножители над г в:,'"'' минах сумм степеней корней многочлена 7.
Более ранние р таты в этом направлении можно найти в статьях 5сйопетапп Т]зоииепо[, С]та!е!е! 1! ) н Шатуновский 1!1 В статье Сга', Сзогбаз [ ! 1 охарактеризованы такие последовательности и = О, 1, ..., что если конечное поле г является полем разл ' иия для многочлена ~ а„х", то оно является полем разложен для многочлена ~з с„а„х".
Коэн (Сойеп 5. Р, 151, [6)) изучал, как распределяются ' личные типы разложения среди многочленов вида ) (х) + при заданных ), д ~[['е [х] и изменяющемся а ~ Гр (см! этом также 1.еопагг] [51). Кроме того, Коэн (Со]теп 5. Р.: изучал также распределение типов разложения в классах выч; по модулю некоторого заданного многочлена и в множ многочленов фиксированной степени, некоторые коэффнцц'' которых заранее заданы. Вильямс (%!]][агпз К. 5. [ ! ! 1) по асимптотическую формулу для числа 7тг(7, д, з, е) нормировазг многочленов данной степени е[ над полем [['е, имеющих ро различных неприводимых нормированных делителей степе(1 над Ге. В статьях Саг 15], 171 н Со]теп 5.
Р. [3] приво асимптотические формулы для числа нормированных многочл заданной степени над Ге, имеющих определенные типы раз, ния; о случае, когда степень многочленов ограничена дан, натуральным числом, см. статью бора, ] и!]таг 1!1. В рд Ез]йшопду 12! найдено число нормированных многочленов да ' степени и над простым полем гр, имеющих заданное число личных корней в поле гр, и для каждого е[, ! ( а' ~~ п, по тано также число нормированных многочленов степени и над... не имеющих неприводимых делителей степени е[. При фактическом осуществлении какого-либо алгоритма ложения многочлена приходится выполнять различные опер в рассматриваемом конечном поле.
Например, чтобы еде„ нормированным многочлен )', требуется вычислить мультик кативный обратный элемент для старшего коэффициента Э, многочлена. Для эффективного выполнения в конечных пт„ арифметических действий были изобретены различные м Так, в работах СоИ!пз [[1, Ран!ба 111, 5с]юп]тане 1!1 н 7Иа Коммеитарии рассматривается вопрос о вычислении мультипликативных обратных элементов.
Эффективные методы умножения элементов поля разработаны в статьях РЫцсс1а, 2а!сз)е!п [11 и %!подгиб [ ! ], [2 ); см. также В!п), Сароиап! 11 ). Алгоритмы для вычисления некоторых первообразных корней из единицы представлены в работах 1 ш, йее6, Тгцопя [! ) и йее6, Тгцопя, МП!ег [11, [21. В статье РоЫ)я, Не!!гпап [! 1 построен быстрый алгоритм для вычисления показателя г в равенстве Ь' = а при заданных а, Ь~ ~ [",', где Ь вЂ” примитивный элемент поля Ко; об этом см. также работы Нег1ез1агп, ЛоЬаппеазоп [1), РоПаг6 [3) и 2)ег1ег [91, а также гл. 10, 5 1 и табл. А настоящей книги.
Обзор по арифметическим алгоритмам для конечного поля !)р дается в работе М!япоПе 13). Реализация арифметики конечнйх полей на переключатсльных схемах рассматривалась в следующих работах: Ваг)ее, 3сЬпе16ег [1], Вег!е1сагпр [4, сЬ. 2], ОП! [2, сЬ. 6], МасФППапгз, 8]оапе 12, сЛ. 31, Ре1егзоп, ЪЧе!6оп [1, сЬ. 7], )[е6!пЬо ) 11, Тапа1са, Кааанага, Техцйа, КазаЬага 111 и %П!е!! [6]; о реализации ее на ЭВМ см. Са)иге[, 1.ооз 12). Полезным вычислительным изобретением является дискретное преобразование Фурье для конечного поля го, введенное Поллардом (РоПаг6 )11).
Пусть Ь вЂ” некоторый элемент порядка 6 мультнпликативной группы поля го. Тогда конечная последовательность а„а„..., а„„элементов поля ))' может быть преобразована в конечную последовательность И-1 Аг = ~~ агЬ'г, 1 = О, 1, ..., 6 — 1. !=о Прн этом обратное преобразование задается формулой и-1 аэ — — 6 ' ~~ А;Ь 'г, 1 = О, 1, ..., 6 — 1. ~=о Эти преобразования называются дискретными преобразованиями Фурье Оба они допускают быстрое вычисление, и при этом работают методы, аналогичные применяемым в теории быстрых преобразований Фурье в обычном комплексном анализе.
Дискретное преобразование Фурье встречается в теории кодирования под "азваннем многочлена Мэттсона — Соломона (см. Ма!1зоп, Бо)огпоп н МасЪЧППагпз, Б!папе !2, сЬ. 8!). Поллард (РоПаг6 111) "~~озал, как можно использовать дискретные преобразования Фурье для выполнения арифметических действий в поле К. Дальнейшие результаты о дискретном преобразовании Фурье " его приложениях можно найти в работах Адагча!, Вцггцз [11, ,!айц! [1], Ра!ешап [1), Оо)огпЬ, Пееб, Тгцопя )1], 1.ш, Пееб, гпопЯ 111, [2), МсС!еПап, йабег 11), ИцззЬацгпег [1, сЬ. 8], !3" Гл. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
