Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
[41-
Эффективные алгоритмы разложения многочленов над конечными простыми
полями могут служить хорошим инструментом также и для разложения
многочленов над кольцом Z целых чисел. Здесь основной является следующая
идея: сначала надо разложить данный многочлен / ?/ [х\ по модулю
надлежащим образом выбранного простого числа р, а затем отсюда получить
разложение этого многочлена над кольцом Z. Берлекэмп (Berlekamp 16], [7])
и Кнут (Knuth [3, ch. 4]) предлагают с этой целью выбрать некий априорный
максимум В0 абсолютных величин для всех коэффициентов любых возможных
делителей многочлена / над Z, а затем взять простое число р > 2Д0,
учитывая, что все делители многочлена / над кольцом Z целых чисел
обязательно встретятся среди найденных делителей этого многочлена по
модулю р. Относительно значений числа В0 см. работы Childs [I, part II,
ch. 13], Knuth [3, ch. 4], Mignotte [4], Zassenhaus
[5] и Zimmer [2, ch. 2]. Цассенхауз в статьях Zassenhaus [5],
[6], [7] рассматривает р-адическую процедуру, в которой, исходя из
разложения многочлена / по модулю какого-либо меньшего простого числа р,
затем с помощью одной конструктивной версии леммы Гензеля получается
разложение f по модулю некоторой степени рк, большей 2?0. Из дальнейших
работ на эту тему см, Kempfert [I], Lenstra, Lenstra, Lovasz [I] и Lloyd
11J, [2]; cm. также Childs [I, part П, ch. 13]. Обзоры по методам
разложения многочленов иад кольцом Z целых чисел имеются в работах
Collins [3], Knuth [3, ch. 4] и Zimmer [2, ch. 2]. Однако следует
заметить, что многочленZ[x] может быть неприводимым над полем
рациональных чисел н в то же время приводимым по модулю р для всех
простых чисел р. Пример такого многочлена был указан еще Гильбертом
(Hilbert Ш). Особенно простой пример такого многочлена, а именно / (х) =
х4 + К предложил Шварц (Schwarz [4]). Другие примеры имеются в работах
Lee М. А. [ 1 ] и Polya, Szego [I, sec. VIII, problem 129]). Существуют
также многочлены над Z, не имеющие линейных делителей иад полем
рациональных чисел, но имеющие хотя бы один линейный делитель по модулю р
для каждого простого числа р (см., например, Hasse 111, Skolem [3] и van
der Waerden [1]).
Алгоритмы разложения для многочленов над полями алгебраических чисел были
построены в статьях Lenstra А. К- И] н Weinberger, Rothschild [1]. Методы
разложения многочленов °г нескольких переменных над полем рациональных
чисел или над полями алгебраических чисел получены в работах Collins [3],
"oses [ I ], Musser fl], Viry [I], [23, Wang P. S. [I], [2], Wang,
Rothschild [1] и Weinberger, Rothschild [1].
230
Гл. 4. Разложение многочленов на множители
Дальнейшие результаты о матрицах из многочленов найти в следующих
источниках: Albert [3, ch. 3], Hoff^ Ktmze [I, ch. 7], Krishnamurthy [1],
Maroulas, Barnett [|J Гантмахер [1, гл. 6].
§ 3. Методы, излагаемые в этом параграфе, развиты в Берлекэмпа (Berlekamp
[6 ]). Некоторые усовершенствой^ получены в статье Моепск [! ] для случая
простого полЩ когда число р - 1 делится на большую степень двойки. Описа#
в § 4 гл. 3 алгоритм нахождения корней многочлена на осЦ рассмотрения его
аффинных кратных получен в работе Berletf Rumsey, Solomon [ 11; см. также
монографию Berlekamp [4, ch. Другой метод нахождения корней многочленов
для конечных щ большой характеристики приводится в статье Rabin [! ]; см.
1ST Canton Zassenhaus [1]. Реализация этих алгоритмов иа рассматривается
в статье Calmet, Loos [2]. В статьях Fray, mer [!] и Mann [6] изучается
теоретический вопрос о разЩ" мости в радикалах полиномиального уравнения
над Fr В nolf ней из этих работ приводится также выражение для корие^Ц.
приводимого над полем F? многочлена /, степень которой делится иа
характеристику этого поля, через корни из еди#
* >Л
над F? и многочлены от коэффициентов /. В статье для многочлена / с
корнями в поле F? указывается сложная формула, выражающая эти корни через
примитД элемент поля Fr В статье Rados [4] приводится явное вырад|
для многочлена НОД (/ (х), хр~г - 1), где р - простое Особые приемы были
развиты для нахождения корней lydjj членов небольшой степени. Даже задача
определения KOjf квадратного уравнения х2 - aCFp [х], где р - простое чЩ
становится нетривиальной, если число р велико. Некоторый}1 тоды
встречаются еще у Гаусса (Gauss [1, ch. 6]); см. тС Adleman, Manders,
Miller [I], Chang [ I ], Cipolla [1], [2h .fi mer D. H. [10], Pocklington
[!], Schonheim [1], Shanks" Smith H. J. S. [!], Tamarkine, Friedmann [I],
Tonelli [Uv| pensky, Heaslet [I, ch. 10] и Vandiver [2]. Методы отыскания
Д ней квадратных многочленов над конечными полями xapaJOfff стнки 2
приводятся в работах Berlekamp [4, ch. 6] и Berlek^j Rumsey, Solomon [
11. О многочленах третьей и четвертой стМ см. следующие работы: Arnoux
[I, ch. 9], Arwin [!], СаШегд Cauchy [3], Cordone [1], Dickson [31],
Escott [I], Hirsetjt [5, ch. I], Mignosi [1], Mirimanoff [I], Oltramare
[I], Sat^ [11, [2], [31, [4], [5], Scarpis [1], Segre [10], Williams, Z$?
