ЛРП над полем GF 256. Помогите с теорией.

Необходимо написать программу генерирующую линейную рекуррентную последовательность над полем GF(256).

Для начала - какую-то конкретную последовательность или хотя бы какую-нибудь?

А на вопросы про алгебру я ответит смогу, если Вы сможете их задать:)

Иными словами, ТЗ в студию!

ТЗ, вот такое. Дано поле GF(256), нужно найти неприводимый многочлен над этим полем, который будет задавать ЛРП. Степень многочлена должны быть больше x^2. Причем элементы полученной ЛРП, должны быть элементами поля GF(256).

А я где-то сегодня прочел, что элементы поля вида GF(2^n) будут не числа, а многочлены. И это меня вводит в полный ступор. Как тогда элементы ЛРП могут быть элементами поля которое состоит только из многочленов?

В общем, могли бы вы мне расписать пример построения какой-нибудь ЛРП, с реальными числами и реально полученной последовательностью над полем GF(2^n). Ну или прям для GF(2^8) или для другого поля, вида GF(2^n).

А я где-то сегодня прочел, что элементы поля вида GF(2^n) будут не числа, а многочлены. И это меня вводит в полный ступор. Как тогда элементы ЛРП могут быть элементами поля которое состоит только из многочленов?

Например, поле комплексных чисел состоит из многочленов над полем вещественных чисел от формальной переменной i, арифметические действия над которыми учитывают правило i^2 = -1. В данном случае действительно можно считать, что GF(256) состоит из многочленов над F_2 с дополнительными соотношениями (только я их сейчас сходу не помню).

Теперь про генерацию ЛРП. Если я правильно понял, то нужно смотреть на страницу 503 указанной Вами книжки. (http://rutracker.org/forum/viewtopic.php?t=2258603 - отсюда скачивал)

Там написана матрица. Так вот коэффициенты этой матрицы a, a_0, a_1, ..., a_{k-1} есть коэффициенты найденного многочлена (в порядке возрастания степени). Если задано какое-то начальное состояние (т.е. k-1 первых членов ЛРП), то следующее состояние получается умножением предыдущего состояния (точнее, вектора состояния) на указанную матрицу слева.

Так, в конце не очень точно написал. Лучше просто смотреть в тест после матрицы, да.

Для приведенного многочлена x^8 + x^4 + x^3 + x + 1 рекуррентная последовательность будет задаваться соотношением s_{n+8} = 1 + s_n + s_{n+2} + s_{n+3} + s_{n+7}, если я не ошибся нигде. Теперь задаем первые несколько элементов s_i (в данном случае s_0, s_1, ..., s_7) и вычисляем следующие.....

Для приведенного многочлена x^8 + x^4 + x^3 + x + 1 рекуррентная последовательность будет задаваться соотношением s_{n+8} = 1 + s_n + s_{n+2} + s_{n+3} + s_{n+7}, если я не ошибся нигде.

Первое. Вот этот момент не очень понял. Как вы нашли соотношение s_{n+8} = 1 + s_n + s_{n+2} + s_{n+3} + s_{n+7}? Т.е. я заметил прямую связь с моим многочленом x^8 + x^4 + x^3 + x + 1, но какое теоретическое обоснование этой связи?

Второе. Сложение в соотношении s_{n+8} = 1 + s_n + s_{n+2} + s_{n+3} + s_{n+7} выполняется по модулю 256?

Третье. Т.е. если я возьму:

s_0 = 1; s_1 = 2; s_2 = 3; s_3 = 4; s_5 = 6; s_6 = 7; s_7 = 8;

и подставлю в соотношение s_{n+8} = 1 + s_n + s_{n+2} + s_{n+3} + s_{n+7}, то следующий член ЛРП будет равен: 1 + 1 + 3 + 4 + 8 = 17. Так?

Первое. Вот этот момент не очень понял. Как вы нашли соотношение s_{n+8} = 1 + s_n + s_{n+2} + s_{n+3} + s_{n+7}? Т.е. я заметил прямую связь с моим многочленом x^8 + x^4 + x^3 + x + 1, но какое теоретическое обоснование этой связи?

Я сам долго искал связь, и сам не уверен, что хорошо понимаю. Вообще, первично рекуррентное соотношение. Хотя бы потому, что ЛРП по определению - это последовательность, удовлетворяющая соотношению такого же вида, что я написал. Уже по этому соотношению строится матрица, определитель которой есть (в однородном случае, когда a = 0) многочлен с коэффициентами a_i (если a != 0, то не совсем, см в книжку).

Второе. Сложение в соотношении s_{n+8} = 1 + s_n + s_{n+2} + s_{n+3} + s_{n+7} выполняется по модулю 256?

Нет! По модулю 2, внезапно. Вообще, поле из p^n элементов это не то же самое, что «остатки от деления на p^n», они же «вычеты по модулю p^n». Устройство конечных полей написано тут: http://ru.wikipedia.org/wiki/Конечное_поле

s_0 = 1; s_1 = 2; s_2 = 3; s_3 = 4; s_5 = 6; s_6 = 7; s_7 = 8;

печаль в том, что в GF(256) нет элемента «8», опять же...

печаль в том, что в GF(256) нет элемента «8», опять же...

заменить на «8 = 0 в нашем поле», это потому что по модулю 2.

s_0 = 1; s_1 = 2; s_2 = 3; s_3 = 4; s_5 = 6; s_6 = 7; s_7 = 8;
и подставлю в соотношение s_{n+8} = 1 + s_n + s_{n+2} + s_{n+3} + >s_{n+7}, то следующий член ЛРП будет равен: 1 + 1 + 3 + 4 + 8 = 17. >Так?

Вы как-то плохо читали Нидеррайтера, там же все есть. Итак, у вас поле GF(2^n), это поле - главный идеал кольца многочленов над Z_2 (кольцом классов вычетов по модулю два), порожденный некоторым неприводимым многочленом степени n (обозначим этот многочлен за M). Z_2 - состоит из 0 и 1. Многочлен над этим полем, соответственно, удобно представить некоторым бинарным вектором, тогда сложение - операция xor. Главный идеал, порожденный многочленом M - это остатки от деления на M. Соответственно, ваше поле - это все бинарные вектора длины n (для 2^8 - по сути байты). Сложение двух элементов поля x и y - это тот же xor, умножение двух элементов поля: x*y mod M (умножаем x на y как многочлены над Z_2, и потом считаем остаток от деления полученного многочлена на M).

Теперь что до вашей задачи. Если у вас есть ЛРП x_k = a_(k-1)*x_(k-1) + a_(k-2)*x_(k-2) + a_(k-3)*x_(k-3) + ... то ей соответствует характеристический многочлен x^k - a_(k-1)*x^(k-1) - a_(k-2)*x^(k-2) - a_(k-3)*x^(k-3) - ... Поскольку у вас в поле сложение - это xor, то минус эквивалентен плюсу, то есть получаем многочлен x^k + a_(k-1)*x^(k-1) + a_(k-2)*x^(k-2) + a_(k-3)*x^(k-3) + ...

Если характеристический многочлен неприводим, то ЛРП имеет максимальный период (именно за тем и нужно его подбирать, иначе можно было бы взять любую ЛРП навскидку). Соответственно, для вашего многочлена получаем последовательность x_8 = x_4 + x_3 + x_1 + x_0

соответственно:

s_0 = 1; s_1 = 2; s_2 = 3; s_3 = 4; s_5 = 6; s_6 = 7; s_7 = 8;

получаем s_0 = 00000001; s_1 = 00000010; s_2 = 00000011; s_3 = 00000100; s_4 = 00000101; s_5 = 00000110; s_6 = 00000111; s_7 = 00001000;

s_8 = 00000010

И, кстати, вы уверены, что ваш многочлен _действительно_ неприводим над GF(2^8)?

над полем GF(256)

И, кстати, это не поле...