Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
[I], Гребеиюк [2], Иванов [Пи Матвеева [1]. О многочл^ пятой степени см.
работы Arwin [2] и Горбов и Шмидт [1ЬД? бые методы вычисления корней для
многочленов малой сте^ возникают также в связи с алгоритмами
декодирования в Щ
Упражнения
231
браической теории кодироваиия; см.т например, статьи Chien, Cunningham
[I], Polkinghorn [1] и Блох [1]. Точные формулы для корней двучленов над
простыми конечными полями можно найти в работах Cipolla [4], Dickson [40,
ch. 7], Farquim de Almeida [lL Lindgren [1] и Scorza [I]. Эффективный
алгоритм для нахождения корней двучленов над простым конечным полем
развит в статье Adleman, Manders, Miller [1]; относительно случая
произвольного конечного поля см. Mignotte [5]. В статье Williams Н. С.
[1] рассматривается случай двучленов простой степени над простым полем
|FP.
Условия, при которых все корни многочлена нз кольца [х] принадлежат полю
|F?, найдены в работе Feit, Rees [1]. Частный случай, когда число ц
простое, рассматривался в следующих работах: Schonemann [2], Thouvenot,
Chatelet [Пи Шатуновскнй [1]. В статье Mignotte [4] представлен быстрый
алгоритм, с помощью которого можно проверить, все ли корни многочлена /?
[х J принадлежат полю |F?. В работах Cipolla [5] и Mignosi
[21 приводятся формулы для корней многочлена в случае, когда все эти
корни принадлежат полю IF?. Редей (Redei И К ch. 5 ]) указал многочлены
вида / (х) - ф ahxk Ф Ф
• -> + a0?lF? [#1, где k < (q Ф 1)/2, у которых все корни принадлежат
полю см. также статью Redei [7] о более ранних результатах в этом
направлении. В статье Gerst, Brillhart [Г] изучены условия, при которых
многочлен f [х] разлагается на различные линейные сомножители по модулю
р, для многих простых чисел р; близкий пример приводится в статье
Lubelski 13].
За результатами о числе корней многочлена в заданном конечном поле мы
отсылаем читателя к § 1 гл. 6 и комментариям к этому параграфу.
[Григорьев [1*], Леистра (Lenstra [2*]) и Ван дер Газен и Калтофен (van
der Gathen, Kaltofen [1*]) построили алгоритмы разложения йа множители
многочленов степени п от г переменных над произвольным конечным полем При
этом в работах первых двух авторов строится детерминированный алгоритм,
имеющий сложность, ограниченную многочленом от пг и q, а в последней
работе - вероятностный алгоритм, имеющий сложность, ограниченную
многочленом от пг и In q.
По тематике четвертой главы имеются также следующие работы: Calmet, Loos
[1*], Lenstra [I*], Smeets [1*1, Кюрегян И*) и Мурзаев [2*]. - Перев. ]
Упражнения
4.1, Разложить многочлен х12 ф х7 ф Xs ф х4 ф х3 ф х2 ф 1 над полем |FS с
помощью алгоритма Берлекэмпа.
4.2. Разложить многочлен х7 ф хв ф хь - хэ ф х2 - х - 1 над полем (Р3 с
помощью алгоритма Берлекэмпа.
232 Гл. 4. Разложение многочленов на множители
4.3. Пусть Г4 - Fa (Й); разложить многочлен хг> вж4 -\- х3 4- (1 @\
¦¦!- Й над полем Г4 е помощью алгоритма Берлекэмпа.
4.4. Применить алгоритм Берлекэмпа для доказательства неприводимой
многочлена хй - ж3 - ж - 1 в кольце Гд [ж 1,
4.5. Применить алгоритм Берлекэмпа для определения числа различай
нормированных неприводимых делителей многочлена х4 4- 1 в кольце JVj для
всех нечетных простых чисел р. р'':
4.6. Использовать многочлены ?';¦ из теоремы 4.3 для разложения мно|
члена х5 ¦{- ж4 3" 1 над нолем Г2. _
4.7. Найти поле разложения многочлена х8 + ж6 -ь ж\+ х4 -j - ж3 -}- $ Jjl
над полем
4.8. Найти поле разложения многочлена х6 - х4 - ж2 ¦- х Д- 1 над нолем |
4.9. Использовать многочлены Rt из теоремы 4.5 для разложения мир; члена
из упр. 4.1 над полем _
4.10. Найти каноническое разложение многочлена хэ -Ь -\- ж4 j- х3 4*1Р1 в
кольце Fa [х], используя многочлены Rj. ;|&pf
4.11. Найти каноническое разложение кругового многочлена Q;J1 (ж) в * '
F-2 1*1-
4.12. Разложить многочлен / (л! - xs - - xn : 1 над
нолем |р2 н вычнслйЦ^'
ord (/ (х)).
4.13. Разложить многочлен / (х) - xs -у xs -j-- х7 Д- х4 + х3 -f- х ф- I
чем и вычислить ord (/ (ж)}.
4.14. Дать подробное доказательство того, что если / -¦ ненулевой
многочлены над некоторым полем и d НОД (/, /'')• то многочлен / !d не
имеет неприводимых сомножителей. (Замечание. Считать ненулевые
постоянные, члены многочленами без кратных сомножителей.) до
4Л5. Пусть / нормированный многочлен положительной степени с лымн
коэффициентами, не имеющий кратных сомножителей. Доказать, что
Существует лишь конечное число простых чисел р, таких, что /,
рассматриваем!*#!
как многочлен над полем Fp, имеет кратные сомножители.
4.16. Определить число нормированных многочленов из [*1 стеоВйЩ: п Дз: 11
ие имеют их кратных н еп р и вод и м ых со ми ож ител ей. ;;
4.17. Пусть / нормированный многочлен над полем F</,h пустьglt , ?тф
ненулевые многочлены над F(?t которые попарно взаимно просты. Доказать,
чфй,
.V/
1
Г
если / делит произведение gl ... gr, то f НОД (f, gR.
< i
4.18. Используя алгоритм Берлекэмпа, доказать следующий частный елуф чай
теоремы 3.75: если a (- f * и t - простой делитель числа q - 1, то
