Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
векторных пространств над полем Г9. В этой связи Диксон (Dickson 17, part
I, ch. 4]) и Мур (Moore [4]) показали, что число г-мерных подпространств
я-мерного векторного пространства над полем Fg задается формулой
Г-1
Д fan-i _ 1)(<7Г~(' - 1)~!, где 1<><я.
f-0
Как определил Нивен (Niven [1 ]), наименьшее общее кратное порядков всех
элементов группы GL (&, Fg) равно р*М, где р - характеристика поля Fg, в-
наименьшее целое число, для которого ре kt а М - наименьшее общее кратное
чисел q - 1, 11г - 1, ... , qk - 1- Эти результаты были дополнены и
обобщены в работе Marshall [1 1. Так, утверждение о том, что порядок
матрицы А в GL (fe, Fg) делит
570 Гл. 8, Линейные рекуррентные последовательности
можно усилить до утверждения, что этот порядок делит РеМЩ Аналог
результата Нивена для GL (k, Zj(m)) был получен в pa|fj| ботах Davis [I ]
и Maxfield [1 ], Кроме того, Нивен в той же работе Niven [I I получил
алгоритм для определения порядка элемент^! из GL (к, FA- Исследованию
порядков матриц посвящены также работы Bollman И], Dai П j, Fillmore,
Marx [1], Gaiu [1] ц|| Liineburg [2, ch. 32, 33]. ||
Теория линейных рекуррентных последовательностей Hajj конечными полями
помимо применения к анализу и синтезу р&Я гистров сдвига с обратной
связью имеет еще одно важное npgJJ менение, а именно в теории
кодирования, особенно в теорищ! циклических кодов (см. § 2 гл. 9
настоящей монографии). ПеД| вымн работами по связи линейных рекуррентных
последователей ностеи и регистров сдвига с обратной связыо с теорией
кодирж§ вания были работы Abramson [1 J, Green, San Soucie f 1 J, Huff
таю fl ], [2], Kasami [11, Mattson, Solomon fl I, Peterson П J, Prangjlj
[ 1 3, Stern, Friedland [1], Yale [11, Zetterberg [1| и Zierler [llBH
[31. См. также Massey [3], Mykkeltveit [1], Zierler [51 и ГабидЯ! лин fl
1, а кроме того, монографии Ash [1, ch. 51, Lin [2, ch. 4),||1 Peterson,
Weldon [1 ]. Приложения к вычислениям в и щ|| рассматривались в работах
Bartee, Schneider [1 j, Berlekanfjjl [4, ch. 2], Bhanu Murthy, Sampath
[1], Gill [2, ch. 61, Tanakjjj Kasahara, Tezuka, Kasahara [1 ] и Willett
[61. Алгоритм МиньотЯв (Mignotte [1]) для определения степени поля
разложения мйогЙИ члена над полем также основывается на свойствах
линейнйЯ рекуррентных последовательностей. Другие связи линейных рШш
куррентных последовательностей с разложением многочленов ."В множители
можно найти в статье Willett [5]. Свойства линейнЩш рекуррентных
последовательностей 2-го порядка над конечными простыми полями
применялись в работе Niederreiter, RobinscB [1] для анализа конечных луп
Бола. Применения линейных рщж куррентных последовательностей над полем р2
в криптографам обсуждаются в работе Beker, Piper [1]. Слозн (Sloane [2 |)
минает о связях между крнптографиен и регистрами сдвига с о§|| ратной
связью. Обзор практических приложений линейных рё|§| куррентных
последовательностей дается в работах Golomb Ш}|| ch. 1 |, 14, ch. 1 ]. О
некоторых специальных приложениях лосле§1 довательностей максимального
периода будет упоминаться пиж&Я в комментариях к § 2 настоящей главы.
Щ
Линейные рекуррентные последовательности можно рассмат||1 рнвать и над
более общими алгебраическими структурами. Уорй (Ward [11) изучал
рекуррентные последовательности над произ||| вольными полями, а позднее в
работах Ward [13], 1151 он нача||| изучать линейные рекуррентные
последовательности над коммщ| тативными кольцами. Дальнейшие исследования
по этим наnpaBrjj ленням можно найти в работах Dade, Robinson, Taussky,
Ware
Комментарии 571
[I), de Carli И ], Duparc 111, Robinson D. W. 14] и Shiue, Sheu [lj.
Линейные рекуррентные последовательности над модулями изучались в статьях
Nathanson [5] н Niederreiter [5], [6]. Линейные рекуррентные
последовательности векторов рассматривались в работах ВоИтап [1], Daykin
[4], Selmer [3, ch. 7], Vince 12]. Свойства периодичности
последовательностей над Fg и Zl(m), удовлетворяющих рекуррентным
соотношениям вида
Sa+fe - ^fe-i (п) sn+fe~l (*0 Sn+ft_2 ~b ¦ * * 4" a(i (n) SB!
i-де коэффициенты at (n) периодичны no nt изучали Нечаев [1], [3] и
Полосуев [1 I. Свойства периодичности, получаемые нз рекуррентных
соотношений других типов, были получены Дюпар-ком (Duparc 12]). Линейные
рекуррентные последовательности над полем Fg представляют собой
одномерный случай в теории линейных рекуррентных массивов надрд.
Этатеория была развита в работах MacWilliams, Sloane [1 ], Nomura, Fukuda
[1 ], Nomura, Miyakawa, Imai, Fukuda 111, 12], [3], Sakata [1], 12],
§ 2. Особая роль, которую играет импульсная функция, была отмечена еще в
классической литературе по линейным рекуррентным последовательностям
(см., напоимер, Lucas [2, ch. 17] и d'Ocagne [1]), Теоремы 8.16 и 8.19
были получены Уордом (Ward [5]), а теорема 8.17 была доказана для
простого q Спей-еером (Speiser [1]). Другие результаты, имеющие отношение
к импульсным функциям, можно найти в работах Ajtai [1 ], Kiss, Bui Minh
