Научная литература
booksshare.net -> Добавить материал -> Физика -> Лидл Р. -> "Конечные поля. Том 1" -> 239

Конечные поля. Том 1 - Лидл Р.

Лидл Р., Нидеррайтер Г. Конечные поля. Том 1 — М.: Мир, 1988. — 430 c.
ISBN 5-03-000065-8
Скачать (прямая ссылка): konechniepolya1988.djvu
Предыдущая << 1 .. 233 234 235 236 237 238 < 239 > 240 241 242 243 244 245 .. 371 >> Следующая

определения при условии, чтр q ф 2. Если же q - 2, то 2k - 1 членов
иногда может быть достаточно для определения минимального многочлена, но
2k - 2 никогда не
j
1
VVS
1
Комментарии
577
будет достаточно. Дальнейшие замечания по этому вопросу, относящиеся к
случаю# = 2, можно найти в работе Dillon, Morris fl], Густавсон
(Gustavson [1]) оценил среднее число сложений и умножений, требуемое
алгоритмом Берлекэмпа-Месси. Обсуждение этого алгоритма можно также найти
в книге Dornhoff, Hohn (1, ch. 9j. Еще ряд замечаний и ссылок по поводу
этого же алгоритма можно найти в комментариях к § 2 следующей главы.
§ 7. Первой работой, посвященной распределению элементов основного ноля в
рекуррентной последовательности, является работа Scarpis [2], в которой
изучается Z (0) для линейных рекуррентных последовательностей 2-го
порядка над нолем с нечетным д. Позднее в статье Ward [3J изучалось
распределение элементов в линейных рекуррентных последовательностях 3-го
порядка над полем Fp- Случаи последовательностей более высокого порядка
рассматривались в работах Hall [3], [4]. Мощный метод тригонометрических
сумм был впервые применен для исследования этих вопросов Коробовым [1].
Теоремы 8.78 и 8.81 являются частными случаями результатов Нидеррайтера
(Niederreiter [5],
[6]). Оценку (8.31) в большинстве случаев можно улучшить (см. упр. 8.66).
Оценка, полученная в теореме 8.81, оказывается не-улучшаемой (см.
Niederreiter [5]). Другими работами по тригонометрическим суммам такого
вида являются статьи Niederreiter
[7], [8] и Нечаев [5], [6]. Случай более общих рекуррентных соотношений
рассматривался в работах Niederreiter [11] и Нечаев [2].
Простая формула для Z (Ь) в случае последовательности максимального
периода была впервые получена в работе Golomb fl 3 для
последовательностей над полем Fa. Теорема 8.82 доказана в статье
Niederreiter [6 j. Оценка такого типа была получена раньше комбинаторными
методами в работе Hall [4] для случая однородной линейной рекуррентной
последовательности k-ro порядка над полем Fp с неприводимым
характеристическим многочленом. Еще раньше Холл (Hall [3]) показал, что
если в этом случае минимальный период превосходит величину рк!2, то в
последовательности обязан встретиться элемент 0. Селмер (Selmer [3, ch.
5]) получил аналог результатов Холла для случая, когда Я ~ 2 и
характеристический многочлен является произведением двух различных
неприводимых многочленов над полем F2- Теорема 8.84 доказана в работе
McEliece [5]: Распространение этого метода на случай, когда минимальный
многочлен ие имеет кратных сомножителей, можно найти в работе
Niederreiter [8]. Результат теоремы 8.85 о распределении элементов поля
на отрезках рекуррентных последовательностей длины, меньшей периода, был
получен в работе Niederreiter [61. Там же было показано, что эта оценка
неулучшаема. Распределение элементов, принадлежащих данному подмножеству
поля Fg (например, принадлежащих множеству
Ю Зак. 243
V/8 Гл. 8. Линейные рекуррентные последовательности
7!
примитивных элементов поля Fg), в линейных рекуррентных
последовательностях над полем Fg рассматривалось в следующих работах:
Niederreiter [б], Коробов [1], Нечаев [4], Нечаев, Степанова [1] и
Шпарлниский [1]. Аналогичные вопросы для последовательностей,
удовлетворяющих более общим рекуррентным соотношениям, изучались Нечаевым
и Полосуевым [1]. Многие результаты из этой работы могут быть перенесены
на случай линейных рекуррентных последовательностей над кольцом Z/(m)
(см. Niederreiter [6], Нечаев [4]).
Голомб (Golomb [9]) рассматривал последовательности над полем F2 с
периодом (не обязательно минимальным), равным 2к - 1, в которых чнсло
появлений 0 и 1 такое же, как в мини* мальном периоде последовательностей
k-то порядка, имеющий максимальный период. В статье Hemmati, Costello [1]
построены линейные рекуррентные последовательности над полем Fg" длй
которых Z (0) = 0. Макэлайс (McEliece [4]) получил значений^ для Z (6) по
различным модулям, равным степеням характерна стикн поля Fg- Исследование
распределения элементов в линейньпЙ рекуррентных последовательностях
небольших порядков было! проделано в работах Scarpis [2], Ward [3], Hall
[2], а такж! в появившихся позднее работах Bloom [lj, Bruckner [1], Burij
|1|, Shah [1], Zeekendorf [1]. Некоторые нз этих работ охваты* вают
случай последовательностей над кольцом Z/(m). Результат о свойствах
распределения элементов поля в линейных рекуррент* ных
последовательностях находят применение в теории кодирова ния (см.
McEliece [5], Niederreiter [8]), а также при получений псевдослучайных
чисел (см., например, Golomb [lj, [4, ch. 3f Niederreiter [7], [10]).
Линейные рекуррентные последовательности над полем Fgll для которых Z (Ь)
имеет одно н то же значение для всех b ? F ' привлекают особое внимание.
Последовательность у таким сво ством называется равномерно распределенной
(uniformly distrl buted, equidistributed) над Fg согласно определению,
Предыдущая << 1 .. 233 234 235 236 237 238 < 239 > 240 241 242 243 244 245 .. 371 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed