Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 53
Текст из файла (страница 53)
Рааложение многочленов иа множители Ро!!агд 12), Ргерага!а, 5агъа!е 111, Кей!пЬо [!1, Кеец, Яс Тгцопц, Фе!сй [11, Кееб, Тгцопд 111, 12], [31, Кеей, Тв %е!сЬ [11, К!се [11 и 5агча!е [!1, [2]. Осуществление какого-либо алгоритма разложения за" также от действий с многочленамн, Эффективные методы множвния двух миогочленов над конечным полем Г предлаг ' в работах Вогой!п, Мцпго 1! ], К[се 121, 5сЬопЬайе [21 и лыго 11]; см.
также Ра!ешап [11 и Ро!!аге[ [11. О зычно ' наибольшего общего делителя и об алгоритме Евклида для М' членов от одной или нескольких переменных см. работы Адом„; [51, Вагпе!! [11, В!ап[е!пзЬ!р 1! ], Вове Ы. К. [!1, Вгони, [11, Со!!|пз [31, О!с[езоп [331. Етге, Нцзеу!п 11], Кпц)Ь.' сЬ. 4], Магоц1аз, ВагпеН [!1, МсЕ!!есе, Бйеагег [11, Мозез'.' н Чой[, Вове 1! ]. Дальнейшие результаты об арифметике м членов можно найти в статьях ВЬапц Мцг!Ьу, 5агпра1Л 111, 1а1*' Михайлюк [! ], [21 и Мурзаев 11]. Полезные сведения о п миальных операциях над конечными полями можно найти в ' дующих книгах: АЬо, Норсгой, [)!!пап [!1, Вег!е[еашр 14, с ' В!г[еЬо!1, Ваг!ее 11, сЬ.
!11, Вогое[!п, Мцпго [!1, 6![! [2, с КпцГЬ [3, сЬ. 41 н Ре!егзоп, Ъе!боп [1, сЬ. 7]). й 2. Алгоритм разложения, основанный на использо ' результантов, восходит к одному утверждению из первого, ния книги Кнута Кпц!Ь [3, сЬ. 4]. Вычисление полиномиа]! результантов методом интерполяции предложено Коллинзом !пз 121). Алгоритм Цассенхауза был описан в статье 2азз ' 151.
Алгоритм разложения с помощью диагоналнзации м ' из многочленов был предложен Берлекэмпом (Вег[е[еашр Алгоритм, основанный на теореме 4.13, взят из статьи Оо Фе!сЛ, На[ез 1! 1; см. также Акоп [8! н Кпц!Ь 13, сЛ. 41. О постном алгоритме в этой связи см. Сап!ог, ХаззепЬацз [11 В работах ХаззепЬацз [4], Кешр1ег1 [11 и Кпцрй [3, с "' рассматривается алгоритм, состонщий в последовательноМА' числении для данного многочлена 7~Р 1х! степени л': без кратных сомножителей многочленов вида Ые (х) = НОД хе' — х) для ! = 1, 2, ..., [п,'23. Если все е[, равны 1, то член 7 неприводим над полем Гр. Если же 1 4 [п~2] — нак ший индекс, для которого и! ~ 1, то многочлен 7 приводим,: [Ге и с[7 является произведением всех его непрнводимых жителей степени 7'.
Другие алгоритмы разложения можно ц„ в работах АгИп [2], Веагй [5], Саппоп [21, [3), КаЫ6;г Ананиашвили, Варшамов, Горовой, Пархоменко 11], ВарЮ Остиану [1] и Дынькин, Агаронов 11]. Сравнительное изу. эффективности различных алгоритмов разложения много%([, предпринято в статье Моепс[е [11.
Методы определения поля разложения многочлена над простым конечным полеМ, Комментарии зтриваются в статьях Бре!вег (1 ) и %едпег (4 1; случай произльного конечного поля изучается в статьях М!дпо!!е [11, 121, [41. Зффективные алгпритмы разложения многочленов над конеч„ыми простыми полями могут служить хорошим инструментом также и для разложения многочленов над кольцом У целых чисел. Здесь основной является следующая идея: сначала надо разложить данный многочлен 7 Е Е [х! по модулю надлежащим образом выбранного простого числа р, а затем отсюда получить изложение этого многочлена над кольцом У..
Берлекэмп (Вег(ейвгпр [61, (71) и Кнут (Кпн1Ь [3, сЬ. 41) предлагают с этой целью выбрать некий априорный максимум В, абсолютных величин для всех коэффициентов любых возможных делителей много. члена 7 над Е, а затем взять простое число р ) 2Ве, учитывая, что все делители многочлена 7 над кольцом Е целых чисел обязательно встретятся среди найденных делителей этого многочлена по модулю р. Относительно значений числа В, см.
работы СЬ!!бв [1, раг! П, сЬ. 13), Кпцрй [3, сЬ. 41, М!йпоНе (41, ХаввепЬацв (5] и Х!пппег (2, сЬ. 21. Цассенхауз в статьях ХаввепЬацв 15], (61, [7 ] рассматривает р-адическую процедуру, в которой, исходя из разложения многочлена 7 по модулю какого-либо меньшего простого числа р, затем с помощью одной конструктивной версии леммы Гензеля получается разложение 7 по модулю некоторой степени р', большей 2В,. Из дальнейших работ на эту тему см.
Кешр!ег! [!], 1.епв1га, 1.епв!га, 1очавх (! ) и [.!оуб [!1, [21; см. также СЬ![бв [1, раг! 11, сЬ. 131. Обзоры по методам разложения многочленов над кольцом Е целых чисел имеются в работах Сой(пв [3], Кпц!Ь (3, сЬ. 4) и 2!пппег [2, сЛ. 21. Однако следует заметить, что многочлен ~С ~1х) может быть неприводимым над полем рациональных чисел и в то же время приводимым по модулкв р для всех простых чисел р. Пример такого многочлена был указан еще Гильбертом (Н!!Ьег! (11). Особенно простой пример такого многочлена, а именно 7 (х) = х'+ 1, предложил Шварц (5сЬцагх (4]). Другие примеры имеются в работах 1.ее М.
А. (11 н Ро!уа, Бзейо 11, вес. Ч[!1, ргоЫегп !29)). Существуют также многочлены над Х, не имеющие линейных делителей над полем рациональных чисел, но имеющие хотя бы один линейный делитель по модулю р для каждого простого числа р (см., например, Навве 111, Яго!ет 13) и чап г[ег 'тЧаегдеп (11). Алгоритмы разложения для многочленов над полями алгебраических чисел были построены в статьях Бепв1га А. К.
[11 " %е!пЬегйег, Яо!ЬвсЫ!д [11. Методы разложения многочленов от нескольких переменных над полем рациональных чисел или над полями алгебраических чисел получены в работах Со!!йвв (31, Мовев [! ), Мцввег [11, Ч[гу [1], [21, Юапй Р. 5. 111, 121, Юапй, Ко!ЬвсЫ!и' (!] и %е!пЬегдег, Ко!ЬвсЬ!!д (11. 230 Гл. 4. Разложение многочленои иа множители Дальнейшие результаты о матрицах из многочленов найти в следующих источниках: А!Ьег! 13, сЬ. 31, Но[[ ' Кинге [1, сЬ. 71, Кг!зЬпагпцг!Ьу [1], Магон!аз, ВагпеН [[з Гантмахер [1, гл. 61. й 3. Методы, излагаемые в этом параграфе, развиты в р Берлекэмпа (Вег!е[еагпр 161).
Некоторые усовершенствов ' получены в статье Моепс[е [!1 для случая простого поля;., когда число р — 1 делится на большую степень двойки. Описа" в 3 4 гл. 3 алгоритм нахождения корней многочлена на рассмотрения его аффннных кратных получен в работе Вег!е]гк Кшпзеу, 50!огпоп [11; см. также монографию Вег!с[татр [4, сЬ,' Другой метод нахождения корней многочленов для конечных большой характеристики приводится в статье КаЬ!п [1]; см. т Сап!ог, ХаззепЬацз [1]. Реализация этих алгоритмов на рассматривается в статье Са!гпе[, Еооз [2!. В статьях Ргау,::; гпег [!1 и Мапп [61 изучается теоретический вопрос о раз '' мости в радикалах полиномиального уравнения над Г . В п ней из этих работ приводится также выражение для корней пРиводимого над полем Ге многочлена 7, степень котоРогхе делится на характеристику этого поля, через корни из едн над Ге и многочлены от коэффициентов 7'.
В статье Ргез[с' для мйогочлена 7' с корнями в поле Г» указывается в ' сложная формула, выражающая эти корнй через примитн элемент поля Г . В статье Кадое [41 приводится явное выра для многочлена НОД (7'(х), хл ' — 1), где р — простое чй Особые приемы были развиты для нахождения корней членов небольшой степени. Даже задача определения ко ' квадратного уравнения х' — аг:Гр 1х1, где р — простое ч ' становится нетривиальной, если чйсло р велико. Некоторывт годы встречаются еще у Гаусса (Оацзз 11, сЬ.
61); см. т Аб!етап, Мапдегз, МВ!ег 1! 1, СЬапя [ 11, С!ро!!а [11, !21, гпег О. Н. [101, Рос[4!!пд!оп 111, 6сЬопЬе!гп [!1, ЗЬап[ез 5тВЬ Н. Л. 5. [! ], Тагпаг[е!пе, Рг!ебшапп [11, Топей 11],, репз[еу, Неаз[е! [1, сЬ. 101 и Ъ'апб[тег 12]. Методы отыскания ней квадратных многочленов над конечными полями харак стики 2 приводятся в работах Вег!ейагпр 14, сЬ. 6] и Вег[е[са Кшпзеу, Яо!ошоп [11. О многочленах третьей и четвертой с см. следующие работы: Агпоцх [1, сЬ.
91, Агте!п [!1, СаНЫ [ СацсЬу [31, Согбопе [!1, Р!с[сноп [311, ЕзсоН [1], Н!гз 15, сЬ. '!1, М!япоз! [!1, М!гппапоН [11, 01!гатаге 111, 8 [!1, [21, [3], [41, [51, Ясагр[з [!1, Бенге [!О1, %!!!!агпз, Е 111, Гребенюк 121, Иванов [! ] и Матвеева [11. О многоч пятой степени см. работы Агте!п [2] и Горбов и Шмидт 111., бые методы вычисления корней для многочленов малой сте, возникают также в связи с алгоритмами декодирования в в 23! Упражнения браической теории кодирования; см., например, статьи СЫеп, Сцпп!па)загп 11], Ро!(с!пй)»огп [1] и Блох (1]. Точные формулы ,пя корней двучленов над простыми конечными полями можно найти в работах С!ро1!а [4], Ис(сноп [40, с(т.
7], Риге)п!гп с[с А)п!е(с(а 11], 1.[пг(йгеп (1] и Ясогза (1]. Эффективный алгоритм длн нахождения корней двучленов над простым конечным полем развит в статье Ас(1егпап, Мапс[егз, М1!1ег (1]; относительно случая произвольного конечного поля см. М!йпо11е [5]. В статье ~"!1!!ап!з Н. С. 11] рассматривается случай двучленов простой степени над простым полем (р„. Условия, при которых все корни многочлена из кольца г (х 1 принадлежат полю Г», найдены в работе РеИ, Гтеез [1]. Частный случай, когда число д простое, рассматривался в следующих работах: Яс)»опегпапп [2], ТЬопчепо1, СЬа1е!е1 (!] и Шатуновский (1).
В статье М1йпо11е [4] представлен быстрый алгоритм, с помощью которого можно проверить, все ли корни многочлена /Е (-]» (х] принадлежат полю г . В работах С»ро1!а [5] и М(апов( [2] приводятся формулы для корней многочлена / ~ Г [х] в случае, когда все эти корни принадлежат полю Р . Редеи (нег(е[ ! ! 1, с!ь 5]) Указал многочлены вида / (х) = х»+ а„х" + аь тха-' + а»~Г (х], где й.< (д + 1)/2, у которых все корни принадлежат полю г»; см. также статью Кес[е) [7] о более ранних результатах в этом йаправлении. В статье Сгегз[, Вг1ПЬаг1 [1] изучены условия, при которых многочлен / ~У (х] разлагается на различные линейные сомножители по модулю р, для многих простых чисел р; близкий пример приводится встатье 1иЬе!з)с! [3]. За результатами о числе корней многочлена в заданном конечном поле мы отсылаем читателя к 2 1 гл.
6 и комментариям к этому параграфу. !Григорьев (!е], Ленстра ([.епз(га (2» ]) и Ван дер Газен и Калтофен (чап с[ег сха1)»еп, Ка!(о[еп [1" ]) построили алгоритмы разложения на множители многочленов степени и от г переменных над произвольным конечным полем г». При этом в работах !!»рных двух авторов строится детерминированный алгоритм, имеюитий сложность, ограниченную многочленом от и' и д, а в последней работе — вероятностный алгоритм, имеющий сложность, ограниченную многочленом от п' и 1п с/. Г]о тематике четвертой главы имеются также следующие ра"сты: Са!гпе1, 1.ооз (1*], 1епз1га [1'], Згпее1з [!" ], Кюрегян и Мурзаев [2» ]. — Перев. ] Упражнения 4 !.
разложить миогочлен х'х+ хг+ хь+ х»+ ха+ хз+ ! над полем х»'а с и помощью алгоритма Берлензмпа. с по 4 2. Разложить многочлен х'+ х»+ хь — ха+ хз — х — ! иад полем га помощью алгоритма Берлеиампа. 232 Гл. 4. Разложение многочленов па множители 4.3. ПУсть Г, =- Ке (О); Разложить многочлен ха -~- 0х' + ха + (1 -[ 0) х ) 0- 0 нзд полем К, с помощью алгоритма Бсрлекэмпа. 4.4. Применить алгоритм Берлекэмпа дчя доказательства неприводиз, многочлена х' — х' — х — 1 в кольце Кз [х [.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
