Математическое моделирование и вычислительный эксперимент
Правильная ссылка на статью:
Захаров В.М., Песошин В.А., Шалагин С.В., Эминов Б.Ф.
Автоматная модель представления нелинейных псевдослучайных последовательностей с функцией выхода на основе системы инъективных преобразований
// Кибернетика и программирование.
2017. № 5.
С. 64-78.
DOI: 10.25136/2644-5522.2017.5.23065 URL: https://nbpublish.com/library_read_article.php?id=23065
Аннотация:
Предметом исследования являются методы усложнения аналитического строения псевдослучайных последовательностей путем применении к элементам заданной исходной псевдослучайной последовательности дополнительного преобразования в виде нелинейной внешней логики - нелинейной функции усложнения. Целью работы является определение и алгоритмическое построение математической модели нелинейной функции усложнения, представляемой на основе модулярной операции возведения в степень по простому модулю, позволяющей получать нелинейные псевдослучайные последовательности, обладающие на заданном максимальном периоде статистическими свойствами, приближающимися к свойствам случайной равновероятной последовательности. Для представления модели используется формализм теории автоматов, теорий конечного поля, модулярной арифметики и простых чисел. Предложена автоматная модель формирования нелинейных псевдослучайных последовательностей с заданными периодами L = 2^n-1 и L = 2^n, n >1, отличающаяся функцией выхода, представленной в виде нелинейной функции усложнения на основе системы нелинейных преобразований по модулям, принадлежащих к множеству простых чисел Ферма. Доказано, что функция выхода автомата, представляется как инъективная функция, выполняющая на основе нелинейных модулярных операций на периоде L = 2^n перестановку элементов последовательности де-Брейна. Показано, что алгоритмическая модель функции выхода автомата позволяет менять структуру нелинейных последовательностей путем перестановки по псевдослучайному закону значений первообразных корней по модулю числа Ферма. Размер ансамбля нелинейных последовательностей, формируемых нелинейной функцией усложнения, зависит от числа первообразных корней и определяется нижней оценкой вида О(2^n), n>1.
Ключевые слова:
псевдослучайная последовательность, автоматная модель, функция усложнения, инъективное преобразование, последовательность де-Брейна, М-последовательность, простые числа Ферма, нелинейная модулярная операция, первообразные корни, ансамбль последовательностей
Abstract:
The subject of the research is the methods of complicating the analytical structure of pseudorandom sequences by applying additional mapping of nonlinear external logic, in particular, nonlinear complication function, to elements fo initial pseudorandom sequence. The purpose of the research is to define and develop an algorithm of a mathematical model of nonlinear complication function presented on the basis of the modular operation of the simple modul exponentiation. This allows to obtain nonlinear pseudorandom sequences that have statistical properties close to the properties of a random sequence at the set maximum period. To present the model, the authors have used the formalism of the automation theory, finite field theory, residue number and primes theories. The authors offer their own automation model for creating nonlinear pseudorandom sequences with the set periods of L = 2^n-1 and L = 2^n, n >1 with the output function as the nonlinear complication function on the basis of nonlinear mapping of modules belonging to Fermal primes. It has been proved that the automation output function is an injective function that displaces elements of the De Bruijn sequence. It has been demonstrated that the algorithmic model of the automation output function allows to change the structure of nonlinear sequences by pseudorandomly displacing values of the primitive roots of the Fermal prime. The size of the nonlinear sequence assemble formed by the nonlinear complication function depends on the number of primitive roots and is determined by the lower bound of О(2^n), n>1 type.
Keywords:
primitive roots, nonlinear modular operation, Fermat primes, M-sequence, the De Bruijn sequence, injective mapping, complication function, automaton model, pseudorandom sequence, ensemble of sequences