Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
статьях Fiduccia, Zalcstein [1] и Winograd [I], [2]; см. также Bini,
Capov an I [I j. Алгоритмы для вычисления некоторых первообразных корней
из единицы представлены в работах Liu, Reed, Truong [1] и Reed, Truong,
Miller [I], [2]. В статье Pohlig, Heilman [1] построен быстрый алгоритм
для вычисления показателя г в равенстве Ьг - а при заданных а,
где b - примитивный элемент поля fQ; об этом см. также работы Herlestam,
Johannesson [1], Pollard [3] и Zierler [91, а также гл. 10, § 1 и табл. А
настоящей книги. Обзор по арифметическим алгоритмам для конечного поля
дается в работе Mignotte [3]. Реализация арифметики конечных полей на
переключательных схемах рассматривалась в следующих работах: Bartee,
Selmeider [I], Berlekamp [4, ch. 2], Gill [2, ch. 61, MacWilliams, Sloane
[2, ch. 33, Peterson, Weldon [1, ch. 73, Redinbo [13, Tanaka, Kasahara,
Tezuka, Kasahara [ 13 и Willett [63; о реализации ее на ЭВМ см. Calmet,
Loos [21.
Полезным вычислительным изобретением является дискретное преобразование
Фурье для конечного поля |F?, введеииое Поллардом (Pollard [1]). Пусть 6
- некоторый элемент порядка d мультипликативной группы поля Тогда
конечная последовательность а0, а1( ..., ad_x элементов поля может быть
преобразована в конечную последовательность
й~\
At = ? щЬ1\ i = 0, 1,
/=0
При этом обратное преобразование задается формулой
<м
aj = <Г] 2 Аi = Q, I, .... d-l.
с=о
Эти преобразования называются дискретными преобразованиями Фурье. Оба они
допускают быстрое вычисление, и при этом работают методы, аналогичные
применяемым в теории быстрых преобразований Фурье в обычном комплексном
аиализе. Дискретное преобразование Фурье встречается в теории кодирования
под названием многочлена Мэттсона-Соломоиа (см. Mattson, Solomon 1П и
MacWilliams, Sloane [2, ch. 83). Поллард (Pollard [13) показал, как можно
использовать дискретиые преобразования Фурье для выполнения
арифметических действий в поле Цу Дальнейшие результаты о днскретиом
преобразовании Фурье и его приложениях можно найти в работах Agarwal,
Burrus [13, oiahut [11, Fateman [II, Golomb, Reed, Truong [13, Liu, Reed,
Arnong [1], [23, McClellan, Rader [13, Nussbaumer [1, ch. 8],
15*
228
Гл. 4. Разложение многочленов на множители
Pollard [2], Preparata, Sarwate [1], Redinbo [I], Reed, "***_ Truong,
Welch 111, Reed, Truong [1], [2], [3], Reed, Trif Welch 11], Rice NJ и
Sarwate fl], [2].
Cy**
Осуществление какого-либо алгоритма разложения з$ж также от действий с
многочленами. Эффективные методы ¦fi множ^ння двух многочленов над
конечным полем fq предлаг^ в работах Borodin, Munro [I], Rice [2],
Schonhage [2] и|-лыго [ 1 j; см. также Fateman [I] и Pollard fl J. О
вычисй* наибольшего общего делителя и об алгоритме Евклида для igjt
членов от одной или нескольких переменных см. работы Agotif
[5], Barnett fl], Blankinship [I], Bose N. K- 113, Brown ijl [11. Collins
[3], Dickson 1333, Emre, Hiiseyin [13, Rnuih![ ch. 4|, Maroulas, Barnett
[1], McEliece, Shearer [13, Mos^l щ Vogt, Bose [1]. Дальнейшие результаты
об арифметике членов можно найти в статьях Bhanu Murthy, Sampath [13, La?
Михайлюк [1], [2] и Мурзаев [13- Полезные сведения о пбЦ миальиых
операциях над конечными полями можно найти if" дующих книгах: Aho,
Hopcroft, Ullman [1 3, Berlekamp [4, dpi Birkhoff, Bartee [ 1, ch. 11],
Borodin, Munro [ 1 ], Gill [2, cjjj Knuth [3, ch. 43 и Peterson, Weldon
[1, ch, 7 3).
§ 2. Алгоритм разложения, основанный иа использрЦ. результантов, восходит
к одному утверждению из пер вою f ния книги Кнута Knuth [3, ch. 4].
Вычисление полиноми$М^ результантов методом интерполяции предложено
Коллинзом ! ins [2]). Алгоритм Цассеихауза был описан в статье Zass#^
[5]. Алгоритм разложения с помощью диагона л изации мйС из многочленов
был предложен Берлекэмпом (Berlekamp jf Алгоритм, основанный на теореме
4.13, взят из статьи Golf Welcn, Hales [ 13; см. также Agou [8 3 и Knuth
[3, ch. 4 ]. О-Btpjj ностном алгоритме в этой связи см. Cantor,
Zassenhaus [Hci|
В работах Zassenhaus [4], Kempfert [3 3 и Knuth [3, <щ| рассматривается
алгоритм, состоящий в последовательномЦ численни для данного многочлена
/С[х] степени .Щ без кратных сомножителей многочленов вида dt (х) - НОД Щ
Xя1 - х) для / - 1,2, ..., \п!2\. Если все dt равны 1, то член f
неприводим иад полем fq. Если же / ^ ший индекс, для которого dj Ф 1, то
многочлен f приводим^
и dj является произведением всех его неприводимых ср:' жителей степени /.
Другие алгоритмы разложения можно
в работах Arwin [2], Beard [51, Camion [2], [3 3, Rabi$| Ананиашвили,
Варшамов, Горовой, Пархоменко [13, ВарШД Остиану [1 3 и Дынькин, Агаронов
Ц]. Сравнительное изШ эффективности различных алгоритмов разложения
многощ предпринято в статье Moenck []]. Методы определения поля
разложения многочлена над простым конечным полеШ^
Комментарии 229
сматриваются в статьях Speiser Ши Wegner [4]; случай произвольного
конечного поля изучается в статьях Mignotte [I]. [2],
