Нелинейные псевдослучайные последовательности над конечным полем

Представлена автоматная модель построения нелинейных псевдослучайных последовательностей с периодом L = 2^n . Функция переходов автомата реализуется на основе генератора М-последовательности. Функция выхода определяется как нелинейная функция усложнения, реализующая векторное однозначное преобразование состояний автомата на основе системы нелинейных модулярных операций по модулю, принадлежащему к множеству простых чисел Ферма. Размер ансамбля выходных последовательностей является экспоненциальной функцией от величины n.

Для справки:
Для ряда криптографических преобразований используют случайные первичные состояния либо целые последовательности. А значит, стойкость криптоалгоритма, использующего такие состояния или последовательности, напрямую зависит от алгоритма генерации случайных чисел и последовательностей, точнее от их степени случайности. Последовательность называется случайной, если воспроизвести ее, зная алгоритм и все исходные данные не представляется возможным (дважды запустив генератор в тех же условиях мы получим разные последовательности). Но компьютерные системы детерминированы, т.е. они могут находиться лишь в конечном количестве состояний. Это приводит к тому, что генерируемые ими последовательности будут периодичны - такие последовательности называются псевдослучайными. Последовательность называется криптографически надежной псевдослучайной последовательностью, если вычислительно неосуществимо предсказать следующий бит, имея полное знание алгоритма и аппаратуры и всех предшествующих битов потока. Кроме того, случайные и псевдослучайные последовательности, используемые в криптографических преобразованиях должны подчиняться закону равномерного распределения. Примером такого распределения может служить следующая последовательность: время, остающееся до начала движения поезда в метро с момента спуска под землю (с учетом что поезд ходит через равные интервалы времени, а спускаемся в подземку мы в случайный дискретный момент времени). Реализовать такую последовательность математически можно используя конгруэнтные генераторы псевдослучайных чисел.

#наука #псевдослучайныепоследовательности

[РусланМим]

Здравствуйте, хорошее видео, а в чем заключаются недостатки М-последовательности и можно ли избавиться от них не применяя реализацию де-Брейна?

[zena_]

С момента записи видео прошло почти 3 года. Появились ли другие методы построения нелинейных псевдослучайных последовательностей?