Криптографические методы защиты информации
Учебно-методическое пособие: Том 3
Покупка
Основная коллекция
Издательство:
РИОР
Автор:
Бабаш Александр Владимирович
Год издания: 2014
Кол-во страниц: 216
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-369-01304-5
ISBN-онлайн: 978-5-16-100192-9
Артикул: 248900.01.01
Доступ онлайн
от 96 ₽
В корзину
В данном (третьем) томе пособия представлены несколько методик построения приближенных (численно приближенных) моделей сложных автоматов, моделирующих современные дискретные устройства криптографической защиты информации. Предлагается четыре подхода к решению задачи приближенного моделирования шифрующих автоматов. Представленные результаты являются частью фундамента для построения новых методов криптографического анализа и синтеза. Они могут быть использованы в криптографической практике.
Пособие предназначено для студентов высших учебных заведений, обучающихся по различным специальностям, связанным с защитой информации. Оно содержит методический материал для ряда инновационных курсов лекций по профилю "Криптографическая защита информации". Ряд представленных результатов полезен специалистам и аспирантам, специализирующихся в указанной области. В пособии учтены тенденции развития образования в части перехода обучения на бакалавриат и магистратуру.
Тематика:
ОКСО:
- ВО - Бакалавриат
- 02.03.02: Фундаментальная информатика и информационные технологии
- 10.03.01: Информационная безопасность
- ВО - Магистратура
- 02.04.02: Фундаментальная информатика и информационные технологии
- 10.04.01: Информационная безопасность
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
В Ы С Ш Е Е О Б Р А З О В А Н И Е В Ы С Ш Е Е О Б Р А З О В А Н И Е У Ч Е Б Н О Е П О С О Б И Е У Ч Е Б Н О Е П О С О Б И Е А.В. Бабаш КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ Том 3
КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ Том 3 УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ Второе издание Рекомендовано Учебно-методическим объединением по образованию в области прикладной информатики в качестве учебно-методического пособия для студентов высших учебных заведений, обучающихся по специальности 080801 «Прикладная информатика» и другим междисциплинарным специальностям Москва РИОР ИНФРА-М А.В. БАБАШ
УДК 004.056(075.8) ББК 32.973.202я73 Б12 Бабаш А.В. Криптографические методы защиты информации. Т. 3: Учеб.-метод. пособие. — 2-е изд. — М.: РИОР: ИНФРА-М, 2014. — 216 с. — (Высшее образование: Бакалавриат). ISBN 978-5-369-01304-5 (РИОР) ISBN 978-5-16-009336-9 (ИНФРА-М) Пособие предназначено для студентов высших учебных заведений, обучающихся по специальности «Прикладная информатика (в экономике)». Оно также содержит методический материал для ряда инновационных курсов лекций по профилю «Информационная безопасность» и может быть использовано для блока дисциплин этого профиля. Ряд представленных результатов полезен специалистам и аспирантам, специализирующимся в указанной области. Б12 УДК 004.056(075.8) ББК 32.973.202я73 ISBN 978-5-369-01304-5 (РИОР) ISBN 978-5-16-009336-9 (ИНФРА-М) Оригинал-макет подготовлен в Издательском Центре РИОР Подписано в печать 15.08.2013. Формат 60х88/8. Бумага офсетная. Гарнитура Newton. Печать офсетная. Усл. печ. л. 26,46. Уч.-изд. л. 20,57. Тираж 300 экз. Заказ № Цена свободная. ТК 248900 – 12734 – 150813 ООО «Издательский Центр РИОР» 127282, Москва, ул. Полярная, д. 31В. Email: info@rior.ru www.rior.ru ООО «Научно-издательский центр ИНФРА-М» 127282, Москва, ул. Полярная, д. 31В, стр. 1. Тел.: (495) 380-05-40, 380-05-43. Факс: (495) 363-92-12 E-mail: books@infra-m.ru http://www.infra-m.ru © Бабаш А.В., 2014
СОДЕРЖАНИЕ Введение ............................................................................................................................. 7 Определения, обозначения и сокращения ................................................................... 8 Часть 1. ЭКСПЕРИМЕНТЫ С АВТОМАТАМИ Глава 1. Определение заключительных состояний автомата по входной и выходной последовательностям. Автоматы с конечной памятью................................ 11 1.1. Основные понятия ................................................................................................................. 11 1.2. Свойства автоматов с конечной памятью........................................................................... 12 1.3. Алгоритм определения автоматов с конечной памятью.................................................... 13 Глава 2. Определение входного слова автомата по его начальному состоянию и выходной последовательности. Автоматы без потери информации........................... 15 2.1. Основные понятия ................................................................................................................. 15 2.2. Задача распознавания неизвестной входной последовательности автомата по его начальному состоянию и выходной последовательности............................................. 16 2.3. Автоматы без потери информации конечного порядка ..................................................... 17 Глава 3. Об экспериментах по распознаванию информации о входном слове автомата .............................................................................................................................. 19 3.1. Понятие закрытого однородного эксперимента с автоматами ......................................... 19 3.2. Закрытый однородный эксперимент по распознаванию информации о первом входном символе входного слова автомата по начальному состоянию и выходной последовательности ............................................................................. 23 3.3. Закрытый однородный эксперимент по распознаванию информации о входном слове перестановочного автомата по начальному состоянию и выходной последовательности ................................................................................................ 25 3.4. Закрытый однородный эксперимент по распознаванию информации о последнем символе входного слова автомата по заключительному состоянию и выходной последовательности ............................................................................. 26 3.5. Закрытый однородный эксперимент по распознаванию информации о входном слове автомата по заключительному состоянию и выходной последовательности ............................................................................................... 28 Глава 4. О восстановлении информации о входном слове перестановочного автомата Медведева по начальным и заключительным состояниям............................. 29 4.1. Основные обозначения и постановка задачи восстановления информации о входном слове перестановочного автомата Медведева по начальным и заключительным состояниям ................................................................................................... 29 4.2. Основные утверждения......................................................................................................... 30 4.3. Оценки параметров ............................................................................................................... 33 4.4. Оценки параметров полугруппы автомата.......................................................................... 34 4.5. Структура отношения эквивалентности П*k ..................................................................... 35 4.6. Алгоритм проверки свойства автомата А приближенно восстанавливать входные слова длины k по L начальным и заключительным состояниям .............................. 36 Глава 5. Определение входного слова векторного перестановочного автомата по множеству пар начальных и заключительных состояний с помощью вероятностной модели их статистических зависимостей ................................................ 38 5.1 Постановка задачи и план ее решения ................................................................................ 38 5.2. Реализация модернизации идеи Матсуи............................................................................. 39 5.3. Первый этап метода.............................................................................................................. 40 5.4. Второй этап метода............................................................................................................... 41 5.5. Третий этап метода ............................................................................................................... 42
5.6. Дополнительные пояснения ................................................................................................. 43 5.7. Об эффективности алгоритма.............................................................................................. 47 Глава 6. Случайное тестирование конечных автоматов по входной и выходной последовательностям..................................................................................... 48 Часть 2. МОДЕЛИ АВТОМАТОВ НА ОСНОВЕ СЛЕДСТВИЙ ЗАКОНОВ ИХ ФУНКЦИОНИРОВАНИЯ Глава 7. Модели автоматов–следствия уравнений их функционирования.................... 52 7.1. Основные обозначения......................................................................................................... 52 7.2. Построение моделей-следствий автомата ......................................................................... 53 7.3. Изучение примитивности степеней автомата..................................................................... 55 Глава 8. Модели автоматов, построенные с помощью обработки их выходных последовательностей инициальными автоматами........................................................... 59 8.1. Построение моделей-следствий автомата. Постановка задачи....................................... 59 8.2. Описание слабо неприведенных автоматов относительно В(Х,Y).................................. 60 Глава 9. Функции - модели автоматов, построенные на основе следствий уравнений их функционирования....................................................................................... 65 9.1. Построение моделей-следствий автомата ......................................................................... 65 Часть 3. МОДЕЛИ АВТОМАТОВ НА ОСНОВЕ РАССТОЯНИЙ ХЭММИНГА Глава 10. Модели автоматов, построенные на основе расстояния Хэмминга между их табличными заданиями ...................................................................................... 73 10.1. О задаче определения начального состояния автомата по его входной и выходной последовательностям.............................................................................................. 73 10.2. Использование статистического аналога конечного автомата, построенного с помощью искажений его частичных функций переходов............................... 74 10.3. Использование статистического аналога конечного автомата, построенного с помощью искажений его частичных функций переходов и выходов ...................................................................................................................................... 86 10.4. Пороговый критерий с уровнем (m,c)................................................................................. 87 10.5. Метод максимального правдоподобия.............................................................................. 88 Глава 11. Приближенные модели автоматов, построенные на основе расстояния Хэмминга между их выходными последовательностями............................. 95 11.1. Введение .............................................................................................................................. 95 11.2. Основные понятия и предварительные результаты ........................................................ 95 11.3. Вычисление значения меры неотличимости состояний по кратному эксперименту с автоматами........................................................................................................ 101 11.4. Приближенные модели связных перестановочных автоматов....................................... 102 Глава 12. Неотличимость состояний конечных автоматов по мере 0........................... 111 Глава 13. Приближенные модели автоматов, построенные на основе преднеотличимости состояний и частичных гомоморфизмов ......................................... 113 13.1. Преднеотличимость состояний конечных автоматов ...................................................... 113 13.2. Преднеотличимость состояний автоматов без выхода ................................................... 113 13.3. Преднеотличимость состояний произвольных автоматов .............................................. 115 13.4. Частичные гомоморфизмы автоматов без выхода .......................................................... 117 13.5. Частичные гомоморфизмы произвольных автоматов ..................................................... 124
Глава 14. Метод приближенных моделей в решении задач определения начальных состояний и входных слов автомата............................................................... 128 14.1. Постановка задачи .............................................................................................................. 128 14.2. Определение начального состояния и входного слова автомата по его выходному слову............................................................................................................... 130 14.3. Определение входного слова автомата по его начальному состоянию и выходному слову ....................................................................................................................... 132 14.4. Определение входного слова автомата по его начальному и заключительному состояниям .................................................................................................. 134 14.5. Определение входного слова автомата по его начальному и заключительному состояниям .................................................................................................. 136 14.6. Метод сведения изложенных задач к задачам решения системы уравнений с искаженными правыми частями ............................................................................ 138 Часть 4. МОДЕЛИ АВТОМАТОВ НА ОСНОВЕ ОБОБЩЕНИЯ ПОНЯТИЯ ГОМОМОРФИЗМА АВТОМАТОВ Глава 15. Многозначные гомоморфизмы конечных автоматов ....................................... 141 15.1. Обозначения ........................................................................................................................ 141 15.2. Многозначные гомоморфизмы автоматов ........................................................................ 141 15.3. Описание многозначных гомоморфизмов для связных перестановочных автоматов ....................................................................................................... 145 15.4. Образы СМГ связных перестановочных автоматов......................................................... 147 15.5. Образы МГ произвольного автомата без выходов........................................................... 148 15.6. Пример использования МГ автомата ................................................................................ 149 15.7. Некоторые обобщения многозначных гомоморфизмов автомата.................................. 150 Глава 16. Модели конечных автоматов, построенные на основе гомоморфизмов поведения................................................................................................. 152 16.1. Обозначения ........................................................................................................................ 152 16.2. Обобщенный гомоморфизм поведения автоматов.......................................................... 152 16.3. Гомоморфизм поведения автоматов................................................................................. 154 16.4. Построение всех конгруэнций поведения автомата без выходов .................................. 155 16.5. Полностью определенные образы автомата при гомоморфизмах поведения........................ 156 16.6. Частные случаи гомоморфизма поведения автоматов ................................................... 158 16.7. Обобщенный многозначный гомоморфизм автоматов.................................................... 160 Глава 17. Методы определения начального состояния автомата по входной и выходной последовательностям с использованием обобщений понятия гомоморфизма автоматов .................................................................................................. 163 17.1. Постановка задачи определения начального состояния автомата по входной и выходной последовательностям с использованием гомоморфного образа ассоциированного с ним автомата Медведева................................... 163 17.2. Определение начального состояния автомата по входной и выходной последовательностям с использованием гомоморфного образа ассоциированного с ним автомата Медведева ........................................................................ 164 17.3. Определение начального состояния перестановочного автомата по входным и соответствующим выходным последовательностям с использованием меры неотличимости состояний ............................................................... 170 17.4. Определение начального состояния s(0) автомата A по его входной Q=x(1),x(2),…,x(L) и выходной A(s(0),Q)=Z последовательностям................ 171 17.5. Определение начального состояния автомата по входной и выходной последовательностям с использованием -неотличимых состояний.................................... 172 17.6. Определение начального состояния перестановочного автомата по входной и выходной последовательностям с использованием -гомоморфизмов автоматов..................................................................................................... 173
17.7. Определение начального состояния s0 автомата по известным входным словам XN и соответствующим им выходным словам A(s0,)=Q() .................................. 175 17.8. Определение начального состояния 1 2 0 0 , s s по выходной последовательности A 1 2 0 0 , s s =g(1),g(2),…,g(N) последовательного соединения автоматов................................. 176 17.9. Гомоморфизмы автоматов по мере ................................................................................ 177 Глава 18. Системные множества со свойством подстановки .......................................... 181 18.1. Введение .............................................................................................................................. 181 18.2. Основные определения и обозначения работы [52. А. Фридман, П. Менон “Теория и проектирования переключательных схем”. М., “Мир”, 1978]............................. 181 18.3. Системные множества со свойством подстановки........................................................... 182 18.4. Неточности, обнаруженные в работе [52] ......................................................................... 182 18.5. Алгоритм поиска всех системных множеств со свойством подстановки работы [52] .............................................................................................................. 184 18.6. Новый алгоритм поиска всех системных множеств со свойством подстановки ........................................................................................................... 185 18.7. Поиск систем слабой импримитивности для заданного автомата.................................. 188 Часть 5. ПОМЕХОУСТОЙЧИВЫЕ АВТОМАТЫ Глава 19. Автоматные отображения периодических последовательностей, не размножающие искажений............................................................................................. 189 19.1. Введение .............................................................................................................................. 189 19.2. Основные обозначения и понятия ..................................................................................... 190 19.3. Описание множества GA(XП,YП, =, μ)............................................................................... 191 19.4. Описание множества GA(XП,YП,≥,μ)................................................................................. 195 Глава 20. Автоматные отображения слов, размножающие искажения в метриках Хэмминга и Левенштейна не более чем в К раз............................................ 201 20.1. Историческая справка ......................................................................................................... 201 20.2. Обозначения и основные понятия ..................................................................................... 201 20.3. Описание множества А((X*,Y*,К)...................................................................................... 203 20.4. Описание множества АG((X*,Y*,К).................................................................................... 210 20.5. Описание множества АG((X*,Y*,D,К).................................................................................. 212 Список использованных источников..................................................................................... 214
ВВЕДЕНИЕ В данном (третьем) томе пособия представлены несколько методик построения приближенных (численно приближенных) моделей сложных автоматов, моделирующих современные дискретные устройства криптографической защиты информации. Пусть задан некоторый конечный автомат A. Для криптографических приложений задача моделирования в теории автоматов состоит в том, чтобы, исходя из данных о внешнем функционировании автомата A, построить «более простой» автомат A', достаточно адекватно описывающий поведение автомата A. Под словами «более простой» обычно понимают автомат с меньшим числом состояний по сравнению с исходным автоматом. При этом автомат A' может описывать внешнее поведение автомата A не полностью, а приближенно. В этом случае говорят о приближенных моделях автоматов. Мы предлагаем четыре подхода к решению задачи приближенного моделирования шифрующих автоматов. Первый подход к решению проблемы моделирования состоит в построении для исходного автомата A нового автомата, являющегося некоторым следствием законов функционирования автомата A. Второй подход состоит в том, что на множестве всех автоматов с общими входным и выходным алфавитами вводится функция близости , для определения которой используется расстояние Хэмминга между выходными последовательностями. Третий подход к построению приближенных моделей обобщает идеи приближения сложной дискретной функции более простой функцией (например, линейной). В автоматной трактовке этот подход состоит в замене исходного автомата A на его статистический аналог A'. Аналог выбирается так, чтобы решаемая задача для автомата A имела для автомата A' достаточно простое по сложности решение, и одновременно табличное задание автомата A' ненамного отличалось от табличного задания автомата A. В этом случае замена A на A' позволяет снизить сложность решения за счет некоторой ненадежности ее решения. Четвертый подход состоит в получении следствий из уравнений функционирования автомата A путем обобщения понятия гомоморфизма автоматов и построения «обобщенных» образов автомата A при таких обобщенных гомоморфизмах. Этот подход связан с тем, что гомоморфный образ автомата в ряде практических задач играет роль его модели. Суть обобщения понятия гомоморфизма состоит в рассмотрении бинарных отношений вместо отображений, входящих в определение гомоморфизма. Таким образом, расширяется класс автоматов, имеющих гомоморфный образ с меньшим числом состояний, до класса автоматов, имеющих обобщенный гомоморфный образ с меньшим числом состояний. Представленные результаты являются частью фундамента для построения новых методов криптографического анализа и синтеза. Они могут быть использованы в криптографической практике. Пособие предназначено для студентов высших учебных заведений, обучающихся по различным специальностям, связанным с защитой информации. Оно содержит методический материал для ряда инновационных курсов лекций по профилю «Криптографическая защита информации». Ряд представленных результатов полезен специалистам и аспирантам, специализирующихся в указанной области. В пособии учтены тенденции развития образования в части перехода обучения на бакалавриат и магистратуру.
, Z, 1,2,…,k, Z={1,2,…,k}.
:
XY – X Y;
Xk – X k;
|M| – ;
h(M’) – M’h: MV. hM’, mM h(m) hm.
A=(X, S, Y, h, f), :
X – , ();
X* – X;
S – , ();
Y – , ();
h: SX S – ;
f: SY – .
t=1,2… . A s(t)S x(t)X, A f(s(t),x(t)) A s(t+1)=h(s(t),i(t)).
, f(s,x)=(s) xX, sS, : SY, A :
A=(X, S, Y, h, ).
X |X|=1, , A = (S,Y,h,).
: . s xX () s`=h(x,s). (x,y), y=f(x,s).
, |X| . , s`
sA, s s`. (s,s`) m(s,s`) s s`, , s s`.
A = (S,Y,h,) , , .
() , (s,s`) s s`.
.
A=(X,S,Y,h,f).
(h x)xX(fx)xXh f :
hx: SS, hx(s)=h(x,s); fx:SY, fx(s)=f(x,s).
A :
A=(X, S, Y, (hx)xX, (fx)xX).
:
hx: SS – A 9
xX, hx(s) = h(s, x), sS (hx: hxs = h(s, x);
hx(Z) – Z, ZS hx;
fx: SY – xX, fx(s) = f(s,x), sS (fx : fxs = f(s, x)).
, .
:
P = x(1), x(2), …, x(k), x(j)X, j{1,2,…, k} – k A;
, , P, , , : =x(1),x(2),…,x(k), J=
x(1),x(2),…,x(k);
|P| – P A;
(
1)
(
2)
(1)
....
x k
x k
x
P
h
h
h
h
– SS, A P=x(1),x(2),…,x(k);
( )
x
h s 1-s;
....
( )
( )
(
1)
(1)
s
x k
x k
x
h
h
h
k-s.
(
1)
(
1)
(1)
....
( )
P
k
k
f
f
h
h
h
x k
x
x
x
– SY, A P= x(1), x(2), …., x(k);
fPs P(s) – , s
() ;
A(s,P) =y1,y2,….,yk, yiY, j[1, k] – A, P= x(1), x(2), …., x(k) A sS;
(s,P)=s1,s2,…,sj,… – =(X,S,Y,h,f), s=s1 S;
G=<(hx)xX>A S , (hx)xX A S ;
A , (hx)xX S S : S S, (S).
, X, S, Y, h, f (), , A = (XA, SA, YA, hA , fA). A , A’, , , (X’, S’, Y’, h’,
f’). , , A B GAGB, .
.
1. s s’ A k-, A(s, P)) = A(s’,P)
P = x(1), x(2),…, x(k) k A. k-.
2. s s’ A , k-k. (). 1. [6, 10]. A = (X, S, Y, h, f) (- 1)-. k-, S A k-. : Nk= ( 1 2 , ,....., kl k k k N N N ), k j N , j [1, l k] – k-A, lk – k-A. A Nj , j [1, l], S : N = (N1, N2, …., Nl), l – A. 3. R A, NR= N NkN k<R. 4. A (), Nj= 1 j[1, l]. , A , l = .
1. , , (, .). . 1 . . [1,2,3]. 1.1. , (P,R) A=(X,S,Y,(hx)xX,(fx)xX), sS, A(s, P)=R. 1. A , 1, 2, 1 0 , 2 1 g 12+1 , (x1,x2,…,xk,…, y1,y2,…,yk,…) A yj=g(xj, xj-1,…, xj- 1, yj-1,yj-2,…, 2 j). (1) , j-j-, 12. , 12+1 g: 1 2 1 X Y Y . (1) A , xj, xj-1,…, xj- 1. . A. ’=(X,S’,Y,(h’x)xX,(f’x)xX), . . ’ xj-1,…, xj-1, yj-1,yj-2,…, 2 j, S’= 1 2 X Y . (1) yj=g(xj,sj). (2) xX f’x’ f’xs= g(x,s). ’ , 12 sj=(xj-1,…, xj-1, yj-1,yj-2,…, 2 j), sj+1=(xj,xj-1,…, xj-1+1, yj,yj-1,yj-2,…, 2 1 j)= =(xj,xj-1,…, xj-1+1, g(xj, xj-1,…, xj- 1, yj-1,yj-2,…, 2 j),yj-1,yj-2,…, 2 1 j). , sj+1F (xj, xj-1,…, xj- 1, yj-1,yj-2,…, 2 j). , sj+1sj+1 =F(xj, sj). xX f’x’ h’xs= F(x, s). 1, 2x yA, =max(12) A. (1) yj=G(xj, xj-1,…, xj-, yj-1,yj-2,…, j) (3) G. A yj(xj, xj-1,…, xj-+1, yj-1,yj-2,…, 1 j), , A . , A j-yjj-. , . 1.2. 1. A : sj=g(xj-1,x2,…,xj-, yj-1,yj-2,…,yj- ). . . (xj-1,xj-2,…,xj-, yj-1,yj-2,…,yj- ), sj. s1, s2, : A(s1, xj-,…, xj-2,xj-1)=yj- ,…, yj-2, yj-1, A(s2, xj-,…, xj-2,xj-1)= yj- ,…, yj-2, yj-1 hxj-1,xj-2,…,xj- s1hxj-1,xj-2,…,xj- s2. A , hxj-1,xj-2,…,xj- s1, hxj-1,xj-2,…,xj- s2 , ij,ij+1,…,ij+n 1, A(hxj-1,xj-2,…,xj- s1, ij,ij+1,…,ij+n)= yj,yj+1,…,yj+n-1, yj+n A(hxj-1,xj-2,…,xj- s2, ij,ij+1,…,ij+n)= yj,yj+1,…,yj+n-1, y”j+n . A , : A(s1, xj-,…, xj-2,xj-1,ij,ij+1,…,ij+n)=yj- ,…, yj-2, yj-1,yj,yj+1,…,yj+n-1, yj+n, A(s2, xj-,…, xj-2,xj-1,ij,ij+1,…,ij+n)=yj- ,…, yj-2, yj-1,yj,yj+1,…,yj+n-1, y”j+n,
+n+1, n+1 . yj+ny”j+n. . 2. A : sj=g(xj-1,x2,…,xj-, yj-1,yj-2,…,yj- ), A , . . s x1,x2,… A yj=h(sj, xj). , yj=h(sj,xj)= h(g(xj-1,x2,…,xj-, yj-1,yj-2,…,yj- ), xj)= =f(xj, xj-1,x2,…,xj-, yj-1,yj-2,…,yj- ) f. A . . , , , , . . 3. A=(X,S,Y,(hx)xX,(fx)xX) , | | (| | 1) 2 S S . . 1 A sj=g(xj-1,x2,…,xj-, yj-1,yj-2,…,yj- ). k x1,x2,…,xk, y1,y2,…,yks1, s2, : A(x1,x2,…,xk, s1)= A(x1,x2,…,xk, s2)= y1,y2,…,yk, hx1,x2,…,xk s1= hx1,x2,…,xk s2. , x1,x2,…,x, y1,y2,…,ys1, s2: hx1s1hx1s2, hx2x1s1hx2x1s2, hx3x2x1s1hx3x2x1s2, …, h-1,…,x1s1h-1,…,x1s2, h,x-1,…,x1s1= h,x-1,…,x1s1. S, | | (| | 1) S S . , | | (| | 1) 2 S S . 1.3. A=(X,S,Y,(hx)xX,(fx)xX) . , , . Qk(s) – k, A, s. 1,
A , s, s’ Q-1(s)Q-1(s’)Q(s)Q(s’)= . 1, A , Qt(s)Qt(s’)| | (| | 1) 2 S S t s, s’. A. (1) k=1. (2) Qk(s), sS. (3) ) Qk(s)Qk(s’) , s, s’, (4). (b) Qk(s)Qk(s’) =s, s’, k A. (4) ) | | (| | 1) 1 2 S S k , k 1 (2). (b) | | (| | 1) 2 S S k , A .
2 . . [3–8]. 2.1. A=(X,S,Y,(hx)xX,(fx)xX) – . (s,P) (AM(s,P)) () A , P sS. (., , [1, 3, 6]). 1. sS A , x(1),x(2),…,x(L), x`(1), x`(2),…,x`(L) L=Ls x(j), x`(j)X, hx(L)hx(L-1)...hx(1)s=hx`(L)hx`(L-1)...hx`(1)s, fx(1)s= fx`(1)s (1) fx(2)hx(1)s=fx`(2)hx`(1)s .......................... fx(L)hx(L-1)...hx(1)s=fx`(L)hx`(L-1)...hx`(1)s sS , . s (. 2.1) L. . 2.1 s s’ x`(1)]y(1) x(1)]y(1) x(2)]y(2) x`(2)]y(2) x(L-1)]y(L-1) x`(L-1)]y(L-1) 1221111111) x(L)]y(L) x`(L)]y(L)
Доступ онлайн
от 96 ₽
В корзину