Автоматная модель представления нелинейных псевдослучайных последовательностей с функцией выхода на основе системы инъективных преобразований

Захаров Вячеслав Михайлович доктор технических наук профессор, кафедра Компьютерных систем, Казанский Национальный Исследовательский Технический Университет им. А. Н. Туполева – КАИ 420111, Россия, Татарстан область, г. Казань, ул. К.маркса, 10 Zakharov Vyacheslav Mikhailovich Doctor of Technical Science professor of the Department of Computer Systems at Kazan National Research Technical University named after A.N. Tupolev 420111, Russia, Tatarstan, Kazan, Karl Marx' str., 10 gilvv@mail.ru Песошин Валерий Андреевич доктор технических наук профессор, кафедра Компьютерных систем, Казанский Национальный Исследовательский Технический Университет им. А. Н. Туполева – КАИ 420111, Россия, республика Татарстан, г. Казань, ул. К.маркса, 10 Pesoshin Valerii Andreevich Doctor of Technical Science professor of the Department of Computer Systems at Kazan National Research Technical University named after A.N. Tupolev 420111, Russia, Tatarstan, Kazan, Karl Marx' str., 10 pesoshin-kai@mail.ru Шалагин Сергей Викторович доктор технических наук профессор, кафедра Компьютерных систем, Казанский Национальный Исследовательский Технический Университет им. А. Н. Туполева – КАИ 420111, Россия, республика Татарстан, г. Казань, ул. К.маркса, 10 Shalagin Sergei Viktorovich Doctor of Technical Science professor of the Department of Computer Systems at Kazan National Research Technical University named after A.N. Tupolev 420111, Russia, Tatarstan, Kazan', Karl Marx' str., 10 sshalagin@mail.ru

Эминов Булат Фаридович кандидат физико-математических наук доцент, кафедра Компьютерных систем, Казанский Национальный Исследовательский Технический Университет им. А. Н. Туполева – КАИ 420111, Россия, республика Татарстан, г. Казань, ул. К.маркса, 10 Eminov Bulat Faridovich PhD in Physics and Mathematics associate professor of the Department of Computer Systems at Kazan National Research Technical University named after A.N. Tupolev 420111, Russia, Republic of Tatarstan, Kazan', Karl Marx' str., 10 bulfami@mail.ru

Введение

Тема развития, совершенствования моделей и алгоритмов построения генераторов псевдослучайных последовательностей (ПСП) с характеристиками, близкими к случайным последовательностям, постоянно отражается в публикациях. Примерами подобных работ, опубликованных в последние годы, являются [1–18]. Одной из активно исследуемых задач в этом направлении является задача ^[19,20] усложнения аналитического строения псевдослучайных последовательностей, применяемых для различных приложений (помехозащищенность широкополосных сигналов, защита информации и др.). Распространенный подход усложнения строения формируемой ПСП заключается в применении к элементам заданной исходной ПСП дополнительного преобразования в виде некоторой нелинейной внешней логики (нелинейной функции усложнения (НФУ)) ^{[6, 19-24]}.В данном подходе выбором исходнойПСП обеспечивается требуемый максимальный период формируемой псевдослучайной последовательности, а необходимое ее качество определяется моделью НФУ.

Важной задачей в отмеченном подходе является построение математических моделей нелинейной функции усложнения, однозначно выполняющей преобразование исходной ПСП и формирующей выходные нелинейные последовательности, обладающие на заданном максимальном периоде статистическими свойствами, приближающимися к свойствам случайной равновероятной последовательности. Этой задаче посвящена, в частности, работа ^[24], где представлена модель генератора ПСП с нелинейной функцией усложнения, реализующей усложнение ПСП из класса М-последовательностей ^[7] путем перестановки ее элементов. Перестановка в ^[24] реализуется на основе модулярной операции возведения в степень по модулю простого числа Ферма. Данная НФУ позволяет менять строение ПСП параметрически - путем замены в модулярной операции значений первообразных корней ^[25]. Однако период получаемых нелинейных ПСП на модели ^[24] ограничен величиной модуля, определяемого простым числом Ферма.

Целью работы является определение и алгоритмическое построение математической модели представления нелинейных ПСП на основе модулярной операции возведения в степень по модулю, принадлежащему к множеству простых чисел Ферма, позволяющей получать нелинейные ПСП с заданными перио­дами L = 2ⁿ−1 и L = 2ⁿ , где n > 1.

1.Постановка задачи

Рассмотрим генератор ПСП в виде конечного автономного автомата с функцией выхода:

(S, Y, , , s_⁰), (1)

где S - конечноемножество состояний; Y - конечное множество выходных букв; : S → S - функция переходов; : S → Y - функция выхода; s₀ – начальное состояние. Пусть |S| = |Y|, состояния автомата (1) являются двоичными векторами , выходные буквы являются двоичными векторами . Функция переходов автомата выполняет преобразование вектора Х в вектор Х и реализуется как генератор последовательности де-Брейна с периодом 2ⁿ на основе РС с нелинейной функцией обратной связи, определяемой полиномом вида ^[20]:

, (2)

где F(x) примитивный полином степени n над полем GF(2) = {0, 1}. Полином F(x) задает функцию обратной связи РС, генерирующего M-последовательность с периодом 2ⁿ−1. Функция выхода рассматривается как функция усложнения, выполняющая однозначное отображение

Z = (X): G(2)ⁿ → G(2)ⁿ, (3)

где G(2)n – множество n-мерных двоичных векторов, |G(2)ⁿ| = 2ⁿ.

Введем следующее нелинейное преобразование - алгоритм возведения в степень по модулю простого числа ^[25]:

, (4)

где p - простое число, j - целое число, Q_h - заданный первообразный корень (примитивный элемент) по модулю p, h = 1, 2, …, (p−1) (число первообразных корней при заданном модуле p равно значению функции Эйлера (p−1)) ^[25], Q_h принимает значения из интервала 1 < Q_h < p−1.

Отметим следующие свойства алгоритма (4), вытекающие из свойств первообразных корней по модулю p ^[25]. Обозначим их символами С1, С2, С3. Введем множества М₁ = {1, 2, …, p−1}, М₂ = {0,1, 2, …, p−1}.

Свойство С1 ^[25]. Пусть в алгоритме (4) переменная jпринимает значения из множества М₁ = {1, 2, …, p−1}. Тогда алгоритм (4) выполняет инъективное отображение F1: М₁ → М₁ и последовательность значений у_j, получаемая по алгоритму (4), имеет период p−1. Отображение F₁ есть перестановка, заданная на М₁.

Свойство С2 ^[25]. Пусть в алгоритме (4) переменная j принимает значения из множества М₂ ={0,1, 2, …, p-1}. Тогда алгоритм (4) выполняет однозначное отображение, сюръекцию F₂: М₂→М₁. В (4) значениям j = 0 и j = p−1 сопоставляется значение у_j = 1.

Свойство С3 ^[25]. Пусть в алгоритме (4) переменная jпринимает значения из множества М₁. Тогда алгоритм (4) при j = (p−1)/2 и заданном Q_h, 1 < Q_h < p –1, выполняет соответствие вида j→(влечет) у_j = р − 1, т.е.

(5)

Решаемой задачей является построение для автоматной модели (1) нелинейной функции выхода, реализующей инъективное отображение (3), где n – четное, n > 1, на основе алгоритма (4).

2. Анализ задачи, подход к решению

Из свойств С1-С3 следует:

1) для реализации в модели (1) инъективного отображения (3) алгоритмом (4) необходимым условием является выполнение соотношения p > 2^_n, n > 1;

2) чем больше величина ∆= p − 2ⁿ, тем больше отличается по составу и величине элементов множество Y от S при реализации функции выхода .

Введем в рассмотрение следующее множество простых чисел p, при которых величина ∆ имеет минимальное значение, равное ∆ =1: множество М_F={р₁, р₂, р₃, р₄} простых чисел Ферма (чисел вида р = 2^m + 1, где m=2, 4, 8, 16, р₁=2²+1=5, р₂=2⁴+1=17, р₃=2⁸+1=257, р₄=2¹⁶+1=65537).

Введем множество М₃ = {0, 1, 2, …, 2^m−1}, |М₃|=2^m, m=2, 4, 8, 16.

Рассмотрим решение задачи реализации инъективного отображения вида F3: М₃→М₃ на основе алгоритма (4).

Отметим следующее свойство алгоритма (4).

Утверждение 1. Пусть в алгоритме (4) выполняются следующие условия: модуль рМ_F, 1 < Q_h < p–1, переменная j принимает значения из множества М3, величина 2^m = p−1, m = 2, 4, 8, 16. Тогда алгоритм (4) выполняет инъективное отображение вида

F₂: М₃ → М₄ = {1, 2, …, 2^m-1, 2^m},

где представлено соответствие

. (6)

Справедливость утверждения 1 следует из свойств С1, С2, C3.

Отметим: операцию возведения в степень по модулю рМ_F по выражению (4) можно реализовать путем применения вычислительного алгоритма, представленного в виде ^[26].

Пример 1. Реализация в соответствии с ^[26] операции возведения в степень по модулю. Пусть m=4, р₂=17, Q₁=3.

1) Зададим двоичное текущее значение j. Пусть j =(х₀ х₁ х₂ х₃)₂=1011.

2) Заполним следующую таблицу

j	х0	х1	х2	х3
Q	Издательство О нас Наши реквизиты Наши партнеры Контактная информация Политика конфиденциальности   Авторам Договоры Авторская зона   Услуги Институт рецензирования   Разное Как написать статью? Журналы в перечне ВАК Мобильное приложение Вопрос - ответ   Наши сайты Aurora group s.r.o. © 1998 – 2024 Nota Bene. Publishing Technologies. NB-Media Ltd.