Правильная ссылка на статью:
Захаров В.М., Песошин В.А., Шалагин С.В., Эминов Б.Ф..
Автоматная модель представления нелинейных псевдослучайных последовательностей с функцией выхода на основе системы инъективных преобразований
// Кибернетика и программирование. – 2017. – № 5.
– С. 64-78.
DOI: 10.25136/2644-5522.2017.5.23065.
DOI: 10.25136/2644-5522.2017.5.23065
Читать статью
Аннотация: Предметом исследования являются методы усложнения аналитического строения псевдослучайных последовательностей путем применении к элементам заданной исходной псевдослучайной последовательности дополнительного преобразования в виде нелинейной внешней логики - нелинейной функции усложнения. Целью работы является определение и алгоритмическое построение математической модели нелинейной функции усложнения, представляемой на основе модулярной операции возведения в степень по простому модулю, позволяющей получать нелинейные псевдослучайные последовательности, обладающие на заданном максимальном периоде статистическими свойствами, приближающимися к свойствам случайной равновероятной последовательности. Для представления модели используется формализм теории автоматов, теорий конечного поля, модулярной арифметики и простых чисел. Предложена автоматная модель формирования нелинейных псевдослучайных последовательностей с заданными периодами L = 2^n-1 и L = 2^n, n >1, отличающаяся функцией выхода, представленной в виде нелинейной функции усложнения на основе системы нелинейных преобразований по модулям, принадлежащих к множеству простых чисел Ферма. Доказано, что функция выхода автомата, представляется как инъективная функция, выполняющая на основе нелинейных модулярных операций на периоде L = 2^n перестановку элементов последовательности де-Брейна. Показано, что алгоритмическая модель функции выхода автомата позволяет менять структуру нелинейных последовательностей путем перестановки по псевдослучайному закону значений первообразных корней по модулю числа Ферма. Размер ансамбля нелинейных последовательностей, формируемых нелинейной функцией усложнения, зависит от числа первообразных корней и определяется нижней оценкой вида О(2^n), n>1.
Ключевые слова: псевдослучайная последовательность, автоматная модель, функция усложнения, инъективное преобразование, последовательность де-Брейна, М-последовательность, простые числа Ферма, нелинейная модулярная операция, первообразные корни, ансамбль последовательностей
Библиография:
Марченко М.А., Михайлов Г.А. Распределенные вычисления по методу Монте-Карло // Автоматика и телемеханика, № 5, 2007. С. 157-170.
Якобовский М.В. Последовательности псевдослучайных чисел для многопроцессорных приложений, 2008. //http://www.imamod.ru/projects/ FondProgramm/RndLib/lrnd32_v02
Иванов М.А., Ковалев А.В., Чугунков И.В. и др. Стохастические методы зашиты информации в компьютерных системах и сетях. М.: КУДИЦ-ПРЕСС, 2009. 512 с.
Агибалов Г.П. Sibecrypt 10. Обзор докладов / Прикладная дискретная математика, 2010. № 4(10). С. 109-124.
Диченко С.А., Вишневский А.К., Финько О.А. Реализация двоичных псевдослучайных последовательностей линейными числовыми полиномами // Известия ЮФУ. Технические науки, №12, 2011. С. 130-140.
Иванов М.А., Васильев Н.П., Чугунков И.В. и др. Трехмерный ГПСЧ, ориентированный на реализацию в гибридных вычислительных системах. Вестник НИЯУ «МИФИ», 2012, том 1, №2. С. 1-4.
Кузнецов В.М., Песошин В.А. Генераторы случайных и псевдослучайных последовательностей на ц