Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
многочлена f М-
Итак, применяя этот алгоритм отыскания корней многочлена / (х), мы должны
поступать следующим образом. Сначала построим многочлены /й (я) по
формуле (4.29) и многочлен F (х) ?
( fp fx] по формуле (4.30). Затем, применяя алгоритм разложения'из § 2,
находим каноническое разложение (4.31) многочлена F (х) в кольце |ГР [х];
это приводит к частичному разложению (4.32) многочлена /(х). Если это
разложение оказывается тривиальным, мы находим многочлены НОД (/ (х), /й
(х)) для всех k, i < k < min. Если и это не приводит к нетривиальному
разложению многочлена / (х), мы заменяем многочлен / (х) многочленом J
(х) из формул (4.34) или (4.33) в соответствии с тем, является / (х)
двучленом или нет. Как показано выше, применение того же алгоритма к f
(х) уже обязательно приводит к нетривиальному разложению многочлена f
(х), а следовательно, и многочлена / (х). Как только нетривиальные
делители многочлена / (х) найдены, процедура повторяется с заменой
многочлена / (х) полученными его нетривиальными делителями, и так
продолжается до полного разложения многочлена / (х) на линейные
сомножители, которые, согласно теореме 1.64, и определяют корни этого
многочлена,
Комментарии
§ 1. Алгоритм разложения, основанный на матрице В (алгоритм Берлекэмпа),
был впервые изложен в статье Berlekamp [3] и воспроизведен в книге
Berlekamp [4, ch. 6]. Возможность использования матрицы В из этого
алгоритма для определения числа нормированных неприводимых сомножителей
многочлена / была замечена еще раньше. В статье Petr [13 показано, что
если все неприводимые сомножители многочлена / различны (т. е. в
разложении (4.1) ех - ... - ек = 1), то характеристический многочлен det
(х/ - В) матрицы В равен произведению двучле-
нов ¦ - 1) ... (/* _ 1), где п, = deg (/,), / = 1, ..., к. Общий
случай был исследован Шварцом, показавшим в статье Schwarz [ 1 ],
k
что det (х/ - В) = хт (х"1 - 1) ... (хПк - 1), где т = ? nt (et - 1);
i=i
см. также Schwarz [11]. Результат, состоящий в том, что ранг матрицы В -
/ равен п - k, установлен Батлером (Butler у]); другое его доказательство
дано Шварцом (Schwarz [11]). В статье Willett [5] число k
интерпретируется как размерность
224
Гл, 4. Разложение многочленов на множители
векторного пространства линейных рекуррентных последова иостей (см. гл,
8). Алгоритм Берлекэмпа излагается в следу работах: Childs [], part II,
ch. 12], Collins [3], Knuth [3, ch. Lidl, Pilz [1, ch. 73, Mignotte [33 и
Zimmer [2, ch. 23.
Алгоритмы, основанные на многочленах (см. теорему и Ri (см. теорему 4.5),
построены Макэлайсом (McEliece В его же работе McEleice [3] приводятся
таблицы разложу двучленов хп - 1, полученные применением этих алгори
Изложение этих н других алгоритмов разложения можно щ также в работах
Collins [3], Knuth [3, ch. 4], Lidl, Wiesenb [1, ch. 2], Mignotte [31 и
Zimmer [2, ch. 2].
Матрицу В можно также использовать для определения чщ ud различных
нормированных неприводимых делителей степе (I < d п) многочлена /. Шварц
(Schwarz [113) показал, числа od удовлетворяют следующей системе линейных
у равнее
>MVs> •.
п
S НОД (/, d) ad
d-1
П
hj, /=1,2,
i > i
•Is 2',
где hj - ранг матрицы В/ - /. Частные случаи такой си* рассматривались
раньше в статьях Redei [9 3 и Schwarz [41, | С помощью этой системы в
статье Gimji, Arnon [13 был постр алгоритм для определения чисел od. В
статье Schwarz [13 числа od получено следующее сравнение по модулю ха
стики р поля fQ:
dod = S р (d/i) Tr (BO (mod p),
i I d
Щ
к.Щ
•
¦:.w
•• \'Ух
где ц - функция Мёбиуса, Tr (В ) - след матрицы Ва су распространяется на
все положительные делители t чис-Щ Частный случай этого сравнения для d =
1 был получен в статье Schwarz [33. В этой последней статье содержатся и
дру сравнения но модулю р для чисел crd, выраженные с номО п х n-матрицы
А - (аи)> где = s^j и sr обозначает r-х степеней корней многочлена /. В
статье Schwarz [14 3 были лучены формулы, выражающие числа ud через ранги
матр^ связанных с матрицей А. В работе Horakova, Schwarz [1] при дятся
формулы, выражающие числа od через ранги циркулянтн матриц, образованных
коэффициентами многочлена /; по э поводу см. также Ward [10]. Связи между
свойствами члена / и соответствующей ему матрицы В были исследованы таж в
работах Ghen, Li [1 3 и T'u [1 ], Упомянем еще об нспользо нин матрицы В
в общем алгоритме разложения Кемпферта (Ке fert [ 13) ив полученных
Симсом (Sims [ 13) условиях, при кото коммутативная конечномерная алгебра
над конечным поле*$ является полем.
Комментарии
225
Отметим следующий полезный результат о числе неприводимых сомножителей
многочлена. Пусть над полем fq нечетной характеристики задан многочлен /
степени п > 2 с дискриминантом о ф 0 (см. определение 1.92) и k - число
его нормированных неприводимых сомножителей; тогда ц (D) =- (-1Г\ где г)
- квадратичный характер поля Fq (см. пример 5.10). Впервые это показал
(для простых полей) Пелле (Pellet [2]), а затем в общем виде доказал
