Первичность полинома на поле Галуа.

evgenija050179

В книге Хоровиц, Хилл "Искуство схемотехники" есть фраза:
Критерием для определения максимальной длины (Имеется ввиду псевдо-случайная последовательность) служит неприводимость полинома 1+x^n+x^m и его первичность на поле Галуа.
Неприводимость, насколько я понимаю - невозможность разложить на множители в действительных числах. (Или я не так понял.)
А что такое "первичность на поле Галуа"?

Vitaminka

неприводимость невозможно разложить на множители над полем

gateway-2002

только не действительных а целых. а термина первичность я не помню вообще. кароче щяс подниму конспекты

Vitaminka

ты бы еще сказал над полем кОмплексных

evgenija050179

только не действительных а целых.
Спасибо!

evgenija050179

Генератор последовательностей максимальной длины устроен так: Сдвиговый регистр, у которого к n-ой и m-ой ножкам подпаяны входы вентиля XOR. А выход вентиля XOR подается на вход сдвигового регистра.
Если состояние сдвигового регистра рассматривать как вектор в n-мерном линейном пространстве над полем {0,1} с операциями по модулю 2-х, то преобразование за такт можно представить как действие на этот вектор линейного опрератора. (Все операции тоже делаются по модулю 2). Так вот, многочлен 1+x^n+x^m - это, если я не ошибаюсь, характеристический многочлен такого преобразования. Но как его неприводимость может быть связана с тем, что получается последовательность максимальной длины?

b4331

Так вот, многочлен 1+x^n+x^m - это, если я не ошибаюсь, характеристический многочлен такого преобразования. Но как его неприводимость может быть связана с тем, что получается последовательность максимальной длины?
Не является ли рассматриваемая последовательность множеством корней этого многочлена (т.е. множеством собственных значений преобразования, если это хар-кий мн-н)? Если да, то связь такая: неприводимый многочлен над конечным полем или полем характеристики 0 не может иметь кратных корней ни в каком расширении данного поля (т.е. является сепарабельным).
Кстати во фразе
А что такое "первичность на поле Галуа"?
под полем Галуа я думаю понимается конечное поле из 2-х элементов, т.е. имеется в виду какое-то св-во этого мн-на (как многочлена) над Z_2 (причем моя догадка состоит в том, что это св-во - неприводимость, т.к. "prime polynomial" - неприводимый мн-н - можно также перевести как "первичный мн-н").

evgenija050179

Не является ли рассматриваемая последовательность множеством корней этого многочлена (т.е. множеством собственных значений преобразования, если это хар-кий мн-н)?
- Я не знаю... Псевдослучайная последовательность состоит из нулей и единиц. Но можно считать, что это - последовательность состояний сдвигового регистра (векторов в n-мерном линейном пространстве над полем Z_2). Что может быть "корнями неприводимого многочлена"? - я ничего не понимаю...
причем моя догадка состоит в том, что это св-во - неприводимость, т.к. "prime polynomial" - неприводимый мн-н - можно также перевести как "первичный мн-н"
- Что-то мне тоже так стало казаться, что они одно и то же перевели дважды!
- Но как связаны неприводимость характеристического многочлена матрицы и условие, что единице равна только (2^N-1)-ая степень этой матрицы - совсем не понимаю... (Над полем Z_2)
Оставить комментарий
Имя или ник:
Комментарий: