M-последовательности, последовательности Лежандра, Якоби и разностные множества Адамара

[Imaginarium]

...и? И что дальше?

И что произошло с'ом в заголовках пунктов?

[Katasonov]

Такое ощущение что это кусок главы выдранный из какой-то книжки по математике и зачем-то опубликованный на Хабре. Особенно повеселило: время на прочтение 5 минут и сложность: средняя :))

[aabzel]

M-последовательности применяются в радиолокации для кодирования BPSK зондирующих импульсов.

[aabzel]

Сколько различных М-последовательностей можно сгенерировать на сдвиговом регистре из K триггеров?

[Morgana0_0]

Так как период M-последовательности равен и равен порядку её характеристического многочлена, то ваша задача равносильна нахождению количества примитивных многочленов степени над полем .
Т.е. , где — функция Эйлера.

[aabzel]

Что такое поле F2? Что такое поле?

И что такое функция Эйлера?

[Morgana0_0]

Поле в общей алгебре — множество, для элементов которого определены операции сложения, взятия противоположного значения, умножения и деления (кроме деления на ноль), причём свойства этих операций близки к свойствам обычных числовых операций.
Поле в свою очередь это множество из двух элементов {0, 1}. Нетрудно проверить, что для него выполнены все аксиомы поля. С ними и формальными определениями лучше ознакомиться в каком-нибудь учебнике, например, Р. Лидл, Г. Нидеррайтер - Конечные поля.

Функция Эйлера отвечает на вопрос, сколько существует натуральных чисел взаимнопростых с и непревосходящих его.

[alvoskov]

Когда я поработал с LFSR в рамках хобби, то мне стало казаться, что математики порой ради высокой абстракции могут переусложнять многие вещи даже в научпопе. Да, теория нужна, но большинство людей мыслят не от абстракций, а от чего-то более осязаемого. Максимальность периода какого-нибудь xorshift можно доказать куда нагляднее:

1) Функция перехода ГПСЧ записывается в виде матрицы (и отдельно проговаривается, что тут всё не как обычно, т.е. вектор с битами пишут нередко горизонтально и слева от матрицы), операции в GF(2) объясняется по простому: заменяй сложение и вычитание на XOR, умножение - на AND. Да, тут возможны неочевидные нюансы в виде вырожденности матрицы, но обычно xorshift собирают по таблице с биективыми операциями над машинными словами.

2) Отдельно показывают, как эта самая матрица (часто companion matrix, но для xorshift может быть и иначе) выдает биты или машинные слова. Прям проговаривая и водя маркером.

3) Потом возводят матрицу в степень "период", и смотрят, получилась ли единичная матрица (что логично - оно должно в конце зациклиться)

4) Дальше возводят матрицу в степени "период / простой делитель периода" и смотрят, "не зациклилось ли по дороге".

5) Если ГПСЧ большой и матрицы тормозят, то можно уже переходить к характеристическим полиномам как к рекуррентным соотношениям. И через jump function проверять уже полиномы на примитивность. Отдельно показывая то, что деление многочленов уголком может соответствовать "промотке" членов последовательности.

В п.1 можно упростить себе жизнь, используя код на Си напрямую как математическую формулу.

[alvoskov]

Если M-последовательность удовлетворяет неким теоретическим критериям псевдослучайности, то откуда взялось столько странных ГПСЧ из LFSR с разреженными полиномами, проваливающих тесты на веса Хемминга или даже gap test? Тот же T800, LRND, вихрь Мерсенна без выходной функции, ещё куча ранних работ? У меня сложилось впечатление, что прогон хотя бы терабайта последовательности через PractRand и TestU01 не менее важен, чем теория. Также очень странны какие-либо мысли о ее криптостойкости, она же линейная.