автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Методы и алгоритмы построения и анализа полиномиальных функций над конечным полем на основе стохастических матриц

На правах рукописи

ЭМИНОВ Булат Фаридович

МЕТОДЫ И АЛГОРИТМЫ ПОСТРОЕНИЯ И АНАЛИЗА ПОЛИНОМИАЛЬНЫХ ФУНКЦИЙ НАД КОНЕЧНЫМ ПОЛЕМ НА ОСНОВЕ СТОХАСТИЧЕСКИХ МАТРИЦ

05 13 18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Казань - 2008

003168924

Работа выполнена в Казанском государственном техническом университете

им АН Туполева

Научный руководитель доктор технических наук,

профессор Захаров Вячеслав Михайлович

Официальные оппоненты доктор физико-математических наук,

профессор Аблаев Фарид Мансурович

доктор технических наук,

профессор Крашенинников Виктор Ростиславович

Ведущая организация Новгородский государственный университет

им. Ярослава Мудрого (г Великий Новгород)

Защита состоится " 6" июня 2008 г в 14 часов на заседании диссертационного совета Д 212 079 01 в Казанском государственном техническом университете им АН Туполева по адресу 420111, г Казань, ул К Маркса, 10

С диссертацией можно ознакомиться в библиотеке Казанского государственного технического университета им А Н Туполева

Автореферет разослан "_"_2008 г

Ученый секретарь

диссертационного совета, С74" ПГ Дани паев

доктор физико-математических наук, профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы Одним из подходов моделирования цепей Маркова (ЦМ) и марковских функций является подход, использующий теорию конечных полей Перспективность этого подхода определяется приложением функций конечных ЦМ, возрастающей сложностью вероятностных дискретных моделей и эффективностью арифметики конечных полей в задачах цифровой обработки информации Аппарат конечных полей используется для решения задач синтеза вероятностных автоматов и генераторов случайных двоичных последовательностей, для моделирования случайных линейных зависимых процессов в конечном поле и некоторых типов ЦМ (Аблаев Ф М, Бухараев Р Г, Гавел Я, Кирьянов Б Ф, Кознов Ф В, Крашенинников В Р, Кузнецов ВМ, Латьшов Р X, Мансуров РМ, Осмоловский CA, Песошин В А, Столов ЕЛ, Taylor L)

В работах Захарова ВМ, Нурутдинова I1LP, Соколова СЮ, Шалагина СВ (2000-2006 г г) предложен подход моделирования дискретных случайных процессов на полиномиальных моделях, описываемых полиномиальными функциями над полем GF(2") Полиномиальные функции рассматриваются как модели дискретных преобразователей цепей Маркова Разработаны методы представления полиномиальными функциями над полем GF(2") простых и сложных ЦМ и определенных функций однородных и неоднородных ЦМ. Задача представления решается как задача вычисления коэффициентов полиномов над полем GF(2") на основе заданных стохастических матриц Решена важная прикладная задача отображения полиномиальных моделей в однородные вычислительные среды, позволяющие реализовал, параллельные алгоритмы вычисления и проводить потоковые преобразования над «-мерными векторами при моделировании дискретных случайных процессов Однако, в этом направлении существуют недостаточно исследованные вопросы и нерешенные задачи, имеющие теоретическое и практическое значение

Для дальнейшего развития и повышения эффективности методов моделирования дискретных случайных процессов в конечном поле актуальным является исследование вопросов, связанных с повышением точности полиномиальных моделей, определением их свойств и вероятностных характеристик, расширением класса случайных последовательностей, представляемых полиномиальными функциями над полем GF(2") и конечным полем GF(qc) характеристики qc> 2, с получением оценок порядка поля в зависимости от точности задания закона цепи Маркова и структуры стохастических матриц, а также ряд других вопросов, связанных с построением (вычислением коэффициентов) и анализом полиномиальных функций над конечным полем

Объект исследования Модели и аналитические методы моделирования случайных последовательностей над конечным полем

Предмет исследования Полиномиальные модели, порождающие функции цепей Маркова в конечном поле, свойства и характеристики этого класса моделей

Научная задача Разработка новых аналитических методов построения полиномиальных функций и анализа свойств полиномиальных функций, порождающих случайные последовательности в конечном поле на основе стохастических матриц (СМ), с учетом структурных свойств СМ и точности задания

переходных вероятностей

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

Решение общей научной задачи и достижение поставленной цели связано с решением следующих задач

1 Разработка метода и алгоритмов представления стохастических матриц полиномиальными функциями над полем GF(2") Определение оценок порядка поля GF(2") с учетом точности задания элементов стохастических матриц

2 Разработка метода и алгоритмов моделирования расширенных цепей Маркова (РЦМ) полиномиальными функциями над полем GF(2") Определение порядка поля GF(2") с учетом структуры стохастической матрицы РЦМ

3 Разработка метода представления неразложимых стохастических матриц с заданной точностью полиномами минимальной степени над конечным полем GF^) характеристики qc> 2

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

5 Статистический анализ цепей Маркова по критерию линейной сложности последовательностей Исследование взаимосвязи эшропии неразложимых стохастических матриц с линейной сложностью реализаций цепей Маркова

6 Разработка комплекса методик и программ, реализующих предлагаемые методы и алгоритмы

Методы исследований Для решения поставленных задач использованы методы теории чисел, теории вероятностей, математической статистики, теории детерминированных и вероятностных автоматов, теории графов, аппарат конечных полей, линейной и полиномиальной алгебры, дискретной математики

Научная новизна работы и значимость результатов

- Новые метод и алгоритмы представления стохастических матриц с двоично-рациональными элементами полиномиальными функциями над полем GF(2"), с учетом точности задания переходных вероятностей Сформулированы и доказаны теоремы, обосновывающие метод

-Новые метод и алгоритмы получения и отображения закона расширенных цепей Маркова в полиномиальную функцию над полем GF(2") Сформулированы и доказаны теоремы, обосновывающие метод

- Новый метод представления стохастических матриц с заданной точностью и моделирования случайных последовательностей из класса неоднородных цепей Маркова полиномами минимальной степени над полем GF(<7C) характеристики qc > 2 Доказана теорема, устанавливающая линейную связь между точностью задания стохастической матрицы и величиной минимальной степени полинома

-Новый метод определения вероятностных характеристик случайных последовательностей из класса функций однородных цепей Маркова, порождаемых полиномиальными нелинейными динамическими моделями над полем GF(2") Доказаны теоремы, устанавливающие формулы для вычисления асимптотических вероятностных характеристик случайных последовательностей

-Методика исследования однородных простых и сложных цепей Маркова на основе критерия линейной сложности Сформулирован критерий нахождения дайн реализаций марковских последовательностей при заданной точности представления матриц цепей Маркова Определены стохастические зависимости линейной сложности реализаций цепей Маркова от этропии стохастических матриц

Достоверность результатов работы Основные полученные результаты сформулированы в виде теорем и утверждений, приведены их доказательства. Предложенные аналитические методы и алгоритмы обоснованы доказательством теорем Адекватность предложенных моделей подтверждается компьютерным моделированием и сравнением с известными результатами

Практическая значимость

- Решение задачи представления РЦМ полиномиальными функциями над полем ОР(2") расширяет класс дискретных случайных процессов, получаемых на полиномиальных моделях, и позволяет определить свойства данных процессов и стохастических матриц РЦМ

- Предложенные алгоритмы разложения СМ ЦМ на имплицирующий вектор (ИВ) и множество стохастических булевых матриц (СБМ) позволяют определить вычислительную и комбинационную сложности вероятностных автоматов, синтезируемых в некотором логическом базисе

- Полученные формулы определения предельного распределения вероятностей символов случайных последовательностей (СП), порождаемых полиномиальными нелинейными динамическими моделями дискрегаых преобразователей информации, и фундаментальная матрица для СМ позволяют на их основе получить ряд других характеристик СП, например, матрицу средних времен достижения, векторы предельных дисперсии и корреляции

- Метод моделирования СП на основе минимального полинома позволяет воспроизводить на линейных регистрах сдвига реализации ЦМ, расширить функциональное использование линейных регистров сдвига.

- Методика исследования линейной сложности (ЛС) марковских последовательностей расширяет класс задач применения ЛС, дает возможность моделировать ЦМ на основе линейных и нелинейных полиномов минимальных степеней, позволяет выявлять свойства ЛС марковских функций

- Комплекс программ, алгоритмов и методик является инструментальным средством для моделирования СП и исследования свойств полиномиальных функций над конечным полем

Результаты работы используются

- в подсистеме временного прогнозирования производственно-экономических показателей состояния предприятия (на базе разработанной в диссертации программной реализации математического аппарата числовых стохастических матриц), включенной в состав автоматизированного рабочего места менеджера предприятия, введенного в опытную эксплуатацию в ОАО "1СЬ-КПО ВС", г Казань (справка об использовании результатов),

- в учебном процессе кафедры Компьютерных систем (предыдущее название (до 2006 года) - Компьютерные системы и информационная безопасность) и кафедры Систем информационной безопасности КГТУ им А.Н Туполева в форме учебного

электронного пособия "Лабораторный практикум по вычислениям в конечных полях" (акт внедрения)

На защиту выносятся следующие результаты

-метод и алгоритмы определения закона и свойств РЦМ по СМ исходной простой ЦМ, теоремы, обосновывающие метод и алгоритмы,

- метод представления заданного закона РЦМ минимизированной автоматной моделью и полиномиальной функцией над полем ОР(2"), теоремы, обосновывающие метод и свойства стохастических матриц РЦМ,

- метод и алгоритмы разложения СМ ЦМ с двоично-рациональными элементами на ИВ и множество СБМ, теоремы, обосновывающие метод и алгоритмы,

-аналитический метод определения характеристик СП из класса функций однородных ЦМ, порождаемых полиномиальными нелинейными динамическими моделями над полем ОЕ(2"), теоремы, обосновывающие метод,

- статистический метод исследования однородных простых и сложных ЦМ на основе критерия ЛС,

- аналитический метод представления СМ с заданной точностью и моделирования СП из класса неоднородных ЦМ полиномами минимальной степени над полем 0¥(дс), теорема, обосновывающая метод,

- комплекс методик и программ, реализующий предложенные методы и алгоритмы

Апробация работы Основные результаты докладывались и обсуждались на следующих конференциях и семинарах Х-ХУ Всероссийские молодежные научные конференции "Туполевские чтения" (Казань, 2002-2007), Всероссийская научная конференция студентов и аспирантов (Таганрог, 2004), XIV Международная конференция "Проблемы теоретической кибернетики" (Пенза, 2005), Региональная научно-методическая конференция "Профессиональные компетенции в структуре модели современного инженера" (Нижнекамск, 2005), 6-ая Международная конференция молодых ученых и студентов (Самара, 2005), Международная научно-праюкческая конференция "Инфокоммуникационные технологам глобального информационного общества" (КазаньДЮ5), Региональная научно-методическая конференция "Информационная культура в системе подготовки будущего инженера" (Нижнекамск, 2006), Всероссийский семинар "Ситуационные исследования" (Казань, 2006), Региональная научно-техническая конференция по вопросам информатики, вычислительной техники и информационной безопасности (Казань, 2006), Региональная научно-практическая конференция "Наука и профессиональное образование" (Нижнекамск, 2007), 9-ый Международный семинар "Дискретная математика и ее приложения" (Москва, 2007), Всероссийская научная конференция студентов, аспирантов и молодых ученых "Наука, технологии, инновации" (Новосибирск, 2007), Республиканский научный семинар "Методы моделирования" при КГТУ им АН Туполева (Казань, 2004-2008)

Публикации Содержание работы опубликовано в 29 работах, включая 3 статьи, опубликованные в изданиях, входящих в перечень ВАК, 16 статей в других изданиях, 9 тезисов докладов и одну работу, зарегистрированную в отраслевом фонде алгоритмов и программ

Структура и объем диссертации Диссертационная работа состоит из введения

четырех глав, заключения и списка использованной литературы, включающего 250 наименований, изложена на 153 страницах машинописного текста, содержит 44 рисунка и 12 таблиц, приложение на 10 страницах

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы диссертации, дается определение цели и задач исследования, приводится перечень основных результатов, выносимых на защиту Дана структура диссертации

В первой главе "Связь цепей Маркова, вероятностных автоматов и полиномиальных функции в конечном поле" дан обзор результатов, определяющих связь ЦМ, вероятностных автоматов и полиномиальных моделей над полем GF(2") Вводятся известные понятия, теоремы и модели, необходимые для изложения решаемых задач Уточняется постановка задач

Связь цепей Маркова, вероятностных автоматов и полиномиальных функций над полем GF(2") определяется на основе представления СМ Р размера т*т линейной стохастической комбинацией ИВ и множества СБМ вида Р - qaB(a), (11) где 1<т2 -т+\ (для минимаксного алгориша), qa - элементы ИВ q, а = 0,1 -1,//"'-СБМ (авторы Бухараев Р Г, Габбасов Н 3, Gelcnbe S Е, Гиоргадзе А.Х, Davis АС, Захаров В М, Костромин Г Л, Кузнецов С Е, Метра И А, Паршенков НЛ, Поспелов ДА, Нурмеев HFL, Салимов ФЛ, Сачков ВЛ, Ченцов ВМ, Чирков МК, Шилкевич ТП и др) Размер ИВ зависит от алгориша разложения и определяет сложность автоматных моделей марковских функций и рассматриваемых полиномиальных моделей над GF(2")

В известных полиномиальных моделях, основанных на использовании полиномиальных функций

- от одной переменной g(y) = £ a[f)y', rf = 2" -1, а,(/), у е GF(2n) (12)

1=0

-от двух переменных ¡{x^Jj^a^x'q1 ,г{ =2" -\,a^\x,qeGF(2n) (13)

минимальный порядок поля GF(2") определяется из условия 2я > /

Пусть задана конечная простая ЦМ системой (SР, л()), (14)

где 5= {s,} - конечное множество состояний ЦМ, Р = (рч\ i,j = 0,/и -1 - СМ, /Т0 -вектор размера т начального распределения вероятностей состояний Величина U -дискретная случайная величина (ДСВ), принимающая конечное число значений хо, , jc^i с вероятностями из ИВ q = {q,} размера /, q,= 1

Теорема 1.1u Существуют такие ДСВ U и функция flx,q) (13) со случайным начальным значением и коэффициентами а\Р eGF(2"), что U может быть

преобразована Дг, q) в заданную ЦМ вида (14) Минимальный порядок поля GF(2") выбирается из условия 2" > /

'' Захаров В М, Нурутдинов Ш Р, Шалагин С В Полиномиальное представление цепей Маркова над полем Галуа//Вестник КГТУ им А_Н Туполева, 2001, №3 - С 27-31

Теорема 11 обосновывает полиномиальную модель (U,ßx, q)), (1 5)

где U - ДСВ со множеством значений {х,} с вероятностями из ИВ q ,ßx, q) - функция (13) со множеством {*,} значений переменной х и множеством {qj значений переменной q для моделирования ЦМ в поле GF(2"), i = 0,1-1, j = 0, от -1 Теорема определяет связь порядка поля с размерами матрицы Р Связь порядка поля GF(2") со структурой и точностью представления матриц Р является малоисследованной задачей (например, исследуемые в главе 2 разреженные матрицы РЦМ)

Дана постановка задачи представления ЦМ над конечным полем G¥(qc), основанная на понятии "линейная сложность" Данное понятие связано с понятием линейных рекуррентных последовательностей над конечным полем Исследования псевдослучайных и случайных последовательностей с помощью JIC имеют следующие направления разработка методов улучшения JIC периодических последовательностей, исследование качества случайных чисел в моделировании, применение алгоритма Берлекэмпа "решения ключевого уравнения над произвольным полем" доя кодирования информации, тестирование работоспособности цифровых схем, тестирование качества поточных шифров и исследование аналитической сложности генераторов чисел в крипгапогии (авторы Алферов А П, Берлекэмп Э, Иванов МЛ, Куракин В Л, Jansen С J, Klapper А, Massey J L,ReedsJA,RueppeIR A., Schaub T, Sloane NJA, Smeets B, Zong-duo Dai) В меньшей степени JIC исследована в теории моделирования марковских последовательностей (МП) над конечным полем

Во второй главе "Методы представления случайных последовательностей полиномиальными функциями над конечным полем" решаются задачи 1-3

В разделе 2.1 "Представление стохастических матриц полиномиальными функциями над полем GF(2") с учетом точности представления элементов матриц" предложен метод представления СМ с двоично-рациональными элементами полиномиальными функциями над полем GF(2") Метод основан на предложенных трех алгоритмах двоично-рационального разложения СМ на комбинацию ИВ и множества СБМ Получены оценки порядка поля GF(2") в зависимости от точности представления элементов СМ Доказаны теоремы, определяющие оценки вычислительной сложности (ВС) и размера / ИВ для предложенных алгоритмов

Рассмотрены следующие алгоритмы минимаксного и двоично-рациональною подходов разложения (11) матрицы Р алгоритм 1, использующий метод минимакса, предлагаемые алгоритмы 2-4, базирующиеся на двоично-рациональном представлении элементов матрицы Р, алгоритм 2 основан на методе двоично-рационального разложения матриц (Бухараев РГ, Захаров ВМ, 1978) Доказаны конечность предложенных алгоритмов и факт различия всех формируемых ими СЬМ Данные алгоритмы позволяют снизить ВС разложения (1 1) и получить точную оценку размера ИВ для заданных матриц и точности представления матриц В алгоритмах 3 и 4 отсутствуют ограничения на класс двоично-рациональных СМ, выявленных в алгоритме 2

Все элементы матриц Р рассматриваются в виде двоично-рациональной дроби с Ъ разрядами Используются следующие формы представления СБМ в виде квадратных бинарных матриц (способ 1) размера т*т и в виде векторов В — {Ь,} (способ 2)

размера т, i,b, = 0,m-l, где позиции элементов p,bt в матрицах Р задают позиции

равных единице элементов СБМ

Предложена модификация алгоритма 2 (алгоритм 2м), позволяющая снизить ВС со значения 0{гпЬг) до 0(т3Ь2) при хранении СБМ способом 2 и исключении операции сравнения получаемых СБМ с ранее найденными.

Пусть Р (т, Ь) - класс СМ с двоично-рациональными элементами, представленными с точностью е = 2ь

Теорема 2.1 Алгоритм 2 для класса матриц Р (т, Ь) не результативен (не создается искомый ИВ), если матрица Р еР(т, b\ Р = (ру), i,j = 0, т -1, обладает одним из следующих свойств

1)3£ = 0,6-1, для которого не выполняется равенство Z"~ocojk = = Е^Чт-чд ,гдезначение¿-горазрядар,, i = 0,m-l,

2)3^=1,где i,j = Q,m-\

Показано, что задача вычисления размера / ИВ для алгоритма 2 сводится к задаче нахождения экстремума числа двоичных единиц в разрядах элементов по строкам матрицы Р

Теорема 2.2 Размер I ИВ, получаемого при разложении (11) матрицы Р по алгоритму 2, определяется условиями

В алгоритме 3 координаты единичных элементов СБМ задаются координатами выбранных последовательно по одному из каждой строки, при минимальном у, элементов pv>0 матрицы Р, i, j = 0, т -1, а каждый элемент ИВ равен l6

Предложен алгоритм 4, обладающий следующими особенностями

- устраняются ограничения (теорема 2 1) на класс матриц алгоритма 2,

- его ВС минимальна для обоих подходов и зависит cum ab,

- дает точную оценку параметра / для конкретной матрицы Р

Алгоритм 4 состоит из следующих пунктов

1 Из исходной матрицы Р формируются матрицы i^k)~(w(yk>\ = 0,2t+l,

i,j = 0,т-1, £ = 0,6-1, по правилу при р9 = 1, то w^=2, иначе w^ =Сф Необходимый объем памяти для матриц tt*® равен n?b{b +\у2 бит

2 При не соблюдении условия d= 0, ^ = nun XJ'o'

к = 0,6 - 2, значения d любых элементов w^ > 0 с удвоением переносятся в соответствующие элементы матрицы так как справедливо равенство

1/2° = где а - натуральное число

3 Текущая СБМ

для V/t = 0,b -1 формируется из элементов > 0 матрицы при минимальном j Осуществляется проверка повторения матрицы if* в матрицах j = к + 1,6-1 При получении iP в И® к qt добавляется

nun w^L 2 (;+1), иначе в ИВ q добавляется элемент q, = nun w(*L 1 (i+1) os/sm-1 lf>. OSiSm-1

Теорема 23 Размер / ИВ, получаемого при разложении (11) матрицы Р по алгоритму 4, определяется условиями

,(*) ^m-i^ii-i (Jt) , [ 2</<26,при/и£2*

'1,=о£ы>Ч )=со^.и , (21)

J ' -т + 1,при/и<2

где ,/ = 0,/и -1 - элемента матриц полученные к пунюу 3 алгоритма

Параметры ВС и / (таблица) алгоритмов двоично-рационального подхода зависят не только от размера т и энтропии Н(Р) матриц Р, как в минимаксном подходе, но и от числа разрядов b представления элементов Размер / ИВ для алгоритма 4 при ¿-const с ростом размера т матриц увеличивается, а при достижении соотношения тг - т +1 > 2Ь становится константой Уменьшение ВС в рассматриваемых алгоритмах осуществляется за счет последовательного выбора элементов из строк, представления СБМ в виде вектора чисел и исключения сравнения полученных СБМ с ранее найденными, снижения точности представления элементов матрицы Р Например, вычислительная сложность снижается от 6561 (алгоритм 1) операций к 5652 (алгоритм 4) для СМ размера 9x9 и при числе двоичных разрядов Ь = 4 представления элементов

Алгоритм Оценка ВС Оценка /

алгоритм 1 0(т4) известные оценки 1 ^ / 2 т2 - т + 1 и (2 2) a^ - число ненулевых элементов в строке /

алгоритм 2 0(тАЬ3) {2<1<тг -т + \,прит<2ь

алгоритм 2м 0(т3Ь2)

алгоритм 3 0(т3) \<,1йтг-т+\

алгоритм 4 (соавторство с Нурмеевым НН) 0(тЬ(ПтЩ) 1-0,т-\, и | 2^/<24,прит>2ь \2<,1<,т2 -т + \,прит<2ь

Теорема1А Порядок п поля ОЕ(Т) в системе (15) для класса СМ ?{т,Ь), представленных в виде (11) по алгоритму 4, определяется из условия 2" > тах(1, т), где / - размер ИВ, удовлетворяющего условию (21)

Опишем метод представления СМ с двоично-рациональными элементами полиномиальными функциями над полем ОР(2"), с учетом точности задания переход ных вероятностей

1 Выполняется разложение (1 1) матрицы Г с помощью алгоритма 4 на ИВ ¿¡г и множество СБМ Размер ИВ ц удовлетворяет условию теоремы 2 3

2 ИВ д и множество СБМ преобразуются в автоматную таблицу конечного

детерминированного автомата (КДА)

3 По автоматной таблице вычисляется функция ц) вида (13) над полем ОР(2"), порядок которого определяется теоремой 2 4

Шаги метода детально описаны в диссертации, в главе 4 В разделе 2.2 "Представление расширенных цепей Маркова над полем ОЩ")" решены задачи синтеза и анализа модели расширенных цепей Маркова над полем СР(2") Доказана теорема (2 5), обосновывающая алгоритм вычисления закона РЦМ по заданной СМ исходной простой ЦМ Предложен метод (теоремы 2 5,2 7,2 8) представления заданного стохастического закона РЦМ в определенную полиномиальную функцию над полем ОЩ") Предложены полиномиальные модели РЦМ, определены свойства структуры матрицы РЦМ (в частности, теорема 2 6 и следствие 2 1) Определены оценки размера ИВ, получаемого при разложении (1 1) матрицы РЦМ, исходя из результатов раздела 21 Получены оценки порядка поля ОР(2")

Пусть задана последовательность состояний ь 2, простой однородной ЦМ с конечным множеством состояний 5= и матрицей Р-(ру) размера т*т, г,) =0,т - 1 Составим цепочки символов ^длины /•= у + к> 2, у> 1, к> 0, имеющие вид (5)1, , ,SJr^г) Смежные цепочки, содержащиек = г-у общих символов

и V отличающихся символов, будем рассматривать как один шаг перехода

расширенной ЦМ с /я"** состояниями Д, / = 0,т"*к -1, определяемой матрицей <2 размера /яvhrx^иv,* Определим матрицу <2 РЦМ (задача анализа) через матрицу Р исходной ЦМ при у >2, к>2 Пусть Е и - единичные матрица и вектор-столбец размеров тГ2*ггГ2 и т соответственно, ® - символ операции кронекерово произведения матриц, С = |#0 5m.il - матрица размера т^т2, являющаяся последовательной конкатенацией матриц = /,_/,а = 0,т-1, где

6о)=К.еслиа = / \ 0, если а * I

Замечание2.1 Пусть дана матрица Р=(ру), I,] = 0,т-1 Тогда по формуле Иг=<Цт®Е®С определяется "промежуточная" стохастическая матрица И/=(н,а/), с, с1 = 0, т г -1, размера т^^гп**, на основе которой вычисляется матрица Q

Утверждение2.1 Пусть дана матрица Р-(ру), Ур9>О, I,] = 0,/л-1, и на ее

основе получена матрица IV = (м^), а,с1 = 0,тг -1, с цепочками длины г = у + а:, V > 1, к> 1 Тогда для IV = (м^) , , Чу/У > О

у У 'т хт 00

Теорема2.5 Пусть - у-я степень матрицы Ш, у> 1, к>0 Тогда переходная матрица {2 РЦМ вида

равна (2.4)

Теорема 2.6 Пусть дана матрица Р=(ру), Мру > 0, ¡, ] = 0, т -1, и на ее основе получена матрица <2 РЦМ размера т'у-т, г=у + к>2, у>1, к>0 Тогда РЦМ -эргодическая

Следствие2.1 Пусть дана матрица Р~(р9) ЦМ, и 3р9 = 0, г,_/ = 0,/и — 1, на основе Р получена матрица <2 РЦМ размера тг*тг, г>2, у> 1, к> О Тогда РЦМ не является эргодической

Утверждение 2.2 Если РИМ, заданная матрицей <2 размера тг*тг, с длиной цепочек г = V + к, образована матрицей Р с одинаковыми строками, то данная цепь является цепью Маркова-Брунса

Предложен алгоритм вычисления матрицы <2 РЦМ по матрице Р Исходные данные матрица Р размера тхт, переменные к, v, г>2 Результат вычислений матрица <2 размера тгхп{

1 Вычисляются ненулевые элементы матрицы IV по формуле

=Л= = М = (2 5)

где / - текущий номер строки матрицы IV, с/-текущий номер столбца Р

2 Вычисляется соотношение (2 4)

Поставим в соответствие матрице <2 размера тгшг полиномиальную модель (15) - (£/, _Цх, где/л, ц) - функция (1 3), принимающая тг значений, переменные х и ц принимают соответственно 1тлтг значений

Структурная схема построенной автоматной модели (1 5) для РЦМ представлена на рис 2 1 (рис 2 2 - схема полиномиальной модели (1 5)), где Г - генератор ДСВ (/, М -

КДА, со множеством состояний Ар у = 0, тг -1, входным алфавитом {х0, , хц} и функцией переходов, полученной по £)

Утверждение 23 Пусть задана матрица (5 РЦМ размера т"тг, г>7 Тогда для ИВ д матрицы £), получаемого по минимаксному алгоритму, с учетом числа ненулевых элементов, размер / лежит в диапазоне

т'<1<тг~тк+1 (2 6)

С учетом структуры СМ РЦМ, порядок поля, необходимого для построения полиномиальной модели РЦМ, был снижен с (тг)2 к тг

Теорема 2.7 Пусть задана матрица <2 РЦМ размера тгхт\ г> 2 Тогда порядок поля СР(2") для модели (1 5) определяется из условия 2">тг, где п - наименьшее целое

Учитывая разреженность матриц РЦМ осуществим синтез автоматной модели РЦМ на основе принципа приведения множества состояний А)

Теорема 2.8 Алгоритм /-эквивалентных разбиений сводит число Л состояний автоматной модели РЦМ, заданной матрицей 2, к значению т

Схема построенной автоматной модели РЦМ изображена на рис 2 3 (рис 24-полиномиальная модель) Блок 1 - КДА с множеством состояний приведенного автомата, ус - состояние КДА Блок 2 - Г для моделирования системы из т случайных величин Елок 3 - регистр сдвига (РС), образующий цепочки 1С символов 5, 6 5 длины

V, /=0,т-1 Цепочки из х, образуют текущее состояние А, РЦМ, J =0 ,тг -1

Теорема 2.9 Пусть задана РЦМ матрицей 0 размера тгхтг и параметрами V, к Тогда последовательность состояний РЦМ представляется последовательностью значений функции у =_/2х/1 - суперпозиции полиномов вида (1 3) над полем С¥(2"), где п - наименьшее целое, удовлетворяющее условию 2" > /, а / удовлетворяет неравенству (2 6)

Т.

Бг

РС

КДА 1

Й

х' = гс 1 Я* ',<?) = ? ? = Уг и'1* г

Я

Рис 2 3

к

Рис 24

Теорема 2 9 дает следующий метод построения полиномиальной модели над полем СР(2") для моделирования РЦМ

1 Вычисляется матрица (2 РЦМ по алгоритму (раздел 2 2)

2 По матрице Q задается автоматная модель, представленная на рис 2 3

3 По автоматной модели определяется функция >{/=/2хЯ и строится полиномиальная модель, представленная на рис 2 4, где блоки 1 и 3 соответствуют блокам 1 и 3 автоматной модели, а блок 2 моделирует ДСВ с числом значений / из (26)

В разделе 2.3 "Моделирование случайных последовательностей минимальными полиномами над конечным полем по заданной стохастической матрице" предложен метод моделирования случайных последовательностей из класса неоднородных ЦМ над полем СР(дс), где дс>2 - простое число Предлагаемый метод позволяет по заданной матрице Р получать семейство реализаций СП фиксированной длины на основе минимальных полиномов (полиномов минимальной степени) над полем СР(<7с), доказана теорема, обосновывающая метод

Пусть заданы Р = (р9), /,_/ = 0, т -1, и я - (щ, , я^) - предельный вектор для Р, р = - последовательность длины N в алфавите обладающую

следующими свойствами для любого / буква sl входит а, > 1 раз в <р, буква следует ац > 0 раз за х, (и за ц следует .<;, О, вьшолняются

(2 7)

С (р свяжем неразложимую матрицу Р„ = ( р',^), р^ = ач ¡а,,

Ч

<р свяжем неразложимую матрицу удовлетворяющую (2 7), и предельный вектор я^

Положим 1) точность приближения матрицы Р = (ру) матрицей Р9 = { ),

\<,е, 0<г< 1, 2) длина N

I,] = 0,т -1, удовлетворяет условию | - рч, последовательности <р определяется из условия N>1/, I/ - максимальное из шах (рия,)~1 и П1ах(1 + р +е)1(л1е) Требуется построить минимальный

полином Дх) над вырабатывающий последовательность длины

Матрица Рг, соответствующая должна с заданной величиной е>0

аппроксимировать исходную матрицу Р

Георама 2.10 Пусть заданы неразложимая СМ размера тхт и числа

0<е<1, N>1/ Тогда существует минимальный полином Д*) над полем СР((/с),

вырабатывающий последовательность длины N'+1 с законом Р9 = (р\^)) который удовлетворяет условиям

|ЛГ'-ЛГ|£т-1, (28)

. í если п., = 0 -

1 И * =|>0,если рч >0' = (29)

+ (2 10) и степень полинома Дх) удовлетворяет условию 2Ь<Ы' + 1

Следствие 2.2 (из теоремы 2 10) Число последовательностей ы^чъ полученных по матрице Рг размера и удовлетворяющих условиям (2 8)-(2 10) теоремы 2 10,

- х - I +1)/2,если-нечетное, ограничено сверху величинои т , где Ь = <

[((Лг +1) + 1)/2,еслиЛг - четное

е,(2 8)-(210) N и,И'

----Р,--->--р--->---Л*), Ь--->----их.+,

Алгоритм Алгоритм Алгоритм Генерация СП

получения выделения Берлекэмпа- линейным

матрицы Рг эйлеровой цепи, Месси(АБМ) регистром

с использованием сдвига (ЛРС)

источника Рис 2 5 случайности

Представим на рис 2 5 метод моделирования СП на основе полинома Лх) входные параметры, необходимые для преобразований, надписаны в верхней части, величины, над которыми выполняются преобразования - посередине, известные алгоритмы, выполняющие преобразования - внизу

Благодаря алгоритму получения матрицы Рг, ¡щя аппроксимации исходном матрицы Р с заданной точностью необходима реализация ЦМ длиной не в Ы2 символов, а в N

Третья глава "Методы анализа полиномиальных функций, моделирующих случайные последовательности в конечном поле", состоит из двух разделов, в которых исследуются свойства полиномиальных нелинейных динамических моделей преобразователей функций ЦМ и линейной сложности МП (решаются задачи 4,5)

В разделе 3.1 "Анализ нелинейных моделей преобразователей случайных последовательностей над полем ОР(2") на основе стохастических матриц" решена задача анализа полиномиальных нелинейных динамических моделей (ПНДМ) над полем ОР(2"), порождающих случайные последовательности (СП) из класса функций конечных однородных ЦМ Задача анализа состоит в определении характеристик СП Основными определяемыми характеристиками являются стохастические векторы, характеризующие асимптотику распределений вероятностей символов СП Доказаны теоремы, обосновывающие аналитическое определение искомых характеристик СП Для четырех последовательно усложняемых ПНДМ, описывающих классы СП, определены их полиномиальные функции над полем СР(2") и структурные схемы

Определение базовых полиномиальных функций над полем СР(2") Введем в рассмотрение ЦМ, заданную системой (14), и полиномиальные функции ¿¿у) (1 2) и Xх, Я) (1 3) над полем СР(2"), значения этих функций обозначим соответственно /?и а.

и1 x{t) л*®, m a(f+1)

4(0 КО | о

Рис 3 1

а, р б GF(2") Поставим в соответствие матрице Р полиномиальную модель (1 5) - ((/, fix, q)), где fix, q) - функция (1 3), принимающая m значений, а переменные х и q -соответственно /йот значений

Утверждение 3.1 Порядок паля GF(2") в (15) определяется из условия 2">/,, где п - наименьшее целое, а 1\ - размер ИВ для матриц Р, у которых Зр9-0, определяемый условием (2 3)

Полиномиальные нелинейные динамические модели, порождающие функции цепей Маркова

1 Зададим следующие ограничения на систему (1 5)

1) Пусть значение a(f+l) функцииq), полученное в момент времени f+1, есть состояние ЦМ, определяемое переменными x(t) и q(t) = а(/) во время f

2) Значите q в момент t=О определяется вектором ж0

При этих ограничениях системе (1 5) соответствует ПНДМ над полем GF(2") вида (С/,a(i+l) =Ж0,Ш Щ>) (31)

Последовательность значений fix(t),q(t)) в системе (3 1) в моменш /=1,2, является простой однородной ЦМ, определяемой Р и л0 На структурной схеме модели (3 1) (рис 3 1) функциональное назначение блоков 1, 2 соответствует системе (3 1), блок 1 - генератор ДСВ U, блок D - элемент задержки на единицу времени / = 1 Пусть Pa(t) =(д,,(0) - вектор распределения вероятностей значений /(х(<), <ï(0) ДДя времени f, ж - предельный вектор эргодической ЦМ.

Теорема 3.1 Для СП, порождаемой моделью (3 1)

Ya{t) = V0P' = ^ЛХЛ W +1) = Pâif)Р »хР-х (32)

2 Разобьем множество S системы (14) на непересекающиеся подмножества

Со. . CV" "0CJ СаПСг0,афМ a,j = 0,h, -1, (33)

ивьшсипшм отображение /j(s) S—>Bt= , (3 4)

где Bt={b\')} - функция конечной ЦМ с h, значениями, определяемая условием

б,1'' =j, если в момент времени t ЦМ находится в каком-либо состоянии s, подмножества Ср i = 0,т -1

По аналогии с (3 1) функцию В, будем моделировал, над полем GF(2") ПНДМ вида. (и, m(t+i)=g0</+ 1))Ж0, Ш (3 5)

где 2" > l\, q(t) = ait), функция g(K'+l)) реализует отображение fis), щ - суперпозиция функций fix, q) и g(y), последовательность значений Р функции щ в моменш f представляет функцию В,

Пусть Pp(t) =(рд(0) и Рр ' вектор и предельный вектор распределения вероятностей значений р функции ул(<) Зададим бинарную матрицу Л = (АД где А, = 1, если 5, eQ,i = 0 ,т -1, j = 0 ,hs -1

Теорема3.2 Для ПНДМ (3 5), заданной системой ((1 4), (3 4)) = (5, Р, В,, //.у), я0), векторы Рр{0 и Рр вычисляются по формулам

Тр(1) = щР'А = £(/)Л пРр=л\ (36)

На систему (3 5) наложим следующие ограничения

аО /¿//определяет порядок поля, а функции соответствует матрица

коэффициентов {а(цл), а[р е ОР(2"), I,] = 0,/у

а2)ЗаданыДСВ (/сИВ </ размера/,/<г/,ивектор л-„ размера/и аз) Переменная * и функция Дх, </) принимают соответственно / и т значений, а множества значений q(f), а и совпадают а*) Функция ^у) реализует отображение

Следствие 3.1 Пусть задана система (3 5) с ограничениями аО-а*) Тогда для нее однозначно определяются матрица Р, векторы

7^(0=Т0р',(0 = Ра(1)\ иТр = х\ (3 7)

3 Зададим функцию ЦМ системой ((14), 1, Дг/5)), _(3 8)

где функция Дг/л) задается матрицей Р[г/5) = {Р(:,и1)\ ' = 0,от-1, у = 0,| 21 -1, а

элемент р^,) определяет вероятность появления буквы при состоянии л, Системе (3 8), по теореме 3 2, поставим в соответствие ПНДМ

(.и, и, 1) =/2№1),д'('+1)]/1[х(0>9(0], я'о), (3 9)

где 2"> тах(/ь /2), /2 - размер ИВ, полученного при разложении матрицы Р^), (/и {/ ДСВ, определяемые по разложению (11) матриц Р и Р^), щ^+Х) - задает процесс 2, и является суперпозицией функций^ и/ ввда (1 3) иРг - вектор и предельный вектор распределения вероятностей значений у/2(г)

Следствие 3.2 Если в системе (3 8) ЦМ - эргодическая, то для модели (3 9), заданной по системе (3 8), векторы Р2(1) и Р2 вычисляются по формулам

Тг(0 = ЩР'Р^и) и ~Р,= я*},,,, (310)

Рассмотрим систему (3 9) при следующих ограничениях

С]) Пусть заданы вектор л0 , ДСВ I] и (/', состоящие соответственно из А и /2 значений

Сг) Заданы порядок п поля ОР(2") из условия 2" > тах(1и /2) и матрицы коэффициентов для/\(х, ф иДУ, </)

сз) Задано ограничение аз) на функцию/¡(х, д)

й) Переменная у! ъ/г(з?, 4) и функция /г(х!, принимают соответственно /2 и \2\ значений, а множества значений </(() и/¡(х, д) совпадают

Следствие 3.3 Пусть задана система (3 9) с ограничениями с^ - С4) Тогда для процесса 2, однозначно определяются матрицы Р и Ру5р вектор Рг{() (3 10) и, если полученная ЦМ является эргодической, то и вектор Рг (3 10)

4 Введем систему М/ь(1) вида М^ = ((1 4), (3 4), 2, /Хг/Ь(')\ (311)

где/Хг///") задается матрицей Р(г/4,0) = (^¿со,). ' = -1, 7 =0,| 21-1, а Р (0)

определяет вероятность появления буквы 1;е2ат буквы ¿>,(<>

Заданную системой (311) функцию ЦМ можно моделировать ПНДМ вида

(£/, V, щ{1+\) =/2[;С(/+1), <7'('+1)] Н'+Ъ Ч \ (3 12)

где у/3,(1) - суперпозиция функций^ и щ, а последовательность значений функции у/3(г) задает процесс 2', (рис 3 2 - структурная схема модели (3 12))

Пусть Р1/Ь(о(0 и Р11Ь<» ' вектор и предельный вектор распределения вероятностей значений у/3(0

Следствие 3.4 Для модели (3 12), заданной по системе (3 11), векторы Р (0 (/) и равны Р^(0 = ^Р'М\г!ь1Л) и = лАР(!/ь[1)) . (3 13)

Совокупность формул (3 2), (3 6), (3 7), (3 10), (3 13), определяемых теоремами (3 1, 3 2) и следствиями (3 1-3 4), образует метод вычисления характеристик ПНДМ вида (3 1), (3 5), (3 9) и (3 12) над полем ОР(2"), порождающих СП из класса функций ЦМ

В разделе 3.2 "Статистический анализ линейной сложности регулярных цепей Маркова" предложен метод статистического анализа однородных простых и сложных ЦМ по критерию ЛС (с использованием результатов раздела 2 3) Определены статистические критерии нахождения необходимых для исследования ЛС длин реализаций МП при заданной точности представления СМ, рассмотрены их отличия и особенности Показана взаимосвязь ЛС и энтропии СМ определены оценки математического ожидания М(ЩС)) и дисперсии ЩЩС)) МП, моделируемых по заданным матрице Р и энтропии Н(Р), где Ц1С) - значение ЛС МП длины 1С, определены оценки М(Щс)) и ¡ХЦ1С)), характеризующие подклассы МП с определенной величиной Я(Р), определен профиль ЛС МП

ЛС линейной рекуррентной последовательности (ЛРП) определяет минимальную длину ЛРС, реализующего данную последовательность Алгоритмом вычисления ЛС заданной ЛРП и нахождения полинома Xх) является АБМ Функция Щ) называется профилем ЛС последовательности и, где Щ) задает ЛС последовательности « = , ¿,-1) для V/ =

Пусть у ЦМ с алфавитом состояний 5 стохастическая матрица Р = (рв) размера тут (тГхтг - для г-сложных ЦМ) принадлежит классу регулярных матриц Мк, предельный вектор я, матрица частот /", вектор соответствуют

обозначениям к, Рг и ягр раздела 2 3 Опишем метод статистического анализа

однородных простых и сложных ЦМ по критерию ЛС

1 Строятся матрицы Р еМя методом статистического моделирования при

условиях сшхастичноста по строкам, регулярности СМ и соответствия Р одной из трех, равных по величине, групп энтропии Н,(Р), i = 1,3

2 Вычисляется точность е отображения свойств исходной ЦМ реализацией ЦМ из условия 2(1 -%f<£ (314)

Выражение (3 14) вытекает из неравенства Бершгейна | р^ - л, | < 2(1 - X)d, где Л = min рх., рf - вероятность перехода ЦМ в состояние s, е S за d шагов, d=l,2,

3 Параллельно со статистическим моделированием реализаций ЦМ определяется 4, с остановкой при выполнении \ц, - а,/Ц < е, V/ = 0, т -1, (3 15) - критерия, задающего длины /с=2м)1а' последовательностей, достаточных для отображения с точностью е свойств ЦМ, и отражающего закономерности и предельные свойства Р Для реализации ЦМ вычисляется ее ЛС (с помощью АБМ) и строится профиль ЛС

4 В пункте 3 генерируются реализации ЦМ, число которых соответствует заданному уровню точности, и по ним вычисляются оценки M(L(lc)) и ДД/С)), строятся плотность и функция распределения величины Щс)

ВС АБМ для двоичной последовательности длины 1С составляет оценку 0(/') Правильность работы программной реализации метода анализа проверялась на основе анализа следующих последовательностей псевдослучайных двоичных, полученных на ЛРС, случайных чисел, реализаций ЦМ при Н„ЛР), полученных аффинными преобразованиями

Для простых и сложных ЦМ получены следующие оценки (по критерию (3 15)), близкие к случайным последовательностям с равномерным распределением M(L(lc)) 1С/2 + со, w < 1 - коэффициент,

ДЦ/с)) 86/81 приН{Р) <= [0,5 Я4Р), 0,9 Н^Р)] и Н^Р) = logгт, распределение случайной величины ЛС с ростом объема выборки стремится к нормальному закону

Показано, что среди сложных и простых ЦМ, матрицы которых равны, ЛС больше у сложных ЦМ из-за избыточности двоичного кодирования состояний ЛС зависит от ЩР) и не зависит от т Если на данном этапе построения профиля ЛС наблюдается горизонтальный тренд, то изменяется/-*) без увеличения L или для АБМ являются предсказуемыми символы последовательности Значение ЛС растет при повторе символов последовательности, не начинающихся с начала последовательности Полученные оценки ЛС ЦМ могут служить оценками необходимой величины минимальной степени полинома при моделировании ЦМ над полем GF(<fc) (раздел 2 3)

В четвертой главе "Комплекс методик и программ для решения задач построения и анализа полиномиальных функций и моделирования случайных последовательностей" описывается разработанный комплекс методик и программ, реализующий методы и алгоритмы, предложенные в диссертации Комплекс позволяет решать следующие задачи преобразование закона цепи Маркова в полиномиальную модель с использованием двоично-рационального разложения СМ и

представление марковских функций полиномиальными моделями, тестирование предложенных полиномиальных моделей, получение закона расширенной цепи Маркова, исследование характеристик марковских и псевдомарковских циклических последовательностей с помощью АБМ

Основные результаты работы

1 Разработан новый метод моделирования расширенных цепей Маркова в поле СР(2"), основанный на предложенном методе определения закона расширенной цепи Маркова по заданной стохастической матрице простой цепи Маркова. Доказаны теоремы, устанавливающие новые свойства (структурные, асимптотические) стохастических матриц расширенных цепей Маркова и оценки минимального порядка поля ОЩ") для представления расширенных цепей Маркова полиномиальными функциями

2 Предложены новые алгоритмы разложения двоично-рациональных стохастических матриц на имплицирующий вектор и множество стохастических булевых матриц, позволяющие снизить вычислительную сложность разложения и получил, точную оценку размера имплицирующего вектора и порядка поля СР(2") для описания полиномиальных функций Доказаны теоремы, обосновывающие алгоритмы и оценки

3 Предложен новый метод моделирования случайных последовательностей фиксированной длины N из класса неоднородных цепей Маркова, заданных стохастическими матрицами, на основе полиномов минимальной степени над конечным полем С¥(дс), ^с>2, позволяющий повысить точность представления стохастических матриц полиномами пропорционально величине Доказана теорема, устанавливающая существование минимальных полиномов для представления стохастических матриц с заданной точностью

4 Сформулированы и доказаны теоремы, составляющие основу предложенного аналитического метода вычисления характеристик полиномиальных нелинейных динамических моделей над полем ОР(2п), порождающих случайные последовательности из класса функций конечных однородных цепей Маркова

5 Предложена новая методика статистического анализа однородных простых и сложных цепей Маркова по критерию линейной сложности Статистическим моделированием получены оценки линейной сложности реализаций цепей Маркова.

6 Разработан комплекс методик и программ, реализующий предложенные методы и алгоритмы

Список публикац ий по теме диссертации

I Статьи по теме диссертации, опубликованные в журналах из перечня ВАК.

1 Захаров В М., Эминов Б Ф Анализ нелинейных моделей преобразователей случайных последовательностей над полем СР(2?) на основе стохастических матриц // Вестник Казанского государственного технического университета им АН. Туполева - Казань КГТУ им АН Туполева,2006,№3 -С 41-46

2 Эминов БФ Метод моделирования случайных последовательностей класса неоднородных цепей Маркова полиномами минимальной степени над полем ОР(<7) // Системы управления и информационные технологии. Вып. 4 1(30) - Воронеж Изд-во "Научнаякнига",2007 -С 203-207

3 Захаров ВМ., Эминов БФ Анализ алгоритмов разложения двоично-рациональных

стохастических матриц на комбинацию булевых матриц // Информационные технологии, №3 - M Изд-во Новые технологии, 2008 - С 54-59

П Статьи в сборниках и материалах научно-технических конференций.

4 Эминов Б Ф К задаче анализа полиномиальных моделей автономных вероятностных автоматов // XII Туполевские чтения Международная молодежная научная конференция ТомЗ -Казань КГТУим АН Туполева,2004 -С 60-62

5 Захаров В M, Эминов Б Ф Автоматное моделирование расширенных цепей Маркова // Актуальные проблемы современной науки Труды 1-го Международного форума молодых ученых и студентов Ч. 18 -Самара Изд-во Самар roc техн ун-та, 2005 - С 146-148

6 Эминов Б Ф Программный комплекс обучающих средств "Основы криптографической защиты информации" // Прикладная информатика - 2004 Доклады факультетской научно-технической конференции.-Казань КГТУим АН Туполева,2005 - С 84-88

7 Эминов Б Ф Анализ полиномиальных моделей автономных вероятностных автоматов // Прикладная информатика - 2004 Доклады факультетской научно-технической конференции -Казань КГТУим АН Туполева,2005 -С 3640

8 Дьячков В В, Эминов БФ Временное прогнозирование функционирования предприятия на нейронных сетях // Информационная культура в системе подготовки будущего инженера Материалы региональной научно-методической конференции, Нижнекамск. - Казань КГТУ им АН Туполева, 2006 - С 64-66

9 Эминов Б Ф Построение имплицирующего вектора на основе двоично-рационального представления элементов стохастических матриц // Информационная культура в системе подготовки будущего инженера Материалы региональной научно-методической конференции, Нижнекамск. - Казань КГТУ им. А H Туполева, 2006 - С 222-224

10 Эминов БФ Модели сшуационнош управления как инструмент познания // Всероссийский семинар Ситуационные исследования выл 2 Типология ситуаций//Под ред H M Ссшодухо - Казань КГТУ имАН Туполева, 2006 - С 84-94

11 Эминов Б Ф Минимизация автоматной модели расширенной цепи Маркова методом /эквивалентных преобразований/УХТУ Туполевские чтения Международная молодежная науч конференциями 4 -Казань КГТУ им АН Туполева,2006 -С 74-76

12 Захаров В М, Эминов Б Ф Статистический анализ линейной сложности регулярных цепей Маркова // Исследования по информатике Выпуск 10 ИЛИ АН РТ -Казань Отечество,2006 -С 37-50

13 Эминов БФ Влияние точности представления двоично-рациональных элементов стохастических матриц на размер имплицирующего вектора // Научно-техническая конференция по вопросам информатики, вычислительной техники и информационной безопасности.-Казань КГТУим АН Туполева,2006 - С 122-125

14 Эминов Б Ф Получение стохастической матрицы расширенной цепи Маркова/УНаука и профессиональное образование Материалы региональной научно-практической конференции, Нижнекамск,- Казань КГТУ им АН Туполева, 2007 -С 225-230

15 Захаров ВМ., Эминов БФ Представление расширенных цепей Маркова над полем GF(2") // Моделирование процессов Труда Казанского научного семинара "Методы моделирования" Вып.3 - Казань КГТУ им. А H Туполева, 2007 - С 270-286

16 Эминов БФ Моделирование случайных последовательностей минимальными полиномами над конечным полем по заданной стохастической матрице // Информационнные технологии моделирования и управления Научно-технический журнал Выл 7 (41) -Воронеж Изд-во Научная книга, 2007 - С 811-818

17 Эминов БФ Применение алгоритма Берлекемпа-Месси к синтезу и анализу рекуррентных двоичных последовательностей//ХУ Туполевские чтения Международная

молодежная науч конф Том 3 -Казань Kl "ГУ им.А.H Туполева.2007 -С 90-92.

18 Эминов Б Ф Вычислительная сложность и имплицирующий вектор стохастических матриц с двоично-рациональными элементами // XV Туполевские чтения Международная молодежная научная конференция. Том 3 - Казань КГТУ им. АН Туполева, 2007 - С 87-90

19 Эминов БФ Представление стохастических неразложимых матриц с заданной точностью минимальными полиномами над конечным полем // Наука, технологии, инновации Материалы всероссийской научной конференции молодых ученых. Часть 1 -Новосибирск. Изд-воНГТУ, 2007 - С 107-109

Ш. Тезисы в сборниках и материалах научно-технических конференций.

20 Соколов С Ю, Шамсетдинов M И, Эминов Б Ф К задаче программной реализации вычисления произведения элементов поля Галуа // X Всероссийские Туполевские чтения студентов Том 2 - Казань КГТУ им А H Туполева, 2002 - С 32

21 Соколов СЮ, Эминов БФ К задаче программной реализации полиномиальной модели конечного детерминированного автомата // XI Туполевские чтения Всероссийская молодежная научная конференция ТомЗ -Казань КГТУ им. АН Туполева, 2003 -С 27

22 Эминов БФ Анализ линейной сложности эргодических цепей Маркова // Всероссийская научная конференция студентов и аспирантов - Таганрог Иэд-во Таганрогского гос радио-техн. ун-та, 2004 - С 242-243

23 Эминов Б Ф Программный комплекс обучающих средств "Основы криптографической защиты информации" // XII Туполевские чтения Международная молодежная научная конференция ТомЗ -Казань КГТУимАНТуполева,2004-С88-89

24 Эминов БФ Сравнительный анализ линейной сложности марковских и псевдомарковских последовательностей // ХП Туполевские чтения Международная молодежная научная конференция. Том 3 - Казань КГТУ имАН Туполева,2004 -С 62-63

25 Эминов Б Ф Программный комплекс лабораторного практикума дги вычислений в полях Галуа // Материалы региональной научно-методической конференции Профессиональные компетенции в структуре модели современного инженера. - Нижнекамск КГТУ им А H Туполева, 2005 -С 104-105

26 Захаров ВМ, Эминов БФ Статистический анализ линейной сложности цепных последовательностей из класса регулярных цепей Маркова // Инфокоммуникационные технологии глобального информационного общества Тезисы докладов 3-ей ежегодной международной научно-пракгаческой конференции. - Казань Иэд-во КГУ им В И Ульянова-Ленина,2005 -С 82-84

27 Эминов БФ Автоматный метод моделирования расширенных цепей Маркова // Туполевские чтения Международная молодежная научная конференция. Том 3 - Казань КГТУ им АН Туполева, 2005 - С 59-60

28 Захаров В M, Эминов Б Ф Статистические оценки линейной сложности марковских последовательностей по критерию этропии // Проблемы теоретической кибернетики Тезисы докладов XIV международной конференции. - M Изд-во механико-математического фак-та МГУ, 2005 -С 49

IV Работы, зарегистрированные в фонде алгоритмов и программ

29 Захаров В М, Эминов Б Ф Электронное учебное пособие "Лабораторный практикум вычислений в конечных полях" И Регистрация в отраслевом фонде алгоритмов и программ, № 10018 -М.2008

Формат 60x84 1/16 Бумага офсетная Печать офсетная Печл 1,25 Услпечл 1,16 Услкр-отт 1,16 Уч-издл 1,04 Тираж 100 Заказ Л 73

Типография Издательства Казанского государственного технического университета 420111, г Казань, К Маркса, 10

Основные условные обозначения

Сокращения, принятые в тексте

Введение

Глава 1. Связь цепей Маркова, вероятностных автоматов и полиномиальных функций в конечном поле

1.1. Связь цепей Маркова, вероятностных автоматов и полиномиальных функций

1.2. Базовые понятия и теоремы

1.2.1. Определения теории цепей Маркова

1.2.2. Определения теории конечных полей

1.2.3. Базовые полиномиальные модели для моделирования цепей Маркова и их функций в поле GF(2")

1.3. О задаче анализа цепей Маркова по критерию линейной сложности

1.4. О задаче разработки комплекса методик и программ

1.5. Выводы по главе

Глава 2. Методы представления случайных последовательностей полиномиальными функциями над конечным полем

2.1. Представление стохастических матриц полиномиальными функциями над полем GF(2") с учетом точности представления элементов матриц

2.1.1. Введение

2.1.2. Подход разложения матриц, основанный на методе минимакса

- Алгоритм минимакса

2.1.3. Двоично-рациональный подход разложения матриц

- Алгоритм

- Алгоритм 2м

- Алгоритм

- Алгоритм Зм

- Алгоритм

- Алгоритм 4м

2.1.4. Метод построения функций цепей Маркова над полем GF(2") и оценки порядка поля

2.1.5. Выводы по разделу

2.2. Представление расширенных цепей Маркова над полем GF(2")

2.2.1. Введение

2.2.2. Получение стохастической матрицы расширенной цепи Маркова

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

- Определение "промежуточной" матрицы переходов

- Определение матрицы О расширенной цепи Маркова

- Алгоритм вычисления матрицы О расширенной цепи Маркова по матрице Р исходной цепи Маркова

2.2.3. Полиномиальные модели расширенных цепей Маркова над полем GF(2")

- Модель генератора расширенной цепи Маркова на регистре сдвига

- Полиномиальная модель расширенной цепи Маркова на основе имплицирующего вектора

- Полиномиальная модель расширенной цепи Маркова на основе приведенного автомата

2.3. Моделирование случайных последовательностей минимальными полиномами над конечным полем по заданной стохастической матрице

2.3.1. Введение

2.3.2. Теоретический анализ. Постановка задачи

2.3.3. Схема построения минимального многочлена над полем

2.3.4. Метод моделирования случайной последовательности на основе минимального полинома

2.3.5. Характеризация класса случайных последовательностей 90 2.4. Выводы по главе

Глава 3. Методы анализа полиномиальных функций, моделирующих случайные последовательности в конечном поле

3.1. Анализ нелинейных моделей преобразователей случайных последовательностей над полем GF(2") на основе стохастических матриц

3.1.1. Введение

3.1.2. Определение базовых полиномиальных функций над полем

GF(2")

3.1.3. Полиномиальные нелинейные динамические модели, 95 порождающие функции цепей Маркова. Вероятностные характеристики моделей

- Полиномиальная модель цепи Маркова

- Полиномиальная модель марковской функции В{

- Полиномиальная модель марковской функции Zt

- Полиномиальная модель марковской функции Z't

3.2. Статистический анализ линейной сложности регулярных цепей

Маркова

3.2.1. Введение

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

3.2.3. Реализация и тестирование алгоритма Берлекэмпа-Мэсси

Во введении обосновывается актуальность темы диссертации, дается определение цели и задач исследования, приводится перечень основных результатов, выносимых на защиту. Дана структура диссертации.

Актуальность работы. Одним из подходов моделирования цепей Маркова (ЦМ) и марковских функций является подход, использующий теорию конечных полей [1]. Перспективность этого подхода определяется приложением функций конечных ЦМ [2-4], возрастающей сложностью вероятностных дискретных моделей [2, 3] и эффективностью арифметики конечных полей в задачах цифровой обработки информации [5-10]. Аппарат конечных полей используется для решения задач синтеза вероятностных автоматов и генераторов случайных двоичных последовательностей, для моделирования случайных линейных зависимых процессов в конечном поле и некоторых типов цепей Маркова и вероятностных автоматов (ВА) (Аблаев Ф.М. [11, 12], Бухараев Р.Г. [2, 3, 13-15], Кирьянов Б.Ф. [16], Крашенинников В.Р. [17, 18], Кузнецов В.М. [19], Латыпов Р.Х. [20-24], Мансуров P.M. [25], Осмоловский С.А. [26], Песошин В.А. [19, 25], Столов Е.Л. [20-23, 27-30], Taylor L. [31]).

В работах Захарова В.М., Нурутдинова Ш.Р., Соколова С.Ю., Шалагина С.В. (2000-2006 г.г.) [32-34] предложен подход моделирования дискретных случайных процессов на полиномиальных моделях, описываемых полиномиальными функциями (ПФ) над полем GF(2"). Полиномиальные функции рассматриваются как модели дискретных преобразователей цепей Маркова [10, 32-37]. Разработаны методы представления полиномиальными функциями над полем GF(2") простых и сложных ЦМ и определенных функций однородных и неоднородных ЦМ (ФЦМ). Задача представления решается как задача вычисления коэффициентов полиномов над полем GF(2") на основе заданных стохастических матриц. Решена важная прикладная задача отображения полиномиальных моделей в однородные вычислительные среды, позволяющие реализовать параллельные алгоритмы вычисления и проводить потоковые преобразования над «-мерными векторами при моделировании дискретных случайных процессов [10, 32-39]. Однако, в этом направлении существуют недостаточно исследованные вопросы и нерешенные задачи, имеющие теоретическое и практическое значение.

Для дальнейшего развития и повышения эффективности методов моделирования дискретных случайных процессов в конечном поле актуальным является исследование вопросов, связанных с повышением точности полиномиальных моделей, определением их свойств и вероятностных характеристик, расширением класса случайных последовательностей (СП), представляемых полиномиальными функциями над полем GF(2") и конечным полем GF(gc) характеристики qc > 2, с получением оценок порядка поля в зависимости от точности задания закона цепи Маркова и структуры стохастических матриц (СМ), а также ряд других вопросов, связанных с построением (вычислением коэффициентов) и анализом полиномиальных функций над конечным полем.

Объект исследования. Модели и аналитические методы моделирования случайных последовательностей над конечным полем.

Предмет исследования. Полиномиальные модели, порождающие функции цепей Маркова в конечном поле, свойства и характеристики этого класса моделей.

Целью диссертационной работы является развитие полиномиальных моделей, аналитических методов и построение эффективных методик для моделирования цепей Маркова и их функций в конечном поле.

Научная задача. Разработка новых аналитических методов построения полиномиальных функций и анализа свойств полиномиальных функций, порождающих случайные последовательности в конечном поле на основе стохастических матриц, с учетом структурных свойств СМ и точности задания переходных вероятностей.

Решение общей научной задачи и достижение поставленной цели связано с решением следующих задач.

1. Разработка метода и алгоритмов представления стохастических матриц полиномиальными функциями над полем GF(2"). Определение оценок порядка поля GF(2") с учетом точности задания элементов стохастических матриц (переход от объекта ЦМ к ВА и к ПФ, от В А и ПФ к ФЦМ (рис.В1,а) по схеме, представленной на рис.В1,б)).

2. Разработка метода и алгоритмов моделирования расширенных цепей Маркова (РЦМ) полиномиальными функциями над полем GF(2"). Определение порядка поля GF(2") с учетом структуры стохастической матрицы расширенной цепи Маркова (переход от простой ЦМ к расширенной ЦМ, и от расширенной ЦМ к В А и к ПФ (рис.В1,а) по схеме, представленной на рис .В 1,6)).

3. Разработка метода представления неразложимых стохастических матриц с заданной точностью полиномами минимальной степени над конечным полем GF(</C) характеристики qc> 2 (представление объекта ЦМ в виде полинома над конечным полем (рис.В1,а) с использованием объекта СМ Р (рис.В1,б)).

4. Разработка метода вычисления характеристик полиномиальных моделей, предназначенных для получения случайных последовательностей из класса функций цепей Маркова (переход от объекта ПФ к ЦМ и ФЦМ (рис.В1,а)).

5. Статистический анализ цепей Маркова по критерию линейной сложности (JIC) последовательностей. Исследование взаимосвязи энтропии неразложимых стохастических матриц с линейной сложностью реализаций цепей Маркова (исследование объекта ЦМ (рис.В1,а) по объекту СМ Р (рис.В1,б)).

6. Разработка комплекса методик и программ, реализующих предлагаемые методы и алгоритмы.

Рис. В1,а иллюстрирует известную [2, 3, 32, 33] существующую взаимосвязь между математическими объектами - ЦМ, В А, ПФ, ФЦМ. Рис. В 1,6 иллюстрирует схему общего подхода [32-34], в рамках которого решаются перечисленные задачи 1-6. Подход основан на разложении стохастических матриц Р на пару - дискретную случайную величину (ДСВ) и конечный м детерминированный автомат (КДА), получаемые из разложения Р =

1=0

-1

40], где q = (q,) - имплицирующий вектор длины /, = 1.

1=0

Данная схема представляет предмет исследования, сформулированный выше.

Методы исследований. Для решения поставленных задач использованы методы теории чисел, теории вероятностей, математической статистики, теории детерминированных и вероятностных автоматов, теории графов, аппарат конечных полей, линейной и полиномиальной алгебры, дискретной математики.

Научная новизна работы и значимость результатов.

- Новые метод и алгоритмы представления стохастических матриц с двоично-рациональными элементами полиномиальными функциями над полем GF(2"), с учетом точности задания переходных вероятностей. Сформулированы и доказаны теоремы, обосновывающие метод.

- Новые метод и алгоритмы получения и отображения закона расширенных цепей Маркова в полиномиальную функцию над полем GF(2"). Сформулированы и доказаны теоремы, обосновывающие метод.

- Новый метод представления стохастических матриц с заданной точностью и моделирования случайных последовательностей из класса неоднородных цепей Маркова полиномами минимальной степени над полем GF(c/c) характеристики qc> 2. Доказана теорема, устанавливающая линейную связь между точностью задания стохастической матрицы и величиной минимальной степени полинома.

- Новый метод определения вероятностных характеристик случайных последовательностей из класса функций однородных цепей Маркова, порождаемых полиномиальными нелинейными динамическими моделями над полем GF(2"). Доказаны теоремы, устанавливающие формулы для вычисления асимптотических вероятностных характеристик случайных последовательностей.

- Методика исследования однородных простых и сложных цепей Маркова на основе критерия линейной сложности. Сформулирован критерий нахождения длин реализаций марковских последовательностей при заданной точности представления матриц цепей Маркова. Определены стохастические зависимости линейной сложности реализаций цепей Маркова от энтропии стохастических матриц.

Достоверность результатов работы. Основные полученные результаты сформулированы в виде теорем и утверждений, приведены их доказательства. Предложенные аналитические методы и алгоритмы обоснованы доказательством теорем. Адекватность предложенных моделей подтверждается компьютерным моделированием и сравнением с известными результатами.

Практическая значимость работы.

- Решение задачи представления РЦМ полиномиальными функциями над полем GF(2") расширяет класс дискретных случайных процессов, получаемых на полиномиальных моделях, и позволяет определить свойства данных процессов и стохастических матриц РЦМ.

-Предложенные алгоритмы разложения СМ ЦМ на имплицирующий вектор (ИВ) и множество стохастических булевых матриц (СБМ) позволяют определить вычислительную и комбинационную сложности вероятностных автоматов, синтезируемых в некотором логическом базисе.

- Полученные формулы определения предельного распределения вероятностей символов СП, порождаемых полиномиальными нелинейными динамическими моделями дискретных преобразователей информации, и фундаментальная матрица для СМ позволяют на их основе получить ряд других характеристик СП, например, матрицу средних времен достижения, векторы предельных дисперсии и корреляции.

- Метод моделирования СП на основе минимального полинома позволяет: воспроизводить на линейных регистрах сдвига реализации ЦМ; расширить функциональное использование линейных регистров сдвига.

- Методика исследования JIC марковских последовательностей расширяет класс задач применения JIC, дает возможность моделировать ЦМ на основе линейных и нелинейных полиномов минимальных степеней, позволяет выявлять свойства JIC марковских функций.

- Комплекс программ, алгоритмов и методик является инструментальным средством для моделирования СП и исследования свойств полиномиальных функций над конечным полем.

Результаты работы используются:

- в подсистеме временного прогнозирования производственно-экономических показателей состояния предприятия (на базе разработанной в диссертации программной реализации математического аппарата числовых стохастических матриц), включенной в состав автоматизированного рабочего места менеджера предприятия, введенного в опытную эксплуатацию в ОАО "ICL-КПО ВС", г. Казань (справка об использовании результатов);

- в учебном процессе кафедры Компьютерных систем (предыдущее название (до 2006 года) - Компьютерные системы и информационная безопасность) и кафедры Систем информационной безопасности КГТУ им. А.Н. Туполева в форме учебного электронного пособия "Лабораторный практикум по вычислениям в конечных полях" (акт внедрения).

На защиту выносятся следующие результаты, полученные лично:

- метод и алгоритмы определения закона и свойств РЦМ по СМ исходной простой ЦМ, теоремы, обосновывающие метод и алгоритмы;

- метод представления заданного закона РЦМ минимизированной автоматной моделью и полиномиальной функцией над полем GF(2"), теоремы, обосновывающие метод и свойства стохастических матриц РЦМ;

- метод и алгоритмы разложения СМ ЦМ с двоично-рациональными элементами на ИВ и множество СБМ, теоремы, обосновывающие метод и алгоритмы;

- аналитический метод определения характеристик СП из класса функций однородных ЦМ, порождаемых полиномиальными нелинейными динамическими моделями над полем GF(2"), теоремы, обосновывающие метод;

- статистический метод исследования однородных простых и сложных ЦМ на основе критерия JIC;

- аналитический метод представления СМ с заданной точностью и моделирования СП из класса неоднородных ЦМ полиномами минимальной степени над полем GF(gc), теорема, обосновывающая метод;

- комплекс методик и программ, реализующий предложенные методы и алгоритмы.

Апробация результатов работы. Основные результаты докладывались и обсуждались на следующих конференциях и семинарах: X-XV Всероссийские молодежные научные конференции "Туполевские чтения" (Казань, 2002-2007); Всероссийская научная конференция студентов и аспирантов (Таганрог, 2004); XIV Международная конференция "Проблемы теоретической кибернетики" (Пенза, 2005); Региональная научно-методическая конференция "Профессиональные компетенции в структуре модели современного инженера" (Нижнекамск, 2005); 6-ая Международная конференция молодых ученых и студентов (Самара, 2005); Международная научно-практическая конференция "Инфокоммуникационные технологии глобального информационного общества" (Казань,2005); Региональная научно-методическая конференция "Информационная культура в системе подготовки будущего инженера" (Нижнекамск, 2006); Всероссийский семинар "Ситуационные исследования" (Казань, 2006); Региональная научно-техническая конференция по вопросам информатики, вычислительной техники и информационной безопасности (Казань, 2006); Региональная научно-практическая конференция "Наука и профессиональное образование" (Нижнекамск, 2007); 9-ый Международный семинар "Дискретная математика и ее приложения" (Москва, 2007); Всероссийская научная конференция студентов, аспирантов и молодых ученых "Наука, технологии, инновации" (Новосибирск, 2007); Республиканский научный семинар "Методы моделирования" при КГТУ им. А.Н. Туполева (Казань, 2004-2008).

Содержание работы опубликовано в 29 работах, включая 3 статьи [41-43], опубликованные в изданиях, входящих в перечень ВАК, 16 статей [44-59] в других изданиях, 9 тезисов [60-68] докладов и одну работу [69], зарегистрированную в отраслевом.фонде алгоритмов и программ.

Структура и объем диссертации.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения.

4.8. Выводы по главе

Разработанный комплекс методик и программ реализует методы, алгоритмы и методики, предложенные в диссертации. Описаны следующие методики:

- представления простых и расширенных цепей Маркова над полем GF(2");

- моделирования случайных последовательностей на основе минимальных полиномов;

- статистического анализа линейной сложности регулярных цепей Маркова.

Часть компонентов комплекса базируется на известных алгоритмах. Комплекс ориентирован на решение задач:

- преобразование цепи Маркова (в том числе и расширенной цепи Маркова) в полиномиальную модель с использованием алгоритмов двоично-рационального разложения стохастических матриц;

- отображение полиномиальных моделей в марковские функции;

- тестирование предложенных полиномиальных моделей;

- получение закона расширенной цепи Маркова;

- исследование характеристик марковских и псевдомарковских циклических последовательностей с помощью алгоритма Берлекэмпа-Месси.

Также разработаны комплексы программ в виде электронных учебных пособий по вычислениям в конечных полях и по моделированию псевдослучайных последовательностей (ПСП) (программная реализация статистических тестов анализа ПСП) (акт внедрения разработанных программ в учебном процессе на кафедре компьютерных систем КГТУ им.А.Н.Туполева по дисциплине "Моделирование"), подсистема временного прогнозирования производственно-экономических показателей состояния предприятия для автоматизированного рабочего места менеджера предприятия (справка об использовании результатов).

Заключение

1. Разработан новый метод моделирования расширенных цепей Маркова в поле GF(2"), основанный на предложенном методе определения закона расширенной цепи Маркова по заданной стохастической матрице простой цепи Маркова. Доказаны теоремы, устанавливающие новые свойства (структурные, асимптотические) стохастических матриц расширенных цепей Маркова и оценки минимального порядка поля GF(2") для представления расширенных цепей Маркова полиномиальными функциями.

2. Предложены новые алгоритмы разложения двоично-рациональных стохастических матриц на имплицирующий вектор и множество стохастических булевых матриц, позволяющие снизить вычислительную сложность разложения и получить точную оценку размера имплицирующего вектора и порядка поля GF(2") для описания полиномиальных функций. Доказаны теоремы, обосновывающие алгоритмы и оценки.

3. Предложен новый метод моделирования случайных последовательностей фиксированной длины N из класса неоднородных цепей Маркова, заданных стохастическими матрицами, на основе полиномов минимальной степени над конечным полем GF(gc), qc > 2, позволяющий повысить точность представления стохастических матриц полиномами пропорционально величине 1 IN. Доказана теорема, устанавливающая существование минимальных полиномов для представления стохастических матриц с заданной точностью.

4. Сформулированы и доказаны теоремы, составляющие основу предложенного аналитического метода вычисления характеристик полиномиальных нелинейных динамических моделей над полем GF(2"), порождающих случайные последовательности из класса функций конечных однородных цепей Маркова.

5. Предложена новая методика статистического анализа однородных простых и сложных цепей Маркова по критерию линейной сложности. Статистическим моделированием получены оценки линейной сложности реализаций цепей Маркова.

6. Разработан комплекс методик и программ, реализующий предложенные методы и алгоритмы.

1. Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т./Пер.с англ. М.: Мир, 1988.-808 с.

2. Бухараев Р.Г. Основы теории вероятностных автоматов. М.: Наука, 1985.-287 с.

3. Бухараев Р.Г., Захаров В.М., Управляемые генераторы случайных кодов. Казань: Изд-во Казан, ун-та, 1978.-160с.

4. Поспелов Д.А. Вероятностные автоматы. М.: Энергия, 1970. - 88 с.

5. Зензин О.С., Иванов М.А. Стандарт криптографической защиты AES. Конечные поля. М.: КУДИЦ-ОБРАЗ, 2002. - 176 с.

6. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. М.: Гелиос АРВ, 2002. - 480 с.

7. Рааг С. A new architecture for a parallel finite field multiplier with low complexity based on composite fields. IEEE Trans, on Computers, 45(7), pp.856861, July, 1996.

8. Paar C., Fleischmann P., Soria-Rodriguez P. Fast arithmetic for public-key algorithms in Galois fields with composite exponents // IEEE Transactions on Computers, 48 (10): pp. 1025-1034, October 1999.

9. Paar C., Lange N. A comparative VLSI synthesis of finite field multipliers. In 3rd International Symposium on Communication Theory and its Applications, Lake District, UK, July 10-14,1995.

10. Нурутдинов Ш.Р. Основы теории полиномиальных моделей автоматных преобразований над полем Галуа. Казань: Изд-во Казан, ун-та, 2005. - 155 с.

11. Аблаев Ф.М. К вопросу об автоматной сложности языков и сложности распознавания по Лавленду // Вероятностные методы и кибернетика, вып. 19. -Казань: Изд-во КГУ, 1983. С. 3-9.

12. Аблаев Ф.М. К вопросу о представимости языков в бесконечных вероятностных автоматах // Вероятностные автоматы и их приложения. -Казань: Изд-во КГУ, 1986. С. 61-64.

13. Бухараев Р.Г. Автоматное преобразование вероятностных последовательностей // Вероятностные методы и кибернетика. Вып. 4. Казань: Изд-во Казан, ун-та, 1966. - С. 24-33.

14. Бухараев Р.Г., Геза В.И. Специализированная ЭВМ для моделирования и обработки функций конечных однородных цепей Маркова. // Тезисы докл. Всес. симп. по вероятностным автоматам. Казань.: Изд-во КГУ, 1969.-С.14-15.

15. А.с. 1524046. Генератор случайных чисел. / Бухараев Р.Г., Захаров В.М., Баранов Г.Г., Комаров Ю.С., Кузнецов С.Е., Макаров И.И., Пермитин В.В.//Б.И. 1983. -№43.

16. Кирьянов Б.Ф. Основы теории стохастических вычислительных машин и устройств. 1976. - Деп. ЦНИИГЭ приборостроения, № 524. - 168 с.

17. Крашенинников В.Р., Трояновский С.В. Случайные блуждания на конечном ориентированном графе // "КИБЕРНЕТИКА", №1, 1970. С. 93-97.

18. Васильев К.К., Драган Я.П., Казаков В.А., Крашенинников В.Р., Кунченко Ю.П., Омельченко В.А., Трифонов А.П., Спектор А.А. Прикладная теория случайных процессов и полей. Ульяновск: Изд-во Ульяновского техн. гос. ун-та, 1995. - 256 с.

19. Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л., Фараджев Р.Г. Применение теории линейных последовательных машин в системах диагностики // Автоматика и телемеханика, № 8. 1988. - С. 3-27.

20. А.с. 1695304. Устройство для контроля логических блоков / Латыпов Р.Х., Нурутдинов Ш.Р, Столов Е.Л. // Б.И. №44. 1991.- 3 с.

21. А.с. 1108614. Генератор случайных последовательностей / Захаров В.М., Баранов Г.Г., Комаров Ю.С., Латыпов Р.Х., Столов Е.Л. 11 Б.И. 1984. -№30.

22. А.с. 1224992. Генератор псевдослучайных чисел / Захаров В.М., Баранов Г.Г., Комаров Ю.С., Латыпов Р.Х., Столов Е.Л. // Б.И. 1986. - № 14.

23. Латыпов Р.Х. Сжатие информации в системах встроенного тестирования цифровых схем. Дис. д-ра. техн. наук. Казань, 1994.

24. А.с. 664185. Генератор случайных чисел / Песошин В.А., Тарасов В.М., Мансуров P.M. // Открытия, изобретения. 1979. - № 19.

25. Осмоловский С.А. Стохастические методы передачи данных. М.: Радио и связь, 1991. - 240 с.

26. Столов Е.Л. Методы компактного тестирования цифровых устройств. -Казань: Изд-во Казан, ун-та, 1993. 116 с.

27. Столов Е.Л. Исчерпывающее тестирование и сигнатурный анализ // АиТ, №6. 1992. - С. 167-172.

28. Столов Е.Л. Об одном классе генераторов псевдомарковских цепей // Исследования по прикладной математике. Вып.8. Казань: Изд-во Казан, ун-та, 1985.-С. 66-71.

29. А.с. 1672438. Устройство для умножения двух элементов конечного поля GF(2") / Нурутдинов Ш.Р., Столов Е.Л. //Б.И., №31. 1991.

30. Taylor L. Booth. Sequential Machines and Automata theory. New York: John Wiley and Sons Inc, 1968. - 592 pp.

31. Захаров B.M., Нурутдинов Ш.Р., Шалагин C.B. Полиномиальное представление цепей Маркова над полем Галуа // Вестник КГТУ им. А.Н. Туполева, 2001, №3. С. 27-31.

32. Захаров В.М., Нурутдинов Ш.Р. Полиномиальные модели вероятностных автоматов и функций цепей Маркова над полем GF(2") // Эволюционное моделирование. Труды Казанского городского семинара "Методы моделирования". Казань: ФЭН, 2004. - С. 48-72.

33. Захаров В.М., Нурутдинов Ш.Р., Шалагин С.В. Синтез автономных вероятностных автоматов на основе полей Галуа // Исследования по информатике. Вып. 2. Казань: Отечество, 2000. - С. 107-116.

34. Нурутдинов Ш.Р. Полиномиальные модели автоматных преобразований над полем GF(2") // Автореферат докторской диссертации. -Казань: Изд-во КГУ, 2007. 32 с.

35. Захаров В.М, Нурутдинов Ш.Р. Шалагин С.В. Аппаратная реализация умножения элементов поля Галуа на программируемых микросхемах архитектуры FPGA // Вестник Казан, гос. технг ун-та им. А.Н. Туполева, 2001, №1. С. 36-41.

36. Нурутдинов Ш.Р., Шалагин С.В. Вычисление произведения элементов поля Галуа // Теория сеточных методов для нелинейных краевых задач. Материалы 3-го Всеросс. семинара. Казань: Изд-во Казанского мат. общества, 2000. - С. 144.

37. Davis A.S. Markov chains as random input automata. Amer. Math. Monthly, 1961, 68, 3, pp. 264-267.

38. Захаров В.М., Эминов Б.Ф. Анализ алгоритмов разложения двоично-рациональных стохастических матриц на комбинацию булевых матриц // Информационные технологии, №3. М.: Изд-во Новые технологии; 2008. - С. 54-59.

39. Захаров В.М., Эминов Б.Ф. Статистический анализ линейной сложности регулярных цепей Маркова // Исследования по информатике. Выпуск 10. ИЛИ АНРТ. Казань: Отечество, 2006. - С. 37-50.

40. Эминов Б.Ф. К задаче анализа полиномиальных моделей автономных вероятностных автоматов // ХП Туполевские чтения: Международная молодежная научная конференция. Том 3. Казань: КГТУ им. А.Н. Туполева, 2004. - С. 60-62.

41. Захаров В.М., Эминов Б.Ф. Автоматное моделирование расширенных цепей Маркова // Актуальные проблемы современной науки: Труды 1-го Международного форума молодых ученых и студентов.Ч. 18.-Самара: Изд-во Самар.гос.техн.ун-та,2005.- С. 146-148.

42. Эминов Б.Ф. Программный комплекс обучающих средств "Основы криптографической защиты информации" // Прикладная информатика 2004: Доклады факультетской научно-технической конференции. - Казань: КГТУ им. А.Н. Туполева, 2005. - С. 84-88.

43. Эминов Б.Ф. Анализ полиномиальных моделей автономных вероятностных автоматов // Прикладная информатика 2004: Доклады факультетской научно-технической конференции. - Казань: КГТУ им. А.Н. Туполева, 2005. - С. 36-40.

44. Эминов Б.Ф. Модели ситуационного управления как инструмент познания // Всероссийский семинар Ситуационные исследования: вып. 2. Типология ситуаций // Под ред. Н.М.Солодухо. Казань: КГТУ им.А.Н.Туполева, 2006. - С. 84-94.

45. Эминов Б.Ф. Минимизация автоматной модели расширенной цепи Маркова методом /-эквивалентных преобразований // XIV Туполевские чтения Международная молодежная науч. конференция,том 4.-Казань :КГТУ им. А.Н.Туполева,2006.-С.74-76.

46. Эминов Б.Ф. Получение стохастической матрицы расширенной цепи Маркова // Наука и профессиональное образование: Материалы региональной научно-практической конференции, Нижнекамск.-Казань: КГТУ им.А.Н.Туполева, 2007.-С.225-230.

47. Эминов Б.Ф. Применение алгоритма Берлекемпа-Месси к синтезу и анализу рекуррентных двоичных последовательностей // XV Туполевские чтения: Международная молодежная науч.конф.Том 3. Казань: КГТУ им. А.Н.Туполева, 2007. - С.90-92.

48. Эминов Б.Ф. Вычислительная сложность и имплицирующий вектор стохастических матриц с двоично-рациональными элементами // XV Туполевские чтения: Международная молодежная научная конференция. Том 3. Казань: КГТУ им.А.Н.Туполева, 2007. - С. 87-90.

49. Эминов Б.Ф. Анализ линейной сложности эргодических цепей Маркова // Всероссийская научная конференция студентов и аспирантов. Таганрог: Изд-во Таганрогского гос. радио-техн. ун-та, 2004. - С. 242-243.

50. Эминов Б.Ф. Сравнительный анализ линейной сложности марковских и псев до-марковских последовательностей // XII Туполевские чтения: Международная молодежная научная конференция. Том 3. Казань: КГТУим. А.Н.Туполева,2004.-С.62-63.

51. Эминов Б.Ф. Автоматный метод моделирования расширенных цепей Маркова // Туполевские чтения: Международная молодежная научная конференция. Том 3. Казань: КГТУ им. А.Н. Туполева, 2005. - С. 59-60.

52. Захаров В.М., Эминов Б.Ф. Электронное учебное пособие "Лабораторный практикум вычислений в конечных полях" // Регистрация в отраслевом фонде алгоритмов и программ, №10018. М., 2008.

53. Марков А. А. Исследование замечательного случая зависимых испытаний // Изв. Петерб. АН (6). 1907. - Т.1.

54. Колмогоров А.Н. Цепи Маркова со счетным числом возможных состояний // Бюл. МГУ. Сер. А. 1937. - т. 1.

55. Волков И.К., Зуев С.М., Цветкова Г.М. Случайные процессы. М.: Изд-во МГТУ им. Н.Э. Баумана, 1999. - 448 с.

56. Дуб Дж.Л. Вероятностные процессы. М.: Изд-во иностранной литературы, 1956. - 607 с.

57. Скороход А.В. Вероятность, марковские процессы, приложения // Итоги науки и техники. ВИНИТИ. Современные проблемы математического фундаментального направления. №43. М.: ВИНИТИ, 1989. - С. 5-270.

58. Гихман И.И., Скороход А.В. Введение в теорию случайных процессов. -М: Наука, 1977.-568 с.

59. Булинский А.В., Ширяев А.Н. Теория случайных процессов. М.: Физматлит, 2005. - 408 с.

60. Портенко Н.И., Скороход А.В., Шуренков В.М. Марковские процессы // Итоги науки и техники. ВИНИТИ. Современные проблемы математического фундаментального направления. №46. М.: ВИНИТИ, 1989. - С. 5-248.

61. Розанов Ю.А. Марковские случайные поля. М.: Наука, 1981. - 256 с.

62. Дынкин Е.Б. Марковские процессы. М.: Государственное издание физико-математической литературы, 1963. - 860 с.

63. Тутубалин В.Н. Теория вероятностей и случайных процессов. Основы математического аппарата и прикладные аспекты. -М.: Изд-во МОГУ,1992.-397 с.

64. Iosifescu, Marius. Finite Markov Processes and Their Applications. New York: John Wiley, 1980. - 294 pp.

65. Малахов А.Н. Кумулянтный анализ случайных негауссовых процессов и их преобразований. М.: Советское радио, 1978. - 376 с.

66. Gohm R. Noncommutative stationary processes. New York: Springer-Verlag, 2004. - 170 pp.

67. Bochner S. Stochastic processes // The Annals of Mathematics. Vol.48, №4. 1947. - pp. 1014-1061.

68. Дынкин Е.Б. Основы теории марковских процессов. М.: Физматгиз, 1959. - 227 с.

69. White D.J. Markov decision processes. New York: John Wiley & Sons, 1993.-224 pp.

70. Стратонович P.JI. Условные марковские процессы и их применение к теории оптимального управления. М.: Изд-во МГУ, 1965. - 319 с.

71. Athreya К.В., Ney Р.Е. Branching processes. New York: Springer, 1972. -287 pp.

72. Bailey N.T.J. The elements of stochastic processes, with applications to natural sciences. New York: John Wiley & Sons Inc., 1964. - 249 pp.

73. Hsu H.P. Theory and problems of probability, random variables and random processes. New York: McGRaw-Hill, 1997. - 311 pp.

74. Ван Кампен Н.Г. Стохастические процессы в физике и химии. М.: Высшая школа, 1990. - 376 с.

75. Kemeny J., Snell J.L., Thompson G. Introduction to finite mathematics. 3ed. New Jersey: Prentice-hall Inc, 1974. - 484 pp.

76. Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1970. -272 с.

77. Olle Haggstrom. Finite Markov Chains and Algorithmic Applications. -Cambridge: Cambridge University Press, 2003. - 114 pp.

78. Kemeny J.G., Snell L.J., Knapp A.W. Denumerable Markov chains. New York: Van Nostrand, 1967. - 439 pp.

79. Романовский В.И. Дискретные цепи Маркова. М.: Гостехиздат, 1949. -436 с.

80. Маслов В.П. Комплексные марковские цепи и континуальный интеграл Фейнмана для нелинейных уравнений. М.: Наука, 1976.- 190.

81. Li Xie. Finite horizon robust state estimation for uncertain finite-alphabet hidden markov models. New South Wales: The University of New South Wales, 2004. - 174 pp.

82. Bleher P., Its A. Random matrix models and their applications. Cambridge: Cambridge University Press, - 2001. - 438 pp.

83. Четаев A.H. Нейронные сети и цепи Маркова. М.: Наука, 1985.-128 с.

84. Постников А.Г. Арифметическое моделирование случайных процессов. Труды математического института им. В.А. Стеклова АН СССР. Т. 57. - М.: Изд-во АН СССР, 1960. - 84 с.

85. Марков А.А. О связанных величинах, не образующих настоящей цепи. ИАН (6), 5(1911). С.113-126.

86. Коновалов М.Г. Некоторые свойства функции предельного среднего дохода в задаче управления марковскими цепями. Вестник РУДН, серия Прикладная и компьютерная математика, Т. 3, №1. 2004. С. 52-68.

87. Коновалов М. Г. Управляемые марковские последовательности и оптимизация маршрутных таблиц в сетях связи с коммутацией каналов // Системы и средства информатики. Вып. 11. 2001. - С. 78-93.

88. Такач Л. Комбинаторные методы в теории случайных процессов. М.: Мир, 1971.-264 с.

89. Дынкин Е.Б., Юшкевич А.А. Управляемые марковские процессы и их приложения. М.: Наука, 1975. - 340 с.

90. Kindermann R., Snell J.L. Markov random fields and applications. -Providence, Rhode Island: American Mathematical Society, 1980. 142 pp.

91. Винер H. Нелинейные задачи в теории случайных процессов. М.: Изд-во иностранной литературы, 1961. - 159 с.

92. Selected papers on noise and stochastic processes. Edited By Wax N. -New York: Dover Publications, 1954. 343 pp.

93. Марченко Б.Г., Щербак JI.H. Линейные случайные процессы и их приложения. Киев: Наукова Думка, 1975. - 130 с.

94. Марченко Б.Г., Омельченко В.А. Вероятностные модели случайных сигналов и полей в прикладной статистической физике. Киев: УМК ВО, 1988. - 176 с.

95. Арато, Матиаш. Линейные стохастические системы с постоянными коэффициентами: статистический подход. М.: Наука, 1989. - 303 с.

96. Владов Ю.Р. Автоматизированная идентификация состояния трубопроводных систем в машиностроении. Оренбург: Изд-во Оренбургского гос-го ун-та, 2005. - 101 с.

97. Тальнишних С.А. Определение времени сохранения качества технических объектов машиностроения // Инструмент и технологии. Санкт-Петербург: Инструмент и технологии, 1995. - С. 101-109.

98. Петунин Ю.И. Приложение теории случайных процессов в биологии и медицине. Киев: Наукова Думка, 1981. - 320 с.

99. George W. Cobb, Yung-Pin Chen. Random Walks on Binary Matrices: An Application of Markov Chain Monte Carlo. Research Experiences for Undergraduates. Department of Mathematics and Statistics. South Hadley: Mount Holyoke College, 2001. 34 pp.

100. Lawrence R. Rabiner. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IEEE, 77 (2), p. 257-286, February 1989.

101. Linda Van Guilder Automated Part of Speech Tagging: A Brief Overview (Handout for LING361, Fall 1995 Georgetown University) Georgetown University, 1995.

102. Lior Pachter and Bernd Sturmfels. Algebraic Statistics for Computational Biology. Cambridge University Press, 2005.

103. Дурбин P., Эдди III., Крог А., Митчисон Г. Анализ биологических последовательностей. М.: РХД, 2006. - 480 с.

104. Singer В., Spilerman S. The representation of social processes by Markov models// American Journal of Sociology. V. 82. 1976, pp. 1-51.

105. Бартоломью Д. Стохастические модели социальных процессов. М.: Наука, 1985.

106. Бородкин Л.И. Стохастические модели в изучении социальных перемещений русского крестьянства в XIX веке.

107. Макаров С.В. О реализации стохастических матриц конечными автоматами // Вычислительные системы. Вып. 9. Новосибирск: Вычислительные системы, 1963. - С. 65-70.

108. Хамитов Г.П. Имитация случайных процессов. Иркутск: Изд-во Иркут. ун-та, 1983.-184 с.

109. Четвериков В.Н., Баканович Э.А., Меньков А.В. Вычислительная техника для статистического моделирования. М.: Сов. радио, 1978. - 312 с.

110. Ченцов В.М. Об одном методе синтеза автономного стохастического автомата // Кибернетика. Киев, Кибернетика, 1968. - №3. - С. 32-35.

111. А.с. 1481755, МКИ С 06 Г 7/58. Генератор случайного марковского процесса / Гремальский А.А., Андроник С.М. // Открытия, изобретения. 1989. -№19.-С. 223.

112. Гремальский А.А., Андроник С.М. Генерация тестовых программ для микропроцессоров с помощью цепей Маркова // Исследование новых микропроцессорных приборов и устройств. Кишинев: Штинца, 1987. - С. 9698.

113. Вероятностные автоматы и их приложения. Казань: Изд-во КГУ, 1986.-212 с.

114. Pitman J. W. Occupation Measures for Markov Chains // Advances in Applied Probability, Vol. 9, No. 1,1977, 69-86 pp.

115. Иванов M.A., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. М.: Кудиц-Образ, 2003. -240 с.

116. Marsaglia G. Diehard Battery of Tests of Randomness, 1995. http://stat.fsu.edu/~geo/diehard.html.

117. Молдавян H.A. и др. Криптография. От примитивов к синтезу криптоалгоритмов. СПб.: БХВ-Петербург, 2005. - 286 с.

118. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях / Под ред. В.Ф: Шаньгина. М.: Радио и связь, 1999. - 328 с.

119. Гладкий B.C. Вероятностные вычислительные модели. М.: Наука, 1973.-300 с.

120. Лоренц А А. Надежность и быстродействие вероятностных автоматов. Рига: Зинатне, 1976. - 112 с.

121. Гилл А. Синтез вероятностных преобразователей // Кибернетический сборник, вып. 8. М.: Мир, 1971. - 245 с.

122. Wing О., Demetrions P. Analysis of probabilistic networks. IEEE trans, commun. techn., 1964, volume 12, №3.

123. Booth J.L. Random input automata. Ln: JCMCL Conf., Tokyo, 1964.

124. Paz A. Introduction to probabilistic automata. NV, Academic Press., 1971.

125. Альпин Ю.А., Захаров В.М. Моделирование случайных последовательностей автономными автоматными схемами // Вероятностные автоматы и их приложения. Казань: Изд-во Казан, ун-та, 1986. С. 22-29.

126. Паршенков Н.Я. Декомпозиционная модель вероятностного автомата //Построение управляющих устройств и систем. М.: Наука, 1974. - С. 180-202.

127. Gelenbe S.E. A realizable model for stohastic sequential machines // IEEE Trans, on Comput, 1971. № 2. P. 199-204.

128. Габбасов Н.З. О минимальном имплицирующем векторе для линейных автоматов // Вероятностные автоматы и их приложения. Казань: Изд-во КГУ, 1986. - С. 78-83.

129. Метра И.А. Замечания о минимальном имплицирующем векторе для стохастической матрицы // Автоматика и вычислительная техника, 1970. № 5. - С. 95-96.

130. Костромин Г.Я. О нахождении имплицирующего вектора для стохастической матрицы // Деп. в ВИНИТИ 10.04.72, № 4248-72 Деп. Краткое сообщение: Автоматика и вычислительная техника, 1972. № 5. - С. 17-18.

131. Чирков М.К., Шилкевич Т.П. О реализуемости вероятностных автоматов автоматами со случайными входами // Методы вычислений. Вып.6. -Л.: Изд-во ЛГУ, 1970. С. 127-136.

132. Паршенков Н.Я., Ченцов В.М. Вопросы теории вероятностных автоматов // Автоматы и управление сетями связи. М.: Наука, 1971.-С. 180-202.

133. Габбасов Н.З. О нахождении минимального имплицирующего вектора // Вероятностные методы и кибернетика.- Казань: Изд-во КГУ, 1984. С. 29-40.

134. Кузнецов С.Е., Нурмеев Н.Н., Салимов Ф.И. Задача о минимальном имплицирующем векторе // Тезисы межреспубл. научно-техн. конф. "Вероятностные автоматы и их приложения". Тбилиси: Мецниереба,1986.-С.З.

135. Kuznetsov S.E., Nurmeev N.N., Salimov F.I. The problem of minimal implicating vector // Lecture Notes in Comput. Sci. Fundamentals of Comput. Theory. Berlin: Springer-Verlag, 1987, pp. 273-278.

136. Кузнецов C.E., Нурмеев H.H., Салимов Ф.И. Задача о минимальном имплицирующем векторе // Математические вопросы кибернетики. Вып. №3. Сборник статей / Под ред. С.В. Яблонского. М.: Наука, Гл. ред. физико-математической литературы, 1991. - С. 199-216.

137. Габбасов Н.З. Задача об имплицирующем векторе и ее приложения // Вероятностные методы и кибернетика. Вып.23. Казань: Изд-во КГУ, 1987. -С.36-50.

138. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: МЦНМО, 2004. - 424 с.

139. Гиоргадзе А.Х., Джебашвили Т.Л., Сафиуллина А.Г. К вопросу определения имплицирующего вектора стохастических матриц // Сообщения АН ГрузССР.- 1982. Т. 108, № 1,- С. 49-52.

140. Гиоргадзе А.Х. Пространственно-временная декомпозиция и структурный анализ и синтез стохастических систем: Дис. д-ра. техн. наук. -Тбилиси, 1981.-320 с.

141. Гилл А. Линейные последовательностные машины. М.: Наука, 1974. -288 с.

142. Чеботарев Н.Г. Теория Галуа. Кн. 1. М.: ОНТИ НКТП СССР, 1936. -156 с.

143. Нечаев В.И. Элементы криптографии. Основы теории защиты информации. М.: Высшая школа, 1999. - 109 с.

144. Крот A.M. Дискретные модели динамических систем на основе полиномиальной алгебры. Минск: Гелиос АРВ, 2002. - 312 с.

145. D.H. Green and I.S. Taylor. Irreducible polynomials over composite Galois fields and their applications in coding techniques. Proc. IEEE, 121(9), pp. 935-939, 1974.

146. B.M. Мутгер. Основы помехоустойчивой телепередачи информации. -JI.: Энергоатомиздат. Ленингр. отд-ие, 1990. 288 с.

147. Моисил Т.К. Алгебраическая теория дискретных автоматических устройств. М.: Изд-во иностранной литературы, 1963. - 680 с.

148. Левин Б.Р., Шварц В. Вероятностные модели и методы в системах связи и управления. М.: Радио и связь, 1985. - 312 с.

149. Левин В.И. Вероятностный анализ ненадежных автоматов. Рига: Зинатне, 1969. - 234 с.

150. А.с. 2802836. Устройство для умножения в конечных полях / Харчистов Б.Ф., Финаев В.И. //Б.И. №15, 1981.

151. Сюрин В.Н., Иванов Н.Н., Альхимович В.В. Реализация вычислений в конечных полях // Зарубежная радиоэлектроника, №5. 1990. - С. 59-68.

152. Бояринов И.М. О систолических и полусистолических вычислениях в GF(2"). // Вопросы кибернетики. Разработка и использование СУПЕР-ЭВМ. -М.: Наука, 1987. С. 183-190.

153. Li H.F., Jayakumar R., Lam С. Restructuring for Fault-Tolerant Systolic Arrays // IEEE Trans, on computer, vol. 38. № 2, February 1989, pp. 307-311.

154. Jagma Sh., Aramaki T. Autonomously testable programmable logic arrays // Int. Simp, on FICS, Portland. June 1981, pp. 41-43.

155. Daehn W., Mucha J. A hardware approach to self-testing of large programmable logic arrays // IEEE Trans. Comput., vol. C-80, № 11, pp. 829-833, Nov. 1981.

156. Захаров B.M. Моделирование /-сложных цепей Маркова конечным детерминированным автоматом // Вероятностные автоматы и их приложения. -Казань: Изд-во КГУ, 1986. С. 155-161.

157. А.с. 1327099. Генератор случайных последовательностей / Захаров В.М., Баранов Г.Г. // Б.И. 1987. - № 28.

158. Lows В.А., Rushforth С.К. A cellular-array multiplier for GF(2m). IEEE Trans. Comput, 1971, v.C-20, №12, pp. 1573-1578.

159. Itoh T. and Tsujii S. Structure of parallel multipliers for a class of fields GF(2A). Inform, and Сотр., 83:21-40, 1989.

160. Hasan M.A., Wang M., Bhargava V.K. Modular construction of low complexity parallel multipliers for a class of finite fields GF(2"). IEEE Trans, on Computers, 41(8), pp. 962-971,1992.

161. Fenn S.T.J., Benaissa M., Taylor D. GF(2") multiplication and division, over the dual base. IEEE Trans, on Computers, 45(3), pp. 319-327, 1996.

162. Paar C., Fleishmann P., Roelse P. Efficient Multiplier Architectures for Galois Fields GF((24)") H IEEE Trans. Computers. 1998. № 2. Vol. 47. P. 162-170.

163. Хинчин А.Я. Понятие энтропии в теории вероятностей // Успехи математических наук, №3 (55). 1953. - с. 3-20.

164. Вентцель Е.С. Теория вероятностей. М.: Наука, 1969. - 576 с.

165. Сигорский В.П. Математический» аппарат инженера. Киев: Техника, 1975.- 768 с.

166. Математика. Большой энциклопедический словарь / Гл. ред. Ю.В. Прохоров. М.: Большая Российская энциклопедия, 2000. - 848 с.

167. Massey J.L. Cryptography and System Theory // Proc. 24th Allerton Conf. Commun., Control, Comput., Oct. 1-3. Allerton, 1986. - P. 1-8.

168. Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971. -478 с.

169. Massey J.L. Shift-register synthesis and BCH decoding // IEEE Trans. Inform. Theory, vol. IT-15, pp. 122-127, Jan. 1969.

170. Massey J.L., Ingemarsson I. The Rip van Winkle cipher a simple and provably computationally secure cipher with a finite key // Abstracts of Papers. IEEE Int. Symp. Inform. Theory, Brighton, England, June 24-28, 1985.

171. Reeds J.A., Sloane N.J.A. Shift register synthesis (modulo m) // SIAM Journal on Computing, 14(3): pp. 505-513, 1985.

172. Piper F. Stream ciphers // Elektrotechnik und Maschinenbau, vol. 104, no. 12, pp. 564-568, 1987.

173. Rueppel R.A. Analysis and Design of Stream Ciphers. Berlin: Springer-Verlag, 1986.

174. Klapper A. The vulnerability of geometric sequences based on fields of odd characteristic // Journal of Cryptology, 7(1): pp. 33-52,1994.

175. Поточные шифры. Результаты зарубежной открытой криптологии.http://www.ssl.stu.neva.ru/psw/crypto/potok/strciph.htm

176. Rueppel R.A. "Linear complexity and random sequences", in Lecture Notes in Computer Science 219; Advances in Cryptology: Proc. Eurociypt'85, F. Pilcher, Ed., Linz, Austria, April 1985, pp. 167-188. Berlin: Springer-Verlag, 1986.

177. Smeets B. The linear complexity profile and experimental results on a randomness test of sequences over the field Fq // IEEE Int. Symp. Inform. Theory, Kobe, Japan, June 19-24,1988.

178. Gottfert R., Niederreiter H. A general lower bound for the linear complexity of the product of shift-register sequences. In Advances in Cryptology -Eurocrypt '94, Springer-Verlag, Berlin.

179. Zong-duo Dai. Proof of Rueppel's linear complexity conjecture. // IEEE

180. Trans, inform. Theory, vol. 32, pp. 440-443, May 1986.

181. Niederreiter H. "Continued fractions for formal power series, pseudorandom numbers, and linear complexity of sequences", contributions to General Algebra 5, Proc. Conf. Salzburg, Teubner, Stuttgart, 1986.

182. Wang M.Z., Massey J.L. "The characteristics of all binary sequences with perfect linear complexity profiles", paper presented at Eurocrypt'86, Linkoping, Sweden, May 20-22,1986.

183. Games R.A., Chan A.H. A fast algorithm for determining the complexity of a binary sequence with period 2n // IEEE Transactions on Information Theory, IT-29: pp. 144-146, 1983.

184. Robshaw M.J.B. On evaluating the linear complexity of a sequence of least period 2n Designs, Codes and Cryptography, 4: pp. 263-269, 1994.

185. Games R.A. There are no de Bruijn sequences of span n with complexity 2n. Journal of Combinatorial Theory, Series A, 34: pp. 248-251, 1983.

186. Games R.A., Chan A.H., Key E.L. On the complexities of de Bruijn sequences. Journal of Combinatorial Theory, Series A, 33: pp. 233-246,1982.

187. Bruer J.O. On nonlinear combinations of linear shift register sequences // Proc. IEEE ISIT, les Arcs, France, June 21-25 1982.

188. Blackburn S.R. A generalisation of the discrete Fourier transform: an algorithm to determine the minimum polynomial of a periodic sequence. September 1993. Preprint.

189. Zong-duo Dai, Kencheng Zeng. "Continued Fractions and the Berlekamp-Massey Algorithm", In J. Seberry and J. Pieprzyk, editors, Advances in Cryptology -Auscrypt '90, pp. 24-31, Springer Verlag, Berlin, 1990.

190. Schaub T. A linear complexity approach to cyclic codes, Ph.D. thesis, Swiss Federal Institute of Technology, Zurich, 1988.

191. Massey J.L., Wong M.Z. "The characterization of all binary sequences with perfect linear complexity profiles", in Abstracts of Papers, Eurocrypt'86, Linkoping, Sweden, May 20-22, 1986, pp. 34A-34B.

192. Jansen C.J. "Investigations on nonlinear stream cipher systems: Construction and evaluation methods", Ph.D. thesis, Eindhoven University of Technology, The Netherlands, 1989.

193. Ziv J., Lempel A. On the complexity of finite sequences. IEEE Trans. Information Theory, 22: pp.75-81, 1976.

194. Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Trans. Information Theory, 23(3): pp. 337-343, 1977.

195. Erdmann E.D. Empirical Tests of Binary Keystreams // Master's thesis, University of London, 1992.

196. O'Connor L., Snider T. Suffix trees and string complexity // In R.A.Rueppel, editor, Advances in Cryptology Eurocrypt '92, pp. 138-152, Springer-Verlag, Berlin, 1993.

197. Chan A.H., Games R.A. On the quadratic spans of periodic sequences // In

198. G. Brassard, editor, Advances in Cryptology Crypto '89, pp. 82-89, Springer-Verlag, New York, 1990.

199. Chan A.H. On quadratic m-sequences // In R. Anderson, editor, Fast Software Encryption Cambridge Security Workshop, pp. 166-173, Springer-Verlag, Berlin, 1994.

200. Khachaturian L.H. The lower bound of the quadratic spans of de Bruijn sequences // Designs, Codes and Cryptography, 3: pp. 29-32, 1993.

201. Rueppel R.A. "Correlation immunity and the summation combiner" in Lecture Notes in Computer Science 218; Advances in Cryptology: Proc. Ciypto'85,

202. H. C. Williams Ed., Santa Barbara, CA, Aug. 18-22, 1985, pp. 260-272. Berlin: Springer-Verlag, 1986.

203. Klapper A., Goresky M. 2-adic shift registers // In R. Anderson, editor, Fast Software Encryption Cambridge Security Workshop, pages 174-178, Springer-Verlag, Berlin, 1994.

204. Klapper A., Goresky M. Feedback registers based on ramified extensions of the 2-adic numbers // Advances in Cryptology Eurocrypt '94 (LNCS vol 950), pages 215-222, Springer-Verlag, Berlin, 1995.

205. Beker H., Piper F. Cipher Systems: the Protection of Communications. -London: Northwood Books, 1982.

206. Альпин Ю.А., Захаров B.M. Теоретико-автоматный метод описания и моделирования случайных процессов // Вероятностные методы и кибернетика. Вып. 19. Казань: Изд-во КГУ, 1983. - С.10-16.

207. Энциклопедия кибернетики. В двух томах. Том 1. Киев: Главная редакция украинской советской энциклопедии, 1975. - 607 с.

208. Баранов Г.Г., Захаров В.М., Кузнецов С.Е. Синтез циклических многозначных последовательностей с заданной структурой // Кибернетика. -Киев: Институт кибернетики АН Украины, 1989, №1. С. 15-18.

209. Вероятностное прогнозирование в деятельности человека / Под ред. И.М. Фейгенберга, Г.Е. Журавлева. М.: Наука, 1977. - 392 с.

210. Бурков В.Н., Горгидзе И.А., Ловецкий С.Е. Прикладные задачи теории графов / Под ред. А .Я. Горгидзе. Тбилиси: Мецниереба, 1974. - 234 с.

211. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях. М.: КУДИЦ-ОБРАЗ, 2001. - 368 с.

212. Баранов Г.Г., Захаров В.М., Кузнецов Е.Г. Рациональная аппроксимация стохастических неразложимых матриц // Вероятностные методы и кибернетика. Казань: Изд-во Казан-го ун-та, 1987, №23. - С. 22-36.

213. Харари Ф. Теория графов. М.: Мир, 1923. - 300 с.

214. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

215. Оре О. Теория графов. 2-ое изд. М.: Наука, Главная редакция физико-математической литературы, 1980. - 336 с.

216. Нурутдинов Ш.Р., Столов E.JI. Реализация автомата асинхронной сетью // Кибернетика. Киев, 1988. - С. 108-109.

217. Сюрин В.Н., Иванов Н.Н., Альхимович В.В. Реализация вычислителей в конечных полях//Зарубежная радиоэлектроника. 1990. - №5. - С. 59-68.

218. Феллер В. Введение в теорию вероятностей и ее приложения. Т. 1. -М.: Мир, 1964.-511 с.240. . Полляк Ю.Г. Вероятностное моделирование на электронных вычислительных машинах. М.: Советское радио, 1971. - 400 с.

219. Словарь по кибернетике. Киев: Гл. ред. УСЭ им. М. П. Баумана, 1989. - 585 с.

220. Захаров В.М., Нурмеев Н.Н., Салимов Ф.И., Шалагин С.В. Классификация стохастических эргодических матриц методами кластерного и дискриминантного анализа // Исследования по информатике. Выпуск 2. -Казань: Отечество, 2000. С.91-106.

221. Гмурман В.Е. Теория вероятностей и математическая статистика. М.: Высшая школа, 2003. - 480 с.

222. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях. М.: КУДИЦ-ОБРАЗ, 2001. - 368 с.

223. Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.Б. Алгоритмические основы эллиптической криптографии. М.: МЭИ,2000.-328 с.

224. Кнут Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы. М.: Мир, 1976. - 725 с.

225. Каштанов Д.В. Сравнительный анализ статистических свойств микросхем генераторов случайных чисел // ХП Туполевские чтения: Межд. молодежная научная конференция. Материалы конференции. Казань: Изд-во Казан.гос.техн.ун-та, 2004. - Том III. - С. 72-73.

226. Гаранин М.В., Журавлев В.И., Кунегин С.В. Системы и сети передачи информации: Учеб. пособие для вузов. М.: Радио и связь, 2001. - 336 с.

227. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика. М.: Мир, 1992.- 184 с.