авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

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


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |

«НАЦИОНАЛЬНАЯ АКАДЕМИЯ НАУК УКРАИНЫ ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ И МЕХАНИКИ В.В. Скобелев АВТОМАТЫ НА АЛГЕБРАИЧЕСКИХ ...»

-- [ Страница 6 ] --

Тогда, выбрав произвольный входной символ x1 K k, эксперимен татор определяет текущее состояние f(q0, x1 ) исследуемого автомата Mf MFk,m, и ситуация сводится к рассмотренному выше случаю.

Предположим, что экспериментатор не имеет возможности наблюдать состояние исследуемого автомата Mf MFk,m ни на одном промежу точном вычислении, а имеет возможность наблюдать только финальное состояние автомата Mf.

Тогда единственным способом поиска одного (не важно, какого имен но) решения u (K m )t уравнения (5.80) является случайный выбор входного слова. При этом, вероятность того, что при случайном выбо ре входного слова u (K m )t истинно равенство (5.80), определяется формулой (5.78).

Аналогичным образом, единственным способом поиска одного (не важно, какого именно) решения (u, u) (K m )t (K m )t (u = u) уравне ния (5.81) является случайный выбор входных слов. При этом, вероят ность того, что при случайном выборе входных слов u, u (K m )t (u = u) истинно равенство (5.81), определяется формулой (5.79).

Высокая сложность поиска входного слова u (K m )t, для которо го истинно равенство (5.80), а также поиска входных слов u, u (K m )t (u = u), для которых истинно равенство (5.81), обосновывают возмож ность использования семейства хэш-функций Hf (f Fk,m ) в алгоритмах защиты информации. При этом начальное состояние q0 K k автомата Mf MFk,m целесообразно использовать в качестве секретного сеансо вого ключа используемой хэш-функции.

Рассмотрим теперь задачу параметрической идентификации семей ства хэш-функций Hf (f Fk,m ).

Пусть f Fk,m – такое отображение, что f(qt, xt+1 ) = F(a1,..., ar, qt, xt+1 ) (t Z+ ), где a1,..., ar K – параметры, т.е. система уравнений (5.57) имеет вид Mf : qt+1 = F(a1,..., ar, qt, xt+1 ) (t Z+ ), (5.84) где отображение F известно экспериментатору.

Предположим, что экспериментатору не известны значения парамет ров, входящих в систему уравнений (5.84), но экспериментатор, кроме возможности наблюдать финальное состояние автомата Mf MFk,m, имеет также возможность наблюдать состояние исследуемого автомата Mf на всех промежуточных вычислениях.

Тогда идентификация семейства хэш-функций (5.84) является зада чей параметрической идентификации автомата, принадлежащего задан ному семейству автоматов над кольцом K.

При возможности экспериментатора проводить только простой экспе римент решение задачи параметрической идентификации автомата сво дится к поиску входного слова x1... xn (K m )n заранее неизвестной длины n N с целью формирования и решения над кольцом K системы уравнений qi = F(a1,..., ar, qi1, xi ) (i = 1,..., n) (5.85) относительно неизвестных a1,..., ar K.

При возможности экспериментатора проводить l-кратный экспери мент (где l N (l 2) – фиксированное число) решение задачи пара метрической идентификации автомата сводится к поиску l-элементного (i) (i) множества входных слов x1... xni (K m )ni (i = 1,..., l), длины ni ко торых заранее неизвестны, с целью формирования и решения над коль цом K системы уравнений (i) (i) (i) qj = F(a1,..., ar, q0, x1... x1 ) (i = 1,..., l;

j = 1,..., ni ) (5.86) относительно неизвестных a1,..., ar K.

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

В этом случае для решения задачи параметрической идентификации автомата достаточно сформировать и решить над кольцом систему урав нений q = F(a1,..., ar, q, x) (q K k, x K m ) (5.87) относительно неизвестных a1,..., ar K.

Отметим, что в кольце с делителями нуля при достаточно большом значении k N решение любой из систем уравнений (5.85)-(5.87) явля ется сложной задачей из-за перебора, обусловленного именно наличием делителей нуля.

Поэтому, при использовании семейства хэш-функций Hf (f Fk,m ) в алгоритмах защиты информации параметры a1,..., ar, входящие в уравнение (5.84), целесообразно использовать либо в качестве секретного ключа средней длительности, либо в качестве долговременного секрет ного ключа.

Замечание 5.16. Если экспериментатор, кроме возможности наблюдать финаль ное состояние автомата Mf MFk,m, имеет также возможность наблюдать состояние исследуемого автомата Mf на всех промежуточных вычислениях, то методом, изло женным в п.5.2, может быть построена имитационная модель заданного семейства хеш-функций. Оценка сложности построения и точности такой модели осуществля ется на основе алгебраических свойств отображения F.

5.4. Автоматы, определенные в терминах идеалов кольца.

В процессе исследования различных объектов, определенных над конечным кольцом, естественно возникает необходимость анализа их свойств при наличии тех или иных дополнительных ограничений, сфор мулированных в терминах этого кольца. Именно такой, по своей сути, подход и применялся (в явном или неявном виде) при исследовании, представленном в разделах 2-5.

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

Исходя из сказанного выше, исследуем свойства автоматов Мили и Мура над кольцом K = (K, +, ·) Kf nt Kf nt (|K| 2), функции пере 1 ходов и выходов которых являются алгебраическими суммами функции от состояния автомата и функции от входного символа при условии, что значение каждой компоненты функции переходов принадлежит фикси рованным идеалам кольца.

5.4.1. Исследуемые модели.

Для каждого числа n N обозначим через An,1 семейство автоматов Мили, определенных системой рекуррентных соотношений { qt+1 = f1 (qt ) + f3 (xt+1 ) (t Z+ ), M1 : (5.88) yt+1 = f2 (qt ) + f4 (xt+1 ) а через An,2 семейство автоматов Мура, определенных системой рекур рентных соотношений { qt+1 = f1 (qt ) + f3 (xt+1 ) (t Z+ ), M2 : (5.89) yt+1 = f2 (qt+1 ) где fi : K n K n (i = 1, 2, 3, 4), а qt K n, xt K n и yt K n являются, соответственно, состоянием автомата, входным и выходным символом в момент t.

Если множество K n интерпретируется, соответственно, как входной алфавит, как множество состояний или как выходной алфавит автомата Mi An,i (i = 1, 2), то будем обозначать множество K n, соответственно, через Xn, Qn и Yn.

Обозначим через Ainv (i = 1, 2) семейство всех обратимых автоматов n,i Mi An,i. Известно, что (см., напр., [80]):

1) M1 Ainv тогда и только тогда, когда f4 является биекцией мно n, n жества K на себя;

2) M2 Ainv тогда и только тогда, когда f2 и f3 являются биекциями n, множества K n на себя.

При этом, для автомата M1 Ainv обратным автоматом является n, автомат { qt+1 = f1 (qt ) + f3 (f1 (xt+1 f2 (qt ))) (t Z+ ), M1 : yt+1 = f4 (xt+1 f2 (qt )) а для автомата M2 Ainv обратным автоматом является автомат n, { qt+1 = f1 (xt+1 ) (t Z+ ).

M1 : 1 yt+1 = f3 (f2 (xt+1 ) f1 (qt )) Замечание 5.17. Отметим, что если пара обратимых автоматов (Mi, Mi1 ) (i = 1, 2) рассматривается в качестве математической модели поточного шифра, то в процессе «шифрование-расшифрование» автоматы Mi и Mi1 движутся в простран стве состояний по одной и той же траектории в одном и том же направлении.

Для каждого идеала I кольца K в фактор-кольце K/I = (K/I, +I, ·I ) множество K/I является разбиением множества K на |K| · |I|1 блоков, каждый из которых содержит |I| элементов.

Отсюда вытекает, что для каждого вектора I = (I1,..., In ), где Ij (j = 1,..., n) – идеал кольца K, в фактор-кольце Kn /I = (K/I1 · · · K/In, +I, ·I ) множество K/I1 · · · K/In является разбиением множества K n на n n |K| · |Ij | блоков, каждый из которых содержит |Ij | элементов.

n j=1 j= (i) (i) При этом для любых элементов ai = (a1,..., an ) K n (i = 1, 2) истин на формула (1) (1) a1 a2 (mod I) (1 j n)(aj aj (mod Ij )).

Каждые два вектора (r) (r) Ir = (I1,..., In ) (r = 1, 2), (5.90) (r) где Ij (r = 1, 2;

j = 1,..., n) – идеал кольца K, определяют семейства автоматов An,i (I1, I2 ) = {Mi An,i | V al f1 = I1 &V al f2 = I2 } (i = 1, 2).

Отметим, что для каждого автомата M An,1 (I1, I2 ) An,2 (I1, I2 ) истинны равенства |Qn /ker f1 | = |I1 | (5.91) и |Qn /ker f2 | = |I2 |. (5.92) Обозначим через Ainv (I1, I2 ) (i = 1, 2) семейство всех обратимых ав n,i томатов Mi An,i (I1, I2 ).

Замечание 5.18. Так как I2 = (K,..., K ) Ainv (I1, I2 ) =, n, n раз то при I2 = (K,..., K ) для упрощения обозначений будем писать Ainv (I1 ) вместо n, n раз Ainv (I1, I2 ).

n, Исследуем свойства семейств автоматов An,i (I1, I2 ) (i = 1, 2) и Ainv (I1, I2 ) (i = 1, 2).

n,i 5.4.2. Комбинаторные характеристики исследуемых моде лей.

Оценим мощности семейств автоматов An,i (I1, I2 ) (i = 1, 2) и Ainv (I1, I2 ) (i = 1, 2).

n,i Утверждение 5.6. Равенства |An,i | = |K|(5i)n|K| (i = 1, 2) (5.93) истинны для всех чисел n N.

Доказательство. Для каждого числа n N число отображений f : K n K n равно |K|n|K|.

При построении автомата M1 An,1 осуществляется независимый выбор отображений fi : K n K n (i = 1, 2, 3, 4). Поэтому, |An,1 | = (|K|n|K| )4 = |K|4n|K|. (5.94) При построении автомата M2 An,2 осуществляется независимый выбор отображений fi : K n K n (i = 1, 2, 3). Следовательно, |An,2 | = (|K|n|K| )3 = |K|3n|K|. (5.95) Из истинности равенств (5.94) и (5.95) вытекает, что для всех чисел n N истинны равенства (5.93).

Утверждение 5.7. Равенства ( )in |K|!

|Ainv | = |An,i | (i = 1, 2) (5.96) |K||K| n,i истинны для всех чисел n N.

Доказательство. Для каждого числа n N число отображений f : K n K n, являющихся биекциями, равно (|K|!)n.

При построении автомата M1 Ainv осуществляется независимый вы n, бор отображений fi : K n K n (i = 1, 2, 3, 4). Следовательно, используя равенство (5.94), получим ( )n |K|!

|An,1 | = (|K| ) (|K|!) = |An,1 | inv n|K| 3 n. (5.97) |K||K| Аналогичным образом, при построении автомата M2 Ainv осуществ n, ляется независимый выбор отображений fi (i = 1, 2, 3). Следовательно, используя равенство (5.95), получим ( ) |K|!

|An,2 | = |K| ((|K|!) ) = |An,2 | inv n|K| n. (5.98) |K||K| Из истинности равенств (5.97) и (5.98) вытекает, что для всех чисел n N истинны равенства (5.96).

Следствие 5.4. При i = 1, 2 асимптотическое равенство |Ainv | = |An,i |( 2|K| · e|K| (1 + O(|K|1 )))in (|K| ) (5.99) n,i истинно для всех чисел n N.

Доказательство. Из формулы Стирлинга вытекает, что |K|! = 2|K| · |K||K| e|K| (1 + O(|K|1 )) (|K| ). (5.100) Из истинности равенств (5.96) и (5.100) вытекает, что для всех чисел i {1, 2} и n N истинны равенства (5.99).

(r) (r) Теорема 5.4. Для каждых векторов Ir = (I1,..., In ) (r = 1, 2), (r) где Ij (r = 1, 2;

j = 1,..., n) – идеал кольца K, равенства |An,i (I1, I2 )| = ( ) (r) |Ij | |An,i | 2 n (r) |Ij | (|Ij | h)|K| (i = 1, 2) (5.101) (r) · h (1) = |K| 2n|K| h r=1 j=1 h= истинны для всех чисел n N.

Доказательство. Известно, что (см., напр., [51]) для каждых чи сел l, m N (m l) число сюръекций l-элементного множества на m элементное множество равно () m hm (m h)l.

sl,m = (1) (5.102) h h= Из формулы (5.102) вытекает, что для каждого вектора (r) (r) Ir = (I1,..., In ) (r = 1, 2), (r) где Ij (r = 1, 2;

j = 1,..., n) – идеал кольца K число всех таких отоб ражений fr : K n K n (r = 1, 2), что V al fr = Ir, равно n tIr = s|K|,|I (r) | = j j= ( ) (r) |Ij | n (r) |Ij | (|Ij | h)|K| (r = 1, 2).

(r) h (1) = (5.103) h j=1 h= При построении автомата M1 An,1 (I1, I2 ) осуществляется независи мый выбор отображений fi (i = 1, 2, 3, 4). Следовательно, из равенств (5.94) и (5.103) вытекает, что |An,1 (I1, I2 )| = |K| 2n|K| tIr = r= ( ) (r) |Ij | 2 n (r) |Ij | (|Ij | h)|K| = (r) = |K| 2n|K| h (1) h r=1 j=1 h= ( ) (r) |Ij | |An,1 | 2 n (r) |Ij | (|Ij | h)|K|.

(r) · h (1) = (5.104) |K| 2n|K| h r=1 j=1 h= При построении автомата M2 An,2 (I1, I2 ) осуществляется независи мый выбор отображений fi (i = 1, 2, 3).

Следовательно, из равенств (5.95) и (5.103) вытекает, что |An,2 (I1, I2 )| = |K| n|K| tIr = r= ( ) (r) |Ij | 2 n (r) |Ij | (|Ij | h)|K| = (r) = |K| n|K| h (1) h r=1 j=1 h= ( ) (r) |Ij | |An,2 | 2 n (r) |Ij | (|Ij | h)|K|.

(r) · h (1) = (5.105) |K| 2n|K| h r=1 j=1 h= Из истинности равенств (5.104) и (5.105) вытекает, что для всех чисел n N истинны равенства (5.103).

(r) (r) Теорема 5.5. Для каждых векторов Ir = (I1,..., In ) (r = 1, 2), (r) где Ij (r = 1, 2;

j = 1,..., n) – идеал кольца K, равенства |Ainv (I1, I2 )| = n, ( ) (r) |Ij | 2 n |Ainv | (r) |Ij | (|Ij | h)|K| n,1 (r) · h (1) = (5.106) |K|2n|K| h r=1 j=1 h= истинны для всех чисел n N.

Доказательство. Так как при построении автомата M1 Ainv осу n, ществляется независимый выбор отображений fi (i = 1, 2, 3, 4), то из равенств (5.97) и (5.103) вытекает, что (|K|!)n K 3n|K| 2 |Ainv (I1, I2 )| n n|K| = (|K|!) K tIr = tIr = n, K 2n|K| r=1 r= ( ) (r) |Ij | |Ainv | |Ainv | 2 2 n (r) |Ij | (|Ij | h)|K|, n,1 n,1 (r) h (1) = 2n|K| tIr = 2n|K| h K K r=1 r=1 j=1 h= что и требовалось доказать.

(1) (1) Теорема 5.6. Для каждого вектора I1 = (I1,..., In ) (r = 1, 2), где (1) Ij (j = 1,..., n) – идеал кольца K, равенства (1) ( ) |Ij | |Ainv | n (1) |Ij | (|Ij | h)|K| n,2 (1) |An,2 (I1 )| = inv h (1) (5.107) |K|n|K| j=1 h h= истинны для всех чисел n N.

Доказательство. Так как при построении автомата M2 Ainv осу n, ществляется независимый выбор отображений fi (i = 1, 2, 3), то из ра венств (5.97) и (5.103) вытекает, что |Ainv | (|K|!)2n K n|K| n, |Ainv (I1 )| 2n = (|K|!) tI1 = tI1 = n|K| tI1 = n,2 n|K| K K (1) ( ) |Ij | |Ainv | n (1) |Ij | (|Ij | h)|K|, n,1 (1) h (1) = n|K| h K j=1 h= что и требовалось доказать.

Из установленных выше оценок мощностей семейств автоматов An,i (I1, I2 ) (i = 1, 2), Ainv (I1, I2 ) и Ainv (I1 ) вытекает, что исследуемые n,1 n, модели определяют достаточно обширные множества семейств автома тов, содержащие нетривиальные подмножества семейств обратимых ав томатов. Это обстоятельство обосновывает актуальность исследования рассматриваемых семейств автоматов с теоретической и с прикладной точки зрения.

5.4.3. Структурные свойства исследуемых моделей.

Обозначим через fM,q0 (M An,1 (I1, I2 ) An,2 (I1, I2 ), q0 Qn ) отоб ражение входной полугруппы X+ в выходную полугруппу, реализуемое n инициальным автоматом (M, q0 ).

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

Из (5.88) и (5.89) вытекает, что:

1) множества состояний-близнецов автомата M1 An,1 (I1, I2 ) совпа дают с элементами фактор-множества Qn /ker f1 ker f2 ;

2) множества состояний-близнецов автомата M2 An,2 (I1, I2 ) совпа дают с элементами фактор-множества Qn /ker f1.

Отсюда вытекает, что мощность множества автоматных отображений FM = {fM,q0 | q0 Qn } (M An,1 (I1, I2 ) An,2 (I1, I2 )), реализуемых автоматом M, удовлетворяет следующим неравенствам:

|FM | |Qn /ker f1 ker f2 |, (5.108) если M An,1 (I1, I2 ), и |FM | |Qn /ker f1 |, (5.109) если M An,2 (I1, I2 ).

Из (5.91), (5.92), (5.108) и (5.109) вытекает, что |FM | min{|Qn |, |I1 | · |I2 |}, если M An,1 (I1, I2 ), и |FM | |I1 |, если M An,2 (I1, I2 ).

Охарактеризуем более подробно структуру множества отображений FM (M An,1 (I1, I2 ) An,2 (I1, I2 )).

Рассмотрим автомат M1 An,1 (I1, I2 ).

Определим на входном алфавите Xn отношения эквивалентности n, и n,2 следующим образом: для всех x, x Xn :

x n,1 x f3 (x ) f3 (x ) (mod I1 ) (5.110) и x n,2 x f4 (x ) f4 (x ) (mod I2 ). (5.111) Из (5.110) и (5.111) вытекает, что ker f3 n,1 (5.112) и ker f4 n,2, (5.113) Положим n,12 = n,1 n,2. (5.114) Замечание 5.19. Из (5.112)-(5.114) вытекает, что ker f3 ker f4 n,12.

Распространим отношения эквивалентности n,i (i = 1, 2) и n,12 на входную полугруппу X+ следующим образом: для каждого числа k N n и для всех входных слов u = x1... xk Xk и u = x... x Xk n 1 n k u n,i u (1 j k)(xj n,i x ) (i = 1, 2) (5.115) j и u n,12 u (1 j k)(xj n,12 x ). (5.116) j (r) (r) (r) Теорема 5.7. Пусть n N и Ir = (I1,..., In ) (r = 1, 2), где Ij (r = 1, 2;

j = 1,..., n) – идеал кольца K. Тогда для каждого автомата M1 An,1 (I1, I2 ) и каждого числа k N формула u n,12 u (q0, q Qn )(1 j k)(qj q (mod I1 )& 0 j &yj y (mod I2 )) (5.117) j истинна для всех u = x1... xk Xk и u = x... x Xk.

n 1 n k Доказательство. Пусть u = x1... xk Xk и u = x... x Xk.

n 1 n k Из 1-го рекуррентного соотношения системы рекуррентных соотно шений (5.88) находим, что для всех чисел j = 0, 1,..., k q qj+1 = (f1 (q ) f1 (qj )) + (f3 (x ) f3 (xj+1 )). (5.118) j+1 j j+ Так как f1 (q ) f1 (qj ) I1 (j = 0, 1,..., k 1) для всех qj, q Qn, j j то из (5.110), (5.115) и (5.118) вытекает, что (q0, q Qn )(1 j k)(qj q (mod I1 )) 0 j (q0, q Qn )(1 j k)(f3 (xj ) f3 (x ) (mod I1 )) 0 j u n,1 u. (5.119) Аналогичным образом, из 2-го рекуррентного соотношения систе мы рекуррентных соотношений (5.88) находим, что для всех чисел j = 0, 1,..., k y yj+1 = (f2 (q ) f2 (qj )) + (f4 (x ) f4 (xj+1 )). (5.120) j+1 j j+ Так как f2 (q ) f2 (qj ) I1 (j = 0, 1,..., k 1) для всех qj, q Qn, j j то из (5.111), (5.115) и (5.120) вытекает, что (q0, q Qn )(1 j k)(yj y (mod I2 )) 0 j (q0, q Qn )(1 j k)(f4 (xj ) f4 (x ) (mod I2 )) 0 j u n,2 u. (5.121) Из (5.114), (5.119) и (5.121) вытекает, что формула (5.117) истинна.

Обозначим через Y+ /mod I2 фактор-множество множества Y+, опреде n ленное следующим образом: для каждого числа k N и всех выходных слов v = y1... yk Yk и v = y... y Yk n 1 n k v v (mod I2 ) (1 j k)(yj y (mod I2 )).

j Из теоремы 5.7 вытекает, что истинно следующее следствие.

(r) (r) (r) Следствие 5.5. Пусть n N и Ir = (I1,..., In ) (r = 1, 2), где Ij (r = 1, 2;

j = 1,..., n) – идеал кольца K. Тогда для каждого автомата M1 An,1 (I1, I2 ) и любых его начальных состояний q0, q Qn истинна диаграмма f (M1, q0 ) + X+ Yn n nat mod I nat ~ n, g M X+ + Yn mod I ~ n, n nat ~ n,12 nat mod I f (M1, q0 ) + X+ Yn n где отображение gM1 определяется автоматом M1.

Таким образом, для каждого автомата M1 An,1 (I1, I2 ) при любых его начальных состояниях q0, q Qn отображения f(M1,q0 ) и f(M1,q ) ре 0 ализуют одно и то же отображение gM1 фактор-множества X+ /n,12 в n + фактор-множество Yn /mod I2.

Рассмотрим автомат M2 An,1 (I1, I2 ).

Определим на множестве X+ отношение эквивалентности n,1 сле n дующим образом: для каждого числа k N и для всех входных слов u = x1... xk Xk и u = x... x Xk n 1 n k u n,1 u u n,1 u & &(q0, q Qn )(1 j k)(qj q (ker f2 )), (5.122) 0 j где n,1 – отношение эквивалентности на множестве X+, определенное в n соответствии с формулами (5.110) и (5.115).

(r) (r) (r) Теорема 5.8. Пусть n N и Ir = (I1,..., In ) (r = 1, 2), где Ij (r = 1, 2;

j = 1,..., n) – идеал кольца K. Тогда для каждого автомата M2 An,2 (I1, I2 ) и каждого числа k N формула u n,1 u (q0, q Qn )(1 j k)(qj q (mod I1 )& 0 j &yj = y ) (5.123) j истинна для всех u = x1... xk Xk и u = x... x Xk.

n 1 n k Доказательство. В системах рекуррентных соотношений (5.88) и (5.89) первые рекуррентные соотношения совпадают. Поэтому из формул (5.119) и (5.122) вытекает, что u n,1 u (q0, q Qn )(1 j k)(qj q (mod I1 ))& 0 j &(q0, q Qn )(1 j k)(qj q (ker f2 )) 0 j (q0, q Qn )(1 j k)(qj q (mod I1 ))& 0 j &(q0, q Qn )(1 j k)(yj = y ) 0 j (q0, q Qn )(1 j k)(qj q (mod I1 )&yj = y ), 0 j j что и требовалось доказать.

Из теоремы 5.8 вытекает, что истинно следующее следствие.

(r) (r) (r) Следствие 5.6. Пусть n N и Ir = (I1,..., In ) (r = 1, 2), где Ij (r = 1, 2;

j = 1,..., n) – идеал кольца K. Тогда для каждого автомата M2 An,2 (I1, I2 ) и любых его начальных состояний q0, q Qn истинна диаграмма X+ n f (M 2, q0 ) nat ~n, g M I+ X+ ~ n,12 n nat ~n, f (M 2, q0 ) X+ n где отображение gM2 определяется автоматом M2.

Таким образом, для каждого автомата M2 An,2 (I1, I2 ) при любых его начальных состояниях q0, q Qn отображения f(M2,q0 ) и f(M2,q ) ре 0 + ализуют одно и то же отображение gM1 фактор-множества Xn /n,1 в множество I+.

5.5. Выводы.

В настоящем разделе исследованы семейства автоматов Мили и Му ра, заданные системами рекуррентных соотношений с параметрами над конечным кольцом. Основные результаты состоят в следующем:

1. Разработан математический аппарат, предназначенный для постро ения имитационной модели семейства автоматов, заданного системой ре куррентных соотношений над конечным кольцом.

2. Для всех комбинаций понятий «в наихудшем случае» и «в сред нем», представляющих интерес с позиции прикладной теории алгорит мов, определено понятие «точность имитационной модели» семейства ав томатов, заданного системой рекуррентных соотношений над конечным кольцом.

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

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

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

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

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

Возможных следующие направления дальнейших исследований.

Во-первых, это выделение нетривиальных классов семейств автома тов над конечным кольцом, для которых любая -точная имитационная модель при всех значениях числа, достаточно близких к единице, су щественно сложнее, чем система рекуррентных соотношений, определя ющая семейство автоматов.

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

В-третьих, это детальный анализ для конкретных типов конечных ко лец при наличии тех или иных соотношений между векторами идеалов I и I2 свойств автоматов, функции переходов и выходов которых являются алгебраическими суммами функции от состояния автомата и функции от входного символа при условии, что значение каждой компоненты функ ции переходов принадлежит фиксированным идеалам кольца.

6. АВТОМАТЫ НА МНОГООБРАЗИИ НАД КОНЕЧНЫМ КОЛЬЦОМ Понятие «многообразие» является одним из основных понятий алгебраической геометрии [24.34,59,111,112], которая детально проработана над алгебраически за мкнутыми полями. Последние, как известно, являются бесконечными полями.

Специальным видом многообразия являются алгебраические кривые. Среди них важную роль играют эллиптические кривые [32,46-48,128,129,207], имеющие много численные применения при решении теоретических и прикладных задач. Успешные применения эллиптических кривых над конечными полями в процессе решения за дач защиты информации привели к формированию эллиптической криптографии [10,12,14,110] – одного из наиболее перспективных в настоящее время разделов со временной криптографии.

Кроме того, в последнее время при решении задач защиты информации фрагмен тарно начинают использоваться вычисления над кольцами вычетов.

Все сказанное выше обосновывает актуальность, как с теоретической, так и с при кладной точки зрения, исследования свойств автоматных моделей, определенных на многообразиях над конечными кольцами. Решению этой задачи и посвящен настоя щий раздел.

В п.6.1 исследовано строение алгебраических кривых 2-го и 3-го порядков над конечным ассоциативно-коммутативным кольцом. Найдены множества разложимых линий. Охарактеризованы множества особых точек исследуемых линий. Исследу ются методы приведения линии 2-го порядка к каноническому виду. Установлены условия существования кратных корней для некоторых линий 3-го порядка. В п.6. выделены 2 типа многообразий над произвольным конечным кольцом: многообразия с алгеброй и параметризованные многообразия. В п.6.3 исследуются автоматы Мили и Мура, определенные на многообразии с алгеброй, а в п.6.4 – автоматы Мили и Мура, определенные на параметризованном многообразии. Установлены автоматные характеристики исследуемых моделей. Охарактеризованы гомоморфизмы исследу емых моделей в терминах гомоморфизмов рассматриваемых многообразий. В п.6. исследованы множества автоматов Мили и Мура, определенные на группах точек эл липтических кривых над конечным полем. Охарактеризованы множества групповых и приведенных автоматов, а также множества эквивалентных состояний не приве денных автоматов. Найдены достаточные условия, при которых автомат не является сильно связным. Решены задача идентификации начального состояния автомата, а также задача построения точной асимптотически имитационной модели автомата.

П.6.6 содержит ряд заключительных замечаний.

Результаты автора, представленные в настоящем разделе, опубликованы в рабо тах [76,77,80,85,90,92-94,97,98,100,102,212,213].

6.1. Кривые 2-го и 3-го порядков над конечным кольцом.

Простейшими нелинейными многообразиями над кольцом K Kf nt являются кривые линии 2-го и 3-го порядков, определенные уравнением над этим кольцом. Исследуем строение таких кривых в предположении, что K = (K, +, ·) Kf nt Kf nt.

1 6.1.1. Анализ кривых 2-го порядка.

Общее уравнение кривой 2-го порядка над кольцом K имеет вид a11 x2 + a12 xy + a22 y 2 + a1 x + a2 y + a0 = 0, (6.1) где a11, a12, a22, a1, a2, a0 K, причем (a11, a12, a22 ) = (0, 0, 0).

Для многочлена f (x, y) = a11 x2 +a12 xy+a22 y 2 +a1 x+a2 y+a0 возможны следующие три ситуации.

Ситуация 6.1. Многочлен f (x, y) неразложим над кольцом K.

Ситуация 6.2. Для любых многочленов fi K[x, y] (i = 1, 2) степени mi 1 (i = 1, 2), удовлетворяющих равенству f (x, y) = f1 (x, y)f2 (x, y), истинно неравенство m1 + m2 2.

Ситуация 6.3. Существуют многочлены fi K[x, y] (i = 1, 2) степени mi = 1 (i = 1, 2), удовлетворяющие равенству f (x, y) = f1 (x, y)f2 (x, y).

Предположим, что имеет место ситуация 6.2. Тогда f (x, y) – много член наименьшей степени, определяющий кривую 2-го порядка. Ана лиз кривой осуществляется непосредственно на основе уравнения (6.1).

Предположим, что имеет место ситуация 6.3. При известном разложе нии многочлена f (x, y) уравнение (6.1) естественно представить в виде (b1 x + b2 y + b0 )(c1 x + c2 y + c0 ) = 0. (6.2) Из (6.2) вытекает, что множество точек кривой может быть пред ставлено в виде = S1 S2 S3, где S1 – объединение множеств решений одно-параметрического семей ства систем линейных уравнений { b1 x + b2 y + b0 = ( K), A :

c1 x + c 2 y + c0 = S2 – объединение множеств решений одно-параметрического семейства систем линейных уравнений { b1 x + b2 y + b 0 = ( K\{0}), B :

c 1 x + c2 y + c 0 = а S3 – объединение множеств решений двух-параметрического семейства систем линейных уравнений { b1 x + b 2 y + b0 = (, K\{0}, = 0).

C, :

c1 x + c2 y + c0 = Замечание 6.1. Таким образом, построение в явном виде множества точек кри вой 2-го порядка в ситуациях 6.1 и 6.2 эквивалентно поиску множества решений нелинейного уравнения (6.1) от двух переменных, а в ситуации 6.3 – поиску множеств решений трех семейств A ( K), B ( K\{0}) и C, (, K\{0}, = 0) систем линейных уравнений. Если кольцо K не содержит делителей нуля, то S3 =.

Охарактеризуем особые точки кривой (6.1).

Множеством особых точек кривой (6.1) является множество решений системы уравнений Dx (a11 x2 + a12 xy + a22 y 2 + a1 x + a2 y + a0 ) = Dy (a11 x2 + a12 xy + a22 y 2 + a1 x + a2 y + a0 ) = a11 x2 + a12 xy + a22 y 2 + a1 x + a2 y + a0 = 2a11 x + a12 y + a1 = a12 x + 2a22 y + a2 = 0.

a11 x2 + a12 xy + a22 y 2 + a1 x + a2 y + a0 = Отсюда вытекает, что истинно следующее утверждение.

Утверждение 6.1. Кривая, определенная уравнением (6.1), име ет особые точки тогда и только тогда, когда существует такое решение (x0, y0 ) системы линейных уравнений { 2a11 x + a12 y = a, (6.3) a12 x + 2a22 y = a что (x0, y0 ) – точка кривой.

Замечание 6.2. Иными словами, когда для решения (x0, y0 ) системы линейных уравнений (6.3) истинно равенство a11 x2 + a12 x0 y0 + a22 y0 + a1 x0 + a2 y0 + a0 = 0.

Если характеристика кольца K равна 2, то система уравнений (6.3) принимает вид { a12 y = a.

a12 x = a Отсюда вытекает, что истинно следующее утверждение.

Утверждение 6.2. Пусть характеристика кольца K равна 2. Тогда кривая, определенная уравнением (6.1):

1) имеет единственную особую точку, если a12 K inv и a11 a2 + a12 a1 a2 + a22 a2 + a0 a2 = 0;

2 1 2) является гладкой кривой, если либо a12 K inv и a11 a2 + a12 a1 a2 + a22 a2 + a0 a2 = 0, 2 1 либо a12 K inv и, кроме того, a1 K inv или a2 K inv.

Охарактеризуем множество точек кривой (6.1).

1. Пусть { a3i,3i =. (6.4) aii = a12 = ai = где либо i = 1, либо i = 2.

Если (6.4) истинно при i = 1, то уравнение (6.1) принимает вид a22 y 2 + a2 y + a0 = 0, (6.5) а если при i = 2, то уравнение (6.1) принимает вид a11 x2 + a1 x + a0 = 0. (6.6) Следовательно, кривая состоит из всех таких точек (x0, y0 ) K 2, что при i = 1 (соответственно, при i = 2) элемент y0 (соответственно, элемент x0 ) – корень уравнения (6.5) (соответственно, уравнения (6.6)) над кольцом K. В частности, если уравнение (6.5) (соответственно, урав нение (6.6)) не имеет решений над кольцом K, то =.

2. Пусть a3i,3i = a = a12 = 0. (6.7) ii ai = где либо i = 1, либо i = 2.

Если (6.7) истинно при i = 1, то имеет место следующая теорема.

Теорема 6.1. Если характеристика кольца K отлична от 2, a1 = 0, a22 = 0, a11 = a12 = 0 и существуют такие элементы b, c K\{0}, что { a22 = cb, (6.8) a2 = 2cb то кривая, определенная уравнением (6.1), состоит из всех таких точек (x0, y0 ) K 2, что (w0, u0 ) = (by0 + 1, x0 ) является корнем уравнения cw2 + a1 u + (a0 c) = 0 (6.9) над кольцом K.

Доказательство. Пусть характеристика кольца K отлична от 2.

Если a1 = 0, a22 = 0, a11 = a12 = 0, то уравнение (6.1) принимает вид a22 y 2 + a1 x + a2 y + a0 = 0. (6.10) Подставив (6.8) в (6.10), получим c(by + 1)2 + a1 x + (a0 c) = 0. (6.11) Положив w = by + 1 и u = x в (6.11), получим уравнение (6.9).

Отсюда вытекает, что (x0, y0 ) тогда и только тогда, когда (w0, u0 ) = (by0 + 1, x0 ) – корень уравнения (6.9) над кольцом K.

Если (6.7) истинно при i = 2, то имеет место следующая теорема.

Теорема 6.2. Если характеристика кольца K отлична от 2, a2 = 0, a11 = 0, a11 = a12 = 0 и существуют такие элементы b, c K\{0}, что a11 = cb2 и a1 = 2cb, то кривая, определенная уравнением (6.1), состоит из всех таких точек (x0, y0 ) K 2, что (w0, u0 ) = (bx0 + 1, y0 ) является корнем уравнения cw2 + a1 u + (a0 c) = 0 над кольцом K.

Доказательство теоремы 6.2 аналогично доказательству теоремы 6.1.

3. Пусть a11 = a22 = 0 и a12 = 0. Имеет место следующая теорема.

Теорема 6.3. Пусть a11 = a22 = 0 и a12 = 0. Тогда:

1) если a1 = a2 = 0, то кривая, определенная уравнением (6.1), состоит из всех таких точек (x0, y0 ) K 2, что (x0, y0 ) – корень уравнения a12 xy + a0 = 0 (6.12) над кольцом K;

2) если a2 = 0 и существует такой элемент c K\{0}, что a2 = ca12, то кривая, определенная уравнением (6.1), состоит из всех таких точек (x0, y0 ) K 2, что (u0, v0 ) = (a12 y0 +a1, x0 +c) является корнем уравнения uv + (a0 ca1 ) = 0 (6.13) над кольцом K;

3) если a1 = 0 и существует такой элемент c K\{0}, что a1 = ca12, то кривая, определенная уравнением (6.1), состоит из всех таких точек (x0, y0 ) K 2, что (u0, v0 ) = (a12 x0 +a2, y0 +c) является корнем уравнения uv + (a0 ca2 ) = 0 (6.14) над кольцом K.

Доказательство. Если a11 = a22 = 0 и a12 = 0, то уравнение (6.1) принимает вид a12 xy + a1 x + a2 y + a0 = 0. (6.15) Если a1 = a2 = 0, то уравнение (6.15) совпадает с уравнением (6.12).

Отсюда вытекает, что кривая, определенная уравнением (6.1), состоит из всех таких точек (x0, y0 ) K 2, что (x0, y0 ) – корень уравнения (6.12) над кольцом K, что и требовалось доказать.

Пусть a2 = 0 и существует такой элемент c K\{0}, что a2 = ca12.

Тогда a12 xy + a1 x + a2 y + a0 = x(a12 y + a1 ) + ca12 y + a0 = = x(a12 y + a1 ) + c(a12 y + a1 ) + (a0 ca1 ) = (a12 y + a1 )(x + c) + (a0 ca1 ).

Следовательно, уравнение (6.15) принимает вид (a12 y + a1 )(x + c) + (a0 ca1 ) = 0. (6.16) Положив u = a12 y + a1 и v = x + c в (6.16), получим уравнение (6.13).

Отсюда вытекает, что кривая, определенная уравнением (6.1), со стоит из всех таких точек (x0, y0 ) K 2, что (u0, v0 ) = (a12 y0 + a1, x0 + c) – корень уравнения (6.13) над кольцом K, что и требовалось доказать.

Пусть a1 = 0 и существует такой элемент c K\{0}, что a1 = ca12.

Тогда a12 xy + a1 x + a2 y + a0 = y(a12 x + a2 ) + ca12 x + a0 = = y(a12 x + a2 ) + c(a12 x + a2 ) + (a0 ca2 ) = = (a12 x + a2 )(y + c) + (a0 ca2 ).

Отсюда вытекает, что уравнение (6.15) принимает вид (a12 x + a2 )(y + c) + (a0 ca2 ) = 0. (6.17) Положив u = a12 x + a2 и v = y + c в (6.17), получим уравнение (6.14).

Следовательно, кривая, определенная уравнением (6.1), состоит из всех таких точек (x0, y0 ) K 2, что (u0, v0 ) = (a12 x0 + a2, y0 + c) – корень уравнения (6.14) над кольцом K, что и требовалось доказать.

4. Пусть { aii = 0 (i = 1, 2).

aj = 0 (j = 1, 2) Имеет место следующая теорема.

Теорема 6.4. Пусть характеристика кольца K отлична от 2. Если aii = 0 (i = 1, 2), aj = 0 (j = 1, 2) и существуют такие элементы b1, b2, c, d K\{0}, что a11 = cb a12 = 2cb1 b a = cb2, (6.18) 22 a1 = db a2 = db то кривая, определенная уравнением (6.1), состоит из всех таких точек (x0, y0 ) K 2, что w0 = b1 x0 + b2 y0 является корнем уравнения cw2 + dw + a0 = 0 (6.19) над кольцом K.

Доказательство. Пусть характеристика кольца K отлична от 2, aii = 0 (i = 1, 2) и aj = 0 (j = 1, 2).

Подставив (6.18) в (6.1), получим a11 x2 + a12 xy + a22 y 2 + a1 x + a2 y + a0 = cb2 x2 + 2cb1 b2 xy + cb2 y 2 + db1 x + db2 y + a0 = 1 c(b2 x2 + 2b1 b2 xy + b2 y 2 ) + d(b1 x + b2 y) + a0 = 1 c(b1 x + b2 y)2 + d(b1 x + b2 y) + a0 = 0. (6.20) Положив w = b1 x + b2 y в (6.20), получим уравнение (6.19).

Отсюда вытекает, что кривая, определенная уравнением (6.1), со стоит из всех таких точек (x0, y0 ) K 2, что w0 = b1 x0 + b2 y0 – корень уравнения (6.19) над кольцом K.

5. Пусть aii = =0, (6.21) a 3i,3i a12 = где либо i = 1, либо i = 2.

Если (6.21) истинно при i = 1, то уравнение (6.1) принимает вид x(a11 x + a12 y) + a1 x + a2 y + a0 = 0, (6.22) а если при i = 2, то уравнение (6.1) принимает вид y(a22 y + a12 x) + a1 x + a2 y + a0 = 0. (6.23) Следовательно, если (6.21) истинно при i = 1 (соответственно, при i = 2), то кривая, определенная уравнением (6.1), состоит из всех та ких точек (x0, y0 ) K 2, что (x0, y0 ) – корень уравнения (6.22) (соответ ственно, уравнения (6.23)) над кольцом K. В частности, если уравнение (6.22) (соответственно, уравнение (6.23)) не имеет решений над кольцом K, то =.

6. Пусть aii = 0 (i = 1, 2) и либо a1 = 0, либо a2 = 0.

Если a1 = 0, то уравнение (6.1) принимает вид x(a11 x + a12 y) + a22 y 2 + a2 y + a0 = 0, (6.24) а если a2 = 0, то уравнение (6.1) принимает вид y(a22 y + a12 x) + a11 x2 + a1 x + a0 = 0. (6.25) Пусть характеристика кольца K отлична от 2.

Если существуют такие элементы b, c, d K, что a22 = db2, a2 = 2dbc и a0 = dc2, то уравнение (6.24) принимает вид x(a11 x + a12 y) + d(by + c)2 = 0, (6.26) а если же существуют такие элементы b, c, d K, что a11 = db2, a1 = 2dbc и a0 = dc2, то уравнение (6.25) принимает вид y(a22 y + a12 x) + d(bx + c)2 = 0. (6.27) Отсюда вытекает, что если aii = 0 (i = 1, 2) и a1 = 0 (соответственно, a2 = 0), то кривая, определенная уравнением (6.1), состоит из всех таких точек (x0, y0 ) K 2, что (x0, y0 ) – корень уравнения (6.26) (соот ветственно, уравнения (6.27)) над кольцом K.

Построим канонические формы кривых 2-го порядка над кольцом K.

Рассмотрим линейное преобразование () (u) x =A, (6.28) y v где ( ) 11 A=. (6.29) 21 Подставив (6.29) в (6.28) и выполнив действия, получим { x = 11 u + 12 v. (6.30) y = 21 u + 22 v Будем говорить,что линейная форма h(x, y) = a1 x + a2 y аннулируется в результате применения линейного преобразования (6.30) тогда и только тогда, когда h(11 u + 12 v, 21 u + 22 v) = 0u + 0v.

Лемма 6.1. Линейная форма h(x, y) = a1 x + a2 y (6.31) над кольцом K аннулируется в результате применения линейного преоб разования (6.30) тогда и только тогда, когда равенства { a1 11 + a2 21 =. (6.32) a1 12 + a2 22 = истинны кольцом K.

Доказательство. Подставив (6.30) в (6.31), получим h(11 u + 12 v, 21 u + 22 v) = a1 (11 u + 12 v) + a2 (21 u + 22 v) = = (a1 11 + a2 21 )u + (a1 12 + a2 22 )v. (6.33) Из (6.33) вытекает, что равенство h(11 u + 12 v, 21 u + 22 v) = 0u + 0v истинно тогда и только тогда, когда истинны равенства (6.32).

Следствие 6.1. Если a1 K inv или a2 K inv, то любое линейное преобразование (6.30), аннулирующее линейную форму (6.31), является необратимым линейным преобразованием над кольцом K.

Доказательство. Пусть линейное преобразование (6.30) аннулиру ет линейную форму (6.31).

Предположим, что a1 K inv. Тогда { { 11 = a1 a2 a1 11 + a2 21 =.

12 = a1 a2 a1 12 + a2 22 = 0 Следовательно, det(A) = 11 22 12 21 = a1 a2 21 22 + a1 a2 22 21 = 0, 1 откуда вытекает, что линейное преобразование (6.30), аннулирующее ли нейную форму (6.31), является необратимым над кольцом K.

В случае, когда a2 K inv, доказательство осуществляется аналогич ным образом.

Выясним, к какому виду в результате применения линейного преоб разования (6.30) может быть приведена квадратичная форма f (x, y) = a11 x2 + a12 xy + a22 y 2, (6.34) где a11, a12, a22 K ((a11, a12, a22 ) = (0, 0, 0)).

Теорема 6.5. Над кольцом K в результате линейного преобразования (6.30) квадратичная форма (6.34) может быть приведена к виду g(u, v) = b11 u2 + b22 v 2 (6.35) тогда и только тогда, когда существуют такие 11, 12, 21, 22 K, что 2(a11 11 12 + a22 21 22 ) + a12 (11 22 + 12 21 ) = 0. (6.36) При этом коэффициенты b11 и b22 определяются равенствами 2 b11 = a11 11 + a12 11 21 + a22 21 (6.37) и 2 b22 = a11 12 + a12 12 22 + a22 22. (6.38) над кольцом K.

Доказательство. Применив линейное преобразование (6.30) к квад ратичной форме (6.34), получим g(u, v) = f (11 u + 12 v, 21 u + 22 v) = a11 (11 u2 + 211 12 uv + 12 v 2 )+ 2 +a12 (11 21 u2 + (11 22 + 12 21 )uv + 12 22 v 2 )+ +a22 (21 u2 + 221 22 uv + 22 v 2 ) = (a11 11 + a12 11 21 + a22 21 )u2 + 2 2 2 +(2(a11 11 12 + a22 21 22 ) + a12 (11 22 + 12 21 ))uv+ +(a11 12 + a12 12 22 + a22 22 )v 2.

2 (6.39) Из (6.39) вытекает, что истинность равенства (6.36) является необхо димым и достаточным условием приведения квадратичной формы (6.34) к виду (6.35). При этом, коэффициенты b11 и b22 определяются, соответ ственно, равенством (6.37) и (6.38).

Из теоремы 6.5 непосредственно вытекает, что истинны следующие три следствия.

Следствие 6.2. Над кольцом K в результате линейного преобразо вания (6.30) квадратичная форма (6.34) может быть приведена к виду g(u, v) = b11 u2 (6.40) тогда и только тогда, когда существуют такие 11, 12, 21, 22 K, что { 2(a11 11 12 + a22 21 22 ) + a12 (11 22 + 12 21 ) =. (6.41) 2 a11 12 + a12 12 22 + a22 22 = При этом, коэффициент b11 определяется равенством (6.37).

Следствие 6.3. Над кольцом K в результате линейного преобразо вания (6.30) квадратичная форма (6.34) может быть приведена к виду g(u, v) = b22 v 2 (6.42) тогда и только тогда, когда { 2(a11 11 12 + a22 21 22 ) + a12 (11 22 + 12 21 ) =. (6.43) 2 a11 11 + a12 11 21 + a22 21 = При этом, коэффициент b22 определяется равенством (6.38).

Следствие 6.4. Над кольцом K в результате линейного преобразо вания (6.30) квадратичная форма (6.34) может быть приведена к виду g(u, v) = b12 uv (6.44) тогда и только тогда, когда { 2 a11 11 + a12 11 21 + a22 21 =. (6.45) 2 a11 12 + a12 12 22 + a22 22 = При этом, коэффициент b22 определяется равенством b12 = 2(a11 11 12 + a22 21 22 ) + a12 (11 22 + 12 21 ) (6.46) над кольцом K.

Необходимость выделения в отдельный случай выражения b12 uv обу словлена тем, что не всегда в кольце K это выражение с помощью обра тимого линейного преобразования { u = U + V v = U + V может быть приведен к виду U 2 + V 2.

Критерием возможности такого приведения является существование таких элементов,,, K, что = и + = 0.

Замечание 6.3. Некоторые из установленных выше равенств упрощаются, если K – кольцо характеристики 2.

Действительно, равенство (6.36) принимает вид a12 (11 22 + 12 21 ) = 0, (6.47) а равенство (6.46) принимает вид b12 = a12 (11 22 + 12 21 ). (6.48) Из леммы 6.1, теоремы 6.5 и следствий 6.2-6.4 вытекают следующие достаточные условия приведения к каноническому виду кривой, опре деленной над кольцом K уравнением (6.1), в результате применения ли нейного преобразования (6.30).

Кривая, определяемая над кольцом K уравнением (6.1), примене нием линейного преобразования (6.30):

1) может быть приведена к виду b11 u2 + b22 v 2 + a0 = 0, (6.49) если a1 11 + a2 21 = ;

(6.50) a + a2 22 = 1 2(a11 11 12 + a22 21 22 ) + a12 (11 22 + 12 21 ) = 2) может быть приведена к виду b11 u2 + a0 = 0, (6.51) если a1 11 + a2 21 = a + a = 1 12 2 ;

(6.52) 2(a11 11 12 + a22 21 22 ) + a12 (11 22 + 12 21 ) = a 2 + a + a 2 = 11 12 12 12 22 22 3) может быть приведена к виду b22 v 2 + a0 = 0, (6.53) если a1 11 + a2 21 = a + a = 1 12 2 ;

(6.54) 2(a11 11 12 + a22 21 22 ) + a12 (11 22 + 12 21 ) = a 2 + a + a 2 = 11 11 12 11 21 22 4) может быть приведена к виду b12 uv + a0 = 0, (6.55) если a1 11 + a2 21 = a + a = 1 12 2. (6.56) a11 11 + a12 11 21 + a22 21 = 2 a 2 + a + a 2 = 11 12 12 12 22 22 Таким образом, системы нелинейных уравнений (6.50), (6.52), (6.54) и (6.56) могут быть использованы для поиска линейного преобразования, осуществляющего приведение кривой, определенной над кольцом K уравнением (6.1), соответственно, к виду (6.49), (6.51), (6.53) или (6.55).

Линейное преобразование (6.28) является биекцией множества K 2 на себя тогда и только тогда, когда 2 2-матрица (6.29) обратима над коль цом K. Последнее имеет место тогда и только тогда, когда 11 22 12 21 K inv. (6.57) Теорема 6.6. Если характеристика кольца K равна 2, а a12 K inv, то никаким обратимым линейным преобразованием (6.28) квадратичная форма (6.34) не может быть приведена ни к виду (6.40), ни к виду (6.42).

Доказательство. Предположим, что характеристика кольца K равна 2, a12 K inv и существует обратимое линейное преобразование (6.28), приводящее квадратичную форму (6.34) к виду (6.40) или (6.42).

Тогда истинно равенство (6.47).

Так как a12 K inv, то равенство (6.47) эквивалентно равенству 11 22 + 12 21 = 0. (6.58) А так как 2 2-матрица (6.29) обратима над кольцом K, то истинно условие (6.57).

Из (6.57) и (6.58) вытекает, что 211 22 K inv 0 K inv.

Полученное противоречие показывает, что предположение – ложное.

Отсюда вытекает, что если характеристика кольца K равна 2, а a12 K inv, то никаким обратимым линейным преобразованием (6.28) квадратичная форма (6.34) не может быть приведена ни к виду (6.40), ни к виду (6.42).

6.1.2. Анализ кривых 3-го порядка.

Рассмотрим над кольцом K = (K, +, ·) кривую 3-го порядка, опре деленную уравнением ay 2 = b3 x3 + b2 x2 + b1 x + b0, (6.59) где a, b3 K\{0} и b2, b1, b0 K.

Для многочлена f (x) = b3 x3 + b2 x2 + b1 x + b0, являющегося правой частью уравнения (6.59), возможны следующие три ситуации.

Ситуация 6.4. Многочлен f (x) неразложим над кольцом K.

Ситуация 6.5. Для любых многочленов fi K[x] (i = 1, 2) степени mi 1 (i = 1, 2), удовлетворяющих равенству f (x) = f1 (x)f2 (x), истинно неравенство m1 + m2 3.

Ситуация 6.6. Существуют многочлены fi K[x] (i = 1, 2) степени mi 1 (i = 1, 2), удовлетворяющие равенству f (x) = f1 (x)f2 (x), для которых m1 + m2 = 3.

Пусть имеет место ситуация 6.5. Тогда f (x, y) – многочлен наимень шей степени, определяющий кривую 3-го порядка. Анализ кривой осуществляется непосредственно на основе уравнения (6.59).

Пусть имеет место ситуация 2.6. Тогда либо f (x) = (2 x2 + 1 x + 0 )(1 x + 0 ), где 2, 1, 0, 1, 0 K, причем 2 1 = 0, либо f (x) = (1 x + 1 )(2 x + 2 )(3 x + 3 ), где i, i K (i = 1, 2, 3), причем 1 2 3 = 0.

Следовательно, уравнение (6.59) принимает либо вид ay 2 = (2 x2 + 1 x + 0 )(1 x + 0 ), (6.60) либо вид ay 2 = (1 x + 1 )(2 x + 2 )(3 x + 3 ). (6.61) Положим Sa = {ay 2 |y K}, Sa = {(µ1, µ2 ) K 2 |µ1 µ2 Sa } (2) и Sa = {(1, 2, 3 ) K 3 |1 2 3 Sa }.

(3) Пусть кривая определена уравнением (6.60). Тогда множество ее точек представляет собой объединение множеств решений двух параметрического семейства систем нелинейных уравнений ay 2 = µ1 µ ((µ1, µ2 ) Sa ).

(2) Aµ1,µ2 : 2 x2 + 1 x + 0 = µ 1 x + 0 = µ Пусть кривая определена уравнением (6.61). Тогда множество ее точек представляет собой объединение множеств решений трех параметрического семейства систем нелинейных уравнений ay 2 = 1 2 x + = 1 1 ((1, 2, 3 ) Sa ).

(3) B1,2,3 :

2 x + 2 = x + = 3 3 Замечание 6.4. Таким образом, построение в явном виде множества точек кри вой 3-го порядка в ситуациях 6.4 и 6.5 эквивалентно поиску множества решений нелинейного уравнения (6.59) от двух переменных, а в ситуации 6.6 – поиску мно (2) жества решений двух-параметрического семейства Aµ1,µ2 ((µ1, µ2 ) Sa ) или трех (3) параметрического семейства B1,2,3 ((1, 2, 3 ) Sa ) систем нелинейных уравне ний.

При этом в ситуации 6.6 возникает необходимость построения в явном виде всех факторизаций всех элементов множества Sa либо на два, либо на три сомножителя.

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

Охарактеризуем особые точки кривой (6.59).

Из определения особой точки кривой вытекает, что множеством осо бых точек кривой (6.59) является множество решений системы уравне ний Dx (b3 x3 + b2 x2 + b1 x + b0 ay 2 ) = Dx (ay 2 b3 x3 b2 x2 b1 x b0 ) = ay = b3 x3 + b2 x2 + b1 x + b 3b3 x2 + 2b2 x + b1 = 2ay = 0.

ay = b3 x3 + b2 x2 + b1 x + b Отсюда вытекает, что истинно следующее утверждение.

Утверждение 6.3. Кривая, определенная уравнением (6.59), име ет особые точки тогда и только тогда, когда существует такое решение (x0, y0 ) системы уравнений { 3b3 x2 + 2b2 x + b1 =, (6.62) 2ay = что истинно равенство ay0 = b3 x3 + b2 x2 + b1 x0 + b0.

0 Пусть характеристика кольца K равна 2.

Тогда система уравнений (6.62) принимает вид { b3 x 2 + b 1 =. (6.63) yK Отсюда вытекает, что истинно следующее утверждение.

Утверждение 6.4. Пусть характеристика кольца K равна 2. Тогда:

1) кривая, определенная уравнением (6.59), является гладкой кри вой, если над кольцом K уравнение b3 x2 + b1 = 0 не имеет решений;

2) если b3 K inv, то множеством особых точек кривой, определен ной уравнением (6.59), является множество решений системы нелиней ных уравнений { { x2 = b1 b x = b3 b ay = b0 + b1 b2 b ay = b0 b1 b2 b 2 над кольцом K;

3) если b3 K\K inv, то множеством особых точек кривой, опреде ленной уравнением (6.59), является множество решений системы нели нейных уравнений { b3 x 2 + b 1 = ay 2 = b2 x2 + b над кольцом K.

Пусть характеристика кольца K равна 3.

Тогда система уравнений (6.62) принимает вид { { 2b2 x + b1 = 0 b2 x = b. (6.64) 2ay = 0 ay = Отсюда вытекает, что истинно следующее утверждение.

Утверждение 6.5. Пусть характеристика кольца K равна 3. Тогда:

1) кривая, определенная уравнением (6.59), является гладкой кри вой, если над кольцом K уравнение b3 x3 b1 x + b0 = 0 не имеет решений;

2) если b2 K inv и b3 b3 b3 b2 b1 + b0 = 0, то множеством особых 12 точек кривой, определенной уравнением (6.59), является множество точек {(b1 b1, y)|ay = 0};

3) если b2 K\K inv, то множеством особых точек кривой, опреде ленной уравнением (6.59), является множество решений системы нели нейных уравнений b2 x = b b x 3 b1 x + b 0 = ay = над кольцом K.

Найдем условия, при которых многочлен, являющийся правой частью уравнения (6.59), имеет кратный корень, т.е. когда b3 x3 + b2 x2 + b1 x + b0 = (x )2 (b3 x + ) (6.65) или b3 x3 + b2 x2 + b1 x + b0 = b3 (x )3. (6.66) Пусть характеристика кольца K равна 2. Тогда истинно следующее утверждение.


Утверждение 6.6. Если характеристика кольца K равна 2, то:

1) разложение (6.65) существует тогда и только тогда, когда суще ствует решение системы нелинейных уравнений { b3 2 = b b2 2 = b над кольцом K;

2) разложение (6.66) существует тогда и только тогда, когда суще ствует решение системы линейных уравнений b3 = b2 b3 = b2 b3 = b b 3 = b1 b2 = b 2 b = b 3 3 3 b3 = b0 b 3 = b0 b1 = b над кольцом K.

Пусть характеристика кольца K равна 3. Тогда истинно следующее утверждение.

Утверждение 6.7. Если характеристика кольца K равна 3, то:

1) разложение (6.65) существует тогда и только тогда, когда суще ствует решение (, ) системы нелинейных уравнений b3 + = b ;

b = b = b 2) разложение (6.66) существует тогда и только тогда, когда суще ствует решение нелинейного уравнения b3 3 = b0 и b2 = b1 = 0.

Замечание 6.5. Для кольца (в отличие от поля) равенство нулю результанта двух многочленов является необходимым условием существования их общего кор ня. Поэтому c использованием понятия «результант двух многочленов» может быть установлено только необходимое условие существования разложений (6.65) и (6.66).

Теорема 6.7. Если характеристика кольца K отлична от 2 и 3, то:

1) если существует разложение (6.65), то равенство b3 (4b0 b3 + 27b2 b2 18b0 b1 b2 b3 + 4b3 b3 b2 b2 ) = 0 (6.67) 2 03 1 истинно над кольцом K;

2) если существует разложение (6.66), то истинны равенства { b3 (4b0 b3 + 27b2 b2 18b0 b1 b2 b3 + 4b3 b3 b2 b2 ) = 2 03 1 (6.68) 12b3 (3b1 b3 b2 ) = над кольцом K.

Доказательство. Производная многочлена f (x), являющегося пра вой частью уравнения (6.59), равна Df (x) = 3b3 x2 + 2b2 x + b1.

Вычислим результант многочленов f (x) и Df (x).

b3 0 3b3 0 b2 b3 2b2 3b3 Res(f, Df, x) = det(Syl(f, Df, x)) = b1 b2 b1 2b2 3b3 = b0 b1 0 b1 2b 0 b0 0 0 b b3 2b2 3b3 0 b2 b3 3b3 b2 b1 2b2 3b3 b b2 2b2 3b + 3b3 = b3 = b1 0 b1 2b2 b0 b1 b1 2b b0 0 0 b1 0 b0 0 b 2b3 2b2 3b3 0 b2 2b3 3b3 b2 b1 2b2 3b3 b b2 2b2 3b + 3b3 = b3. (6.69) 0 0 b1 2b2 b0 0 b1 2b b0 0 0 b1 0 b0 0 b Вычислим по отдельности определители 4-го порядка.

2b3 2b2 3b3 2b3 2b2 3b 2b2 3b3 b2 b1 2b2 3b = b0 b1 2b2 3b3 + b1 b2 b1 2b2 = 0 0 b1 2b 0 b1 2b2 0 0 b b0 0 0 b = b0 (8b3 12b1 b2 b3 ) + b2 (2b1 b3 + 2b2 ) = 2 1 = 8b0 b3 + 12b0 b1 b2 b3 2b3 b3 + 2b2 b2, (6.70) 2 1 b2 2b3 3b3 b2 2b3 3b b2 3b3 b1 b2 2b2 3b = b0 b1 2b2 3b3 + b1 b1 b2 2b2 = b0 0 b1 2b b0 b1 2b2 b0 0 b 0 b0 0 b = b0 (4b3 + 9b0 b2 9b1 b2 b3 ) + b1 (b1 b2 b0 b2 b3 + 2b2 b3 ) = 2 3 2 = 4b0 b3 + 9b2 b2 10b0 b1 b2 b3 b2 b2 + 2b3 b3. (6.71) 2 03 12 Подставив (6.70) и (6.71) в (6.69), получим Res(f, Df, x) = b3 (8b0 b3 + 12b0 b1 b2 b3 2b3 b3 + 2b2 b2 )+ 2 1 +3b3 (4b0 b3 + 9b2 b2 10b0 b1 b2 b3 b2 b2 + 2b3 b3 ) = 2 03 12 = b3 (8b0 b3 + 12b0 b1 b2 b3 2b3 b3 + 2b2 b2 + 2 1 +12b0 b3 + 27b2 b2 30b0 b1 b2 b3 3b2 b2 + 6b3 b3 ) = 2 03 12 = b3 (4b0 b3 + 27b2 b2 18b0 b1 b2 b3 + 4b3 b3 b2 b2 ). (6.72) 2 03 1 Из (6.72) вытекает, что если существует разложение (6.65), то истинно равенство (6.67), что и требовалось показать.

Производная многочлена Df (x) равна D2 f (x) = 6b3 x + 2b2.

Вычислим результант многочленов Df (x) и D2 f (x).

Res(Df, D2 f, x) = det(Syl(Df, D2 f, x)) = 3b3 6b3 3b3 6b3 0 2b2 6b3 = 12b3 (3b1 b3 b2 ).

= 2b2 2b2 6b3 = (6.73) b1 0 2b2 b1 0 2b Из (6.72) и (6.73) вытекает, что если существует разложение (6.66), то истинны равенства (6.68), что и требовалось показать.

Замечание 6.6. Пусть характеристика кольца K равна 4. Из (6.73) вытекает, что Res(Df, D2 f, x) 0, т.е. необходимое условие существования разложения (6.66), устанавливаемое равенствами (6.68), тривиально для кольца характеристики 4.

Из (6.72) вытекает, что b3 disc(f ) = b3 (4b0 b3 + 27b2 b2 18b0 b1 b2 b3 + 4b3 b3 b2 b2 ). (6.74) 2 03 1 Из (6.74) непосредственно вытекает, что истинно утверждение.

Утверждение 6.8. Пусть либо b3 K inv, либо K – гауссово кольцо.

Тогда достаточное условие отсутствия разложения (6.65) для многочлена f (x) = b3 x3 + b2 x2 + b1 x + b0 состоит в том, что 4b0 b3 + 27b2 b2 18b0 b1 b2 b3 + 4b3 b3 b2 b2 = 2 03 1 над кольцом K.

6.2. Два типа многообразий над конечным кольцом.

Рассмотрим над кольцом K = (K, +, ·) Kf nt автомат Мили { qt+1 = f1 (qt, xt+1 ) (t Z+ ), yt+1 = f2 (qt, xt+1 ) где f1 : K n1 K n2 K n1 и f2 : K n1 K n2 K n3, или автомат Мура { qt+1 = f1 (qt, xt+1 ) (t Z+ ), yt+1 = f2 (qt+1 ) где f1 : K n1 K n2 K n1 и f2 : K n1 K n3 (элементы qt K n1, xt K n и yt K n3 являются, соответственно, состоянием, входным символом и выходным символом автомата в момент t).

Если при любом начальном состоянии q0, принадлежащем многооб разию V K n1, для любого входного слова x1... xi (K n2 )i (i N) все состояния qj также принадлежат этому многообразию, то естественно говорить, что автомат определен на многообразии V.

Само по себе определение многообразия над кольцом K формулой V = {(v1,..., vn ) K n |fi (v1,..., vn ) = 0 для всех i = 1,..., m}, где f1,..., fm K[1,..., n ] – попарно различные ненулевые многочле ны, мало что дает при исследовании свойств отображений, определенных на многообразии V (напомним, что даже над полем GF (2k ) (k N) по иск решений уравнения f (1,..., n ) = 0, где f – квадратичная форма, является NP-полной задачей).

Поэтому при исследования отображений, определенных на многооб разии, естественно ограничиться такими многообразиями V над кольцом K, которые представляют интерес как с теоретической, так и с приклад ной точки зрения, и свойства которых могут быть эффективно исполь зованы в процессе анализа автоматных моделей, определенных на этих многообразиях. Рассмотрим два основных типа таких многообразий над кольцом K = (K, +, ·) Kf nt.

6.2.1. Многообразия с алгеброй.

Рассмотрим вначале следующий пример.

Пример 6.1. Пусть – эллиптическая кривая над конечным полем K. Извест но, что множество точек G этой кривой (включая бесконечно удаленную точку O) является абелевой группой G = (G, +, · ).

Зафиксируем на множестве G множество унарных операций F1 = {0, 1,..., k1 } (k1 N), где 0 (P ) = O и i (P ) = P + · · · + P (i Nk1 ) i раз для всех P G.

Положим F2 = {+ }.

Таким образом, построена алгебра AG = (G, F1, F2 ), основой которой является множество G точек эллиптической кривой.

Рассмотренная в примере 6.1 конструкция допускает следующее есте ственное обобщение.

Пусть K = (K, +, ·) Kf nt.

Во множестве всех многообразий в K n (n N) выделим множество V1,n (K) всех таких многообразий V K n, что задана некоторая алгебра AV = (V, F1,V, F2,V ), где F1,V = {0, 1,..., k1 } (k1 Z+ ) и F2,V = {1,..., k2 } (k2 N) есть множество, соответственно, унарных и бинарных операций, опреде ленных на множестве V.

Замечание 6.7. Целесообразность выделения множества многообразий V1,n (K) (n N) над кольцом K Kf nt обосновывается, по крайней мере, тем, что эллиптиче ские кривые над конечными полями имеют многочисленные применения в процессе решения как теоретических, так и прикладных задач.

Пусть Vi V1,ni (Ki ) (i = 1, 2) (где n1, n2 N и K1, K2 Kf nt ) – такие многообразия, что для алгебр AVi = (Vi, F1,Vi, F2,Vi ) (i = 1, 2), где (i) (i) (i) (i) F1,Vi = {0, 1,..., } (k1 Z+ ) (i) k есть множество унарных операций алгебры AVi, а (i) (i) (i) F2,Vi = {1,..., } (k2 N) (i) k есть множество бинарных операций алгебры AVi, истинны равенства (1) (2) k1 = k1 = k и (1) (2) k2 = k2 = k2.

Предположим, что существует тройка отображений = 1, 2, 3 ), где 1 : V1 V2 – сюръекция, а 2 : F1,V1 F1,V2 и 3 : F2,V1 F2,V – биекции, для которой равенства 1 ((v1 )) = 2 ()(1 (v1 )) (6.75) и 1 ((v1, v2 )) = 3 ()(1 (v1 ), 1 (v2 )) (6.76) истинны для всех v1, v2 V1, F1,V1 и F2,V1.

Тогда будем говорить, что:

1) многообразие V2 – гомоморфный образ многообразия V1 ;

2) многообразия V1 и V2 изоморфны, если отображение 1 – биекция.

Иными словами:

1) многообразие V2 V1,n2 (K2 ) – гомоморфный образ многообразия V1 V1,n1 (K1 ) тогда и только тогда, когда алгебра AV2 = (V2, F1,V2, F2,V2 ) является гомоморфным образом алгебры AV1 = (V1, F1,V1, F2,V1 );

2) многообразия V1 V1,n1 (K1 ) и V2 V1,n2 (K2 ) изоморфны тогда и только тогда, когда изоморфны алгебры AV1 = (V1, F1,V1, F2,V1 ) и AV2 = (V2, F1,V2, F2,V2 ).

Замечание 6.8. Подчеркнем, что приведенное выше определение гомоморфизма (соответственно, изоморфизма) для многообразий с алгеброй представляет, по своей сути, определение гомоморфизма (соответственно, изоморфизма) для упорядочен ных пар (V1, AV1 ) (V1 V1,n1 (K1 )) и (V2, AV2 ) (V2 V1,n2 (K2 )).

Пример 6.2. Пусть 1 и 2 – эллиптические кривые, заданные над областью целостности K. Говорят, что:

1) эллиптическая кривая 2 является гомоморфным образом эллиптической кри вой 1, если абелева группа (K(2 ), +2 ) является гомоморфным образом абелевой группы (K(1 ), +1 );

2) эллиптические кривые 1 и 2 изоморфны, если абелевы группы (K(1 ), +1 ) и (K(2 ), +2 ) изоморфны.

Пусть 1 : K(1 ) K(2 ) – гомоморфизм эллиптической кривой 1 на эллипти ческую кривую 2.

Тогда для любого числа k1 {1,..., |K(2 )| 1} алгебра (2) (2) AK(2 ) = (K(2 ), F1, F2 ), где (2) (2) (2) (2) F1 = {0, 1,..., k1 } и (2) F2 = {+2 }, является гомоморфным образом алгебры (1) (1) AK(1 ) = (K(1 ), F1, F2 ), где (1) (1) (1) (1) F1 = {0, 1,..., k1 } и (1) F2 = {+1 }.

При этом для гомоморфизма = (1, 2, 3 ) (1) (2) (1) (2) алгебры AK(1 ) на алгебру AK(2 ) биекции 2 : F1 F1 и 3 : F2 F2 опреде ляются равенствами (1) (2) 2 (i ) = i (i Zk1 +1 ) и 3 (+1 ) = +2.

В частности, если 1 – биекция, то алгебры AK(1 ) и AK(2 ) изоморфны.

Таким образом, если эллиптическая кривая 2 – гомоморфный образ эллипти ческой кривой 1, то упорядоченная пара (K(2 ), AK(2 ) ) (K(2 ) V1,2 (K)) является гомоморфным образом упорядоченной пары (K(1 ), AK(1 ) ) (K(1 ) V1,2 (K)).


В частности, если эллиптические кривые 1 и 2 изоморфны, то упорядоченные пары (K(1 ), AK(1 ) ) (K(1 ) V1,2 (K)) и (K(2 ), AK(2 ) ) (K(2 ) V1,2 (K)) изоморфны.

6.2.2. Параметризованные многообразия.

Пусть K = (K, +, ·) Kf nt.

Во множестве всех многообразий в K n (n N) выделим множество V2,n (K) всех многообразий V K n, для которых существует парамет ризация v = h(t), где t K m (m n), а h = (h1,..., hn )T – набор многочленов от m переменных t1,..., tm над кольцом K.

Замечание 6.9. Целесообразность выделения множества многообразий V2,n (K) (n N) над кольцом K Kf nt обосновывается тем, что параметризованные мно гообразия над полями имеют многочисленные применения в процессе решения как теоретических, так и прикладных задач.

Параметризация v = h(t) (t K m ) дает возможность выделить на многообразии V V2,n (K) множество траекторий, т.е. последовательно стей точек.

Действительно (см. рис. 6.1), любое отображение f : K m K m опре деляет во множестве K m множество траекторий t, f (t), f 2 (t),... (t K m ), где f i = f · · · f (i N), i раз а «» является операцией суперпозиции.

V h h h h Km h h f ( 1 ) f 2 ( 1 ) f ( ) f 2 ( ) Рис. 6.1. Траектории в многообразии V V2,n (K).

Следовательно, для любого многообразия V V2,n (K) отображение f : K m K m и параметризация v = h(t) (t K m ) определяют на многообразии V множество траекторий h(t), h(f (t)), h(f 2 (t)),... (t K m ).

Пусть параметризация многообразия Vj V2,nj (Kj ) (j = 1, 2) (где n1, n2 N и Kj = (Kj, +j, ·j ) Kf nt (j = 1, 2)) имеет вид v = hj (t) (t Kj i ), m (j) (j) где hj = (h1,..., hnj )T (j = 1, 2) представляет собой набор многочленов (j) (j) от mj переменных t1,..., tmj над кольцом Kj Зафиксируем такие семейства отображений (j) (j) = {i }iNkj (j = 1, 2), mj mj (j) Kj для всех i Nkj, что истинно равенство где i : Kj k1 = k2 = k.

Предположим, что существует такая упорядоченная пара сюръекций = (1, 2 ), где 1 : V1 V2 и 2 : K1 1 K2 2, что равенства m m 1 (h1 (t)) = h2 (2 (t)) (6.77) и (1) (2) 2 (i (t)) = i (2 (t)) (6.78) истинны для всех t K1 1 и i Nk.

m Тогда будем говорить, что:

1) упорядоченная пара (V2, (2) ) – гомоморфный образ упорядочен ной пары (V1, (1) );

2) упорядоченные пары (V1, (1) ) и (V2, (2) ) изоморфны, если отоб ражения 1 и 2 – биекции.

Пример 6.3. Любая алгебраическая кривая v2 = a0 v1 + a1 v1 + · · · + an n n над кольцом K = (K, +, ·) Kf nt может рассматриваться как полиномиально пара метризованное многообразие { v1 = ( K) v2 = a0 n + a1 n1 + · · · + an в K 2, т.е. как элемент множества V2,2 (K).

Алгебраические кривые v2 = a0 v1 1 + a1 v1 1 1 + · · · + an n n и u2 = b0 un2 + b1 un2 1 + · · · + bn 1 над кольцом K определяют в K 2 многообразия V1 = {(1, a0 1 1 + a1 1 1 1 + · · · + an1 ) | 1 K} n n и V2 = {(2, b0 2 2 + b1 2 2 1 + · · · + bn2 ) | 2 K}.

n n Зафиксируем элементы c, c1,..., ck K inv.

Определим семейство = {i }iZk отображений i : K K следующим образом i ( ) = ci (i Zk, K), а пару биекций = (1, 2 ) (1 : V1 V2, 2 : K K) определим равенствами 1 ((, a0 n1 + a1 n1 1 + · · · + an1 )) = = (c, b0 cn2 n2 + b1 cn2 1 n2 1 + · · · + bn2 ) ( K), 2 ( ) = c ( K).

Так как для биекций = (1, 2 ) истинны равенства (6.77) и (6.78), то упорядо ченные пары (V1, ) и (V2, ) изоморфны.

6.3. Автоматы на многообразии с алгеброй.

Определим автоматы Мили и Мура на многообразии V V1,n (K), где K = (K, +, ·) Kf nt и n N, и исследуем свойства таких автоматов.

6.3.1. Исследуемые модели.

Для каждого многообразия V V1,n (K) может быть задана некоторая алгебра AV = (V, F1,V, F2,V ), где F1,V = {0, 1,..., k1 } (k1 Z+ ) и F2,V = {1,..., k2 } (k2 N) есть множество, соответственно, унарных и бинарных операций, опреде ленных на множестве V. Таким образом, может быть задана упорядо ченная пара (V, AV ).

Системы рекуррентных соотношений { qt+1 = j1 (i1 (qt ), xt+1 (v1 )) (t Z+ ) (6.79) yt+1 = j2 (i2 (qt ), xt+1 (v2 )) { и qt+1 = j1 (i1 (qt ), xt+1 (v1 )) (t Z+ ), (6.80) yt+1 = j2 (i2 (qt+1 ), v2 ) где v1, v2 V – фиксированные точки, i1, i2 Zk1 +1 и j1, j2 Nk2 – фиксированные числа, а q0 V и xt+1 Zk1 +1 (t Z+ ), определяют, соответственно, семейство автоматов Мили M(1) (V, AV ) и семейство ав томатов Мура M(2) (V, AV ).

Для каждого автомата M M(1) (V, AV ) M(2) (V, AV ) элементы xt, qt и yt являются, соответственно, входным символом, состоянием и выходным символом в момент t.

Поэтому, для каждого автомата M M(1) (V, AV )M(2) (V, AV ) мно жество чисел Zk1 +1 является входным алфавитом, а многообразие V – как множеством состояний, так и выходным алфавитом.

Пример 6.4. Пусть – эллиптическая кривая, заданная над областью целостно сти K.

Тогда для любого числа k1 {1,..., |K()| 1} может быть задана алгебра AK() = (K(), F1, F2 ), где F1 = {0, 1,..., k1 } и F2 = {+ } являются множествами, соответственно, унар ных и бинарных операций, определенных на множестве K().

Из (6.79) и (6.80) вытекает, что упорядоченная пара (K(), AK() ) дает возмож ность определить системами рекуррентных соотношений { qt+1 = i1 (qt ) + xt+1 (P1 ) (t Z+ ) (6.81) yt+1 = i2 (qt ) + xt+1 (P2 ) { и qt+1 = i1 (qt ) + xt+1 (P1 ) (t Z+ ), (6.82) yt+1 = i2 (qt+1 ) + P соответственно, семейство автоматов Мили M(1) (K(), AK() ) и семейство автоматов Мура M(2) (K(), AK() ), где i1, i2 Zk1 +1 – фиксированные числа, P1, P2 K() – фиксированные точки, q0 K() и xt+1 Zk1 +1 (t Z+ ).

6.3.2. Автоматные характеристики исследуемых моделей.

Пусть на многообразии V V1,n (K) (n N) задана алгебра AV = (V, F1,V, F2,V ), где F1,V = {0, 1,..., k1 } (k1 Z+ ) и F2,V = {1,..., k2 } (k2 N) есть множество, соответственно, унарных и бинарных операций, опреде ленных на множестве V.

Из (6.79) и (6.80) вытекает, что истинны равенства |M(1) (V, AV )| = |M(2) (V, AV )| = (k1 + 1)2 k2 |V|.

Положим V alv F1,V = {r (v) | r Nk1 } (v V). (6.83) Охарактеризуем свойства автомата M M(1) (V, AV ) M(2) (V, AV ), которые формулируются только в терминах функции переходов автома та, т.е. в терминах рекуррентного соотношения qt+1 = j1 (i1 (qt ), xt+1 (v1 )).

Напомним, что автомат называется групповым, если для каждого фиксированного входного символа функция переходов является подста новкой на множестве состояний.

Утверждение 6.9. Для многообразия V V1,n (K) (n N) и алгебры AV = (V, F1,V, F2,V ) семейство всех групповых автоматов M M(1) (V, AV ) M(2) (V, AV ) определяется множеством всех та ких упорядоченных пар (i1, j1 ) F1,V F2,V, что V al i1 = V и V al j1 |V{v} = V для каждого v V alv1 F1,V.

Доказательство. Для каждых фиксированных v1 V и x Zk1 + формула j1 (i1 (q), x (v1 )) = j1 (i1 (q), x (v1 )) истинна для всех состояний q, q V (q = q) тогда и только тогда, когда V al i1 = V и V al j1 |V{x (v1 )} = V.

Следовательно, автомат M M(1) (V, AV ) M(2) (V, AV ) являет ся групповым автоматом тогда и только тогда, когда V al i1 = V и V al j1 |V{x (v1 )} = V.

Отсюда и из формулы (6.83) вытекает, что утверждение истинно.

Состояние q V автомата M M(1) (V, AV ) M(2) (V, AV ) называ ется:

1) источником, если из любого состояния q V автомата M невозмо жен переход в состояние q;

2) стоком, если из состояния q невозможно перейти ни в какое другое состояние автомата M.

Утверждение 6.10. Для автомата M M(1) (V, AV ) M(2) (V, AV ) множество Vист = V\V al (j1 |V al i1 V alv1 F1,V ) (6.84) является множеством состояний-источников.

Доказательство. Для любых фиксированных элементов q, v1 V уравнение q = j1 (i1 (q), x (v1 )) (6.85) имеет решение относительно переменных q V и x Zk1 +1 тогда и только тогда, когда q V al (j1 |{(i1 (q),x (v1 ))} ).

qV,xZk1 + При этом V al (j1 |{(i1 (q),x (v1 ))} ) = qV,xZk1 + ( ) V al (j1 |{(i1 (q),x (v1 ))} ) = = xZk1 + qV ( ) V al (j1 |{i1 (q)}V alv1 F1,V ) = V al (j1 |V al i1 V alv1 F1,V ).

= qV Таким образом, для любых фиксированных элементов q, v1 V урав нение (6.85) имеет решение относительно переменных q V и x Zk1 + тогда и только тогда, когда q V al (j1 |V al i1 V alv1 F1,V ). Отсюда и из определения состояния-источника вытекает равенство (6.84).

Утверждение 6.11. Для автомата M M(1) (V, AV ) M(2) (V, AV ) множество Vст = {q V | {q} = V al (j1 |V al i1 V alv1 F1,V )} (6.86) является множеством состояний-стоков.

Доказательство. Для любых фиксированных элементов q, v1 V уравнение q = j1 (i1 (q), x (v1 )) (6.87) не имеет решения относительно переменных q V\{q} и x Zk1 +1 тогда и только тогда, когда V al (j1 |{(i1 (q),x (v1 ))} ) = {q}.

xZk1 + При этом V al (j1 |{(i1 (q),x (v1 ))} ) = V al (j1 |{i1 (q)}V alv1 F1,V ).

xZk1 + Следовательно, для любых фиксированных элементов q, v1 V урав нение (6.87) не имеет решения относительно переменных q V\{q} и x Zk1 +1 тогда и только тогда, когда V al (j1 |{i1 (q)}V alv1 F1,V ) = q. От сюда и из определения состояния-стока вытекает равенство (6.86).

Охарактеризуем свойства автомата M M(1) (V, AV ) M(2) (V, AV ), при формулировке которых существенно используется функция выходов автомата.

Для автомата M M(1) (V, AV ) M(2) (V, AV ) определим на много образии V V1,n (K) (n N) такие отношения эквивалентности 1 (v) (v V alv1 F1,V ), 2 (v) (v V alv2 F1,V ) и 3 (v) (v V alv1 F1,V ), что:

(q, q) 1 (v) j1 (i1 (q), v) = j1 (i1 (q), v), (6.88) (q, q) 2 (v) j2 (i2 (q), v) = j2 (i2 (q), v) (6.89) и (q, q) 3 (v) j2 (i2 (j1 (i1 (q), v)), v2 ) = j2 (i2 (j1 (i1 (q), v)), v2 ). (6.90) Положим 1 = 1 (v), (6.91) vV alv1 F1,V 2 = 2 (v) (6.92) vV alv2 F1,V и 3 = 3 (v). (6.93) vV alv1 F1,V Напомним, что два различных состояния автомата называются близ нецами, если каждый входной символ переводит их в одно и то же со стояние, и при этом автомат выдает одинаковые выходные символы.

Из (6.88), (6.89), (6.91) и (6.92) непосредственно вытекает, что истинно следующее утверждение.

Утверждение 6.12. Для автомата M M(1) (V, AV ) состояния q, q V (q = q) являются близнецами тогда и только тогда, когда (q, q) 1 2.

Аналогичным образом, из (6.88), (6.90), (6.91) и (6.93) непосредствен но вытекает, что истинно следующее утверждение.

Утверждение 6.13. Для автомата M M(2) (V, AV ) состояния q, q V (q = q) являются близнецами тогда и только тогда, когда (q, q) 1 3.

Замечание 6.10. Из утверждений 6.12 и 6.13 вытекает, что:

1) максимальными множествами состояний-близнецов автомата M M(1) (V, AV ) являются такие элементы S фактор-множества V/1 2, что |S| 2;

2) максимальными множествами состояний-близнецов автомата M M(2) (V, AV ) являются такие элементы S фактор-множества V/1 3, что |S| 2.

Автомат называется явно приведенным (говорят также, что автомат является 1-диагностируемым), если для любых двух его различных со стояний существует входной символ, который различает эти состояния.

Из (6.89) и (6.92) непосредственно вытекает, что истинно следующее утверждение.

Утверждение 6.14. Автомат M M(1) (V, AV ) является явно при веденным тогда и только тогда, когда отношение эквивалентности является отношением равенства на множестве V.

Аналогичным образом, из (6.90) и (6.93) непосредственно вытекает, что истинно следующее утверждение.

Утверждение 6.15. Автомат M M(2) (V, AV ) является явно при веденным тогда и только тогда, когда отношение эквивалентности является отношением равенства на множестве V.

6.3.3. Гомоморфизмы исследуемых моделей.

Напомним, что понятие «гомоморфизм» для абстрактных автоматов определяется следующим образом.

Гомоморфным образом автомата M = (Q, X, Y,, ) называется такой автомат M = (Q, X, Y,, ), что существует такая тройка сюръекций (1, 2, 3 ) (где 1 : Q Q, 2 : X X и 3 : Q Y ), что равенства 1 ((q, x)) = (1 (q), 2 (x)) и 3 ((q, x)) = (1 (q), 2 (x)) истинны для всех q Q и x X. В частности, если 1, 2, 3 – биекции, то автоматы M и M называются изоморфными.

Гомоморфизм упорядоченной пары (V1, AV1 ) (V1 V1,n1 (K1 )) на упо рядоченную пару (V2, AV2 ) (V2 V1,n2 (K2 )), где AVr = (Vr, F1,Vr, F2,Vr ) (r = 1, 2) – алгебра, а (r) (r) (r) F1,Vr = {0, 1,..., k1 } и (r) (r) F2,Vr = {1,..., k2 } есть множество, соответственно, унарных и бинарных операций, опреде лен в п.6.2.1 как тройка отображений = (1, 2, 3 ) где 1 : V1 V2 – сюръекция, а 2 : F1,V1 F1,V2 и 3 : F2,V1 F2,V – биекции, удовлетворяющих равенствам (6.75) и (6.76).

Следующая теорема устанавливает, каким образом связаны между собой гомоморфизм = (1, 2, 3 ) упорядоченной пары (V1, AV1 ) на упорядоченную пару (V2, AV2 ) и го моморфные образы автоматов Mr M(r) (V1, AV1 ) (r = 1, 2), которые принадлежат семейству автоматов M(r) (V2, AV2 ).

Теорема 6.8. Если упорядоченная пара (V2, AV2 ) (V2 V1,n2 (K2 )) – гомоморфный образ упорядоченной пары (V1, AV1 ) (V1 V1,n1 (K1 )), то существуют такие отображения r : M(r) (V1, AV1 ) M(r) (V2, AV2 ) (r = 1, 2), (6.94) что автомат r (Mr ) (Mr M(r) (V1, AV1 )) – гомоморфный образ авто мата Mr.

Доказательство. Предположим, что упорядоченная пара (V2, AV2 ) (V2 V1,n2 (K2 )) – гомоморфный образ упорядоченной пары (V1, AV1 ) (V1 V1,n1 (K1 )), а тройка отображений = (1, 2, 3 ), (1) (2) (1) (2) где 1 : V1 V2, 2 : F1 F1 и 3 : F2 F2, определя ет гомоморфизм упорядоченной пары (V1, AV1 ) на упорядоченную пару (V2, AV2 ).

Рассмотрим такие отображения (6.94), что:

1) для автомата M1 M(1) (V1, AV1 ), заданного системой рекуррент ных соотношений { (1) (1) (1) (1) (1) (1) qt+1 = j1 (i1 (qt ), xt+1 (v1 )) (t Z+ ), (6.95) (1) (1) (1) (1) (1) (1) yt+1 = j2 (i2 (qt ), xt+1 (v2 )) автомат 1 (M1 ) M(1) (V2, AV2 ) задан системой рекуррентных соотно шений { (2) (1) (1) (2) (1) (2) qt+1 = 3 (j1 )(2 (i1 )(qt ), 2 (xt+1 )(v1 )) (t Z+ );

(6.96) (2) (1) (1) (2) (1) (2) yt+1 = 3 (j2 )(2 (i2 )(qt ), 2 (xt+1 )(v2 )) 2) для автомата M2 M(2) (V1, AV1 ), заданного системой рекуррент ных соотношений { (1) (1) (1) (1) (1) (1) qt+1 = j1 (i1 (qt ), xt+1 (v1 )) (t Z+ ), (6.97) (1) (1) (1) (1) (1) yt+1 = j2 (i2 (qt+1 ), v2 ) автомат 2 (M2 ) M(2) (V2, AV2 ) задан системой рекуррентных соотно шений { (2) (1) (1) (2) (1) (2) qt+1 = 3 (j1 )(2 (i1 )(qt ), 2 (xt+1 )(v1 )) (t Z+ ). (6.98) (2) (1) (1) (2) (2) yt+1 = 3 (j2 )(2 (i2 )(qt+1 ), v2 )) Из (6.95)-(6.98) вытекает, что для всех t Z+ истинны равенства (1) (1) (1) (1) (1) 1 (j1 (i1 (qt ), xt+1 (v1 ))) = (1) (1) (1) (1) (1) = 3 (j1 )(2 (i1 )(1 (qt )), 2 (xt+1 )(1 (v1 ))), (6.99) (1) (1) (1) (1) (1) 1 (j2 (i2 (qt ), xt+1 (v2 ))) = (1) (1) (1) (1) (1) = 3 (j2 )(2 (i2 )(1 (qt )), 2 (xt+1 )(1 (v2 ))) (6.100) и (1) (1) (1) (1) (1) (1) (1) (1) 1 (j2 (i2 (qt+1 ), v2 )) = 3 (j2 )(2 (i2 )(1 (qt+1 )), 1 (v2 )). (6.101) Из (6.99) и (6.100) вытекает, что автомат 1 (M1 ) M(1) (V2, AV2 ) – гомоморфный образ автомата M1 M(1) (V1, AV1 ), а из (6.99) и (6.101) вытекает, что автомат 2 (M2 ) M(2) (V2, AV2 ) – гомоморфный образ автомата M2 M(2) (V1, AV1 ).

Замечание 6.11. Из равенств (6.99)-(6.101) вытекает, что для тройки сюръекций (1, 2, 3 ), определяющей гомоморфизм автомата Mr M(r) (V1, AV1 ) (r = 1, 2) на автомат r (Mr ) M(r) (V2, AV2 ) истинно равенство 1 = 3 = 1, а значения 2 (i) Zk1 +1 (i Zk1 +1 ) определяются равенствами (2) (1) (1) (1) 2 (i) (1 (v1 )) = i (v1 ).

Из теоремы 6.8 непосредственно вытекает, что истинно следующее следствие.

Следствие 6.5. Если упорядоченные пары (V1, AV1 ) (V1 V1,n1 (K1 )) и (V2, AV2 ) (V2 V1,n2 (K2 )) изоморфны, то существуют такие отобра жения r : M(r) (V1, AV1 ) M(r) (V2, AV2 ) (r = 1, 2), что автоматы Mr M(r) (V1, AV1 ) и r (Mr ) изоморфны.

Пример 6.5. Пусть 1 и 2 – такие эллиптические кривые, заданные над областью целостности K, что упорядоченная пара (K(2 ), AK(2 ) ) изоморфна упорядоченной па (r) (r) (r) (r) (r) (r) ре (K(1 ), AK(1 ) ), где AK(r ) = (K(r ), F1, F2 ) (r = 1, 2), а F1 = {0, 1,..., k1 } (r) и F2 = {+r } являются множествами, соответственно, унарных и бинарных опера ций, определенных на множестве K(r ).

Из теоремы 6.8 вытекает, что существуют такие отображения r : M(r) (K(1 ), AK(1 ) ) M(r) (K(2 ), AK(2 ) ) (r = 1, 2) что автомат r (Mr ) (Mr M(r) (K(1 ), AK(1 ) ) – гомоморфный образ автомата Mr.

При этом, из доказательства теоремы 6.8 вытекает, что:

1) для автомата M1 M(1) (K(1 ), AK(1 ) ), заданного системой рекуррентных со { отношений (1) (1) (1) (1) (1) qt+1 = i1 (qt ) +1 xt+1 (P1 ) (t Z+ ), (1) (1) (1) (1) (1) yt+1 = i2 (qt ) +1 xt+1 (P2 ) автомат 1 (M1 ) M(1) (K(2 ), AK(2 ) ) задан системой рекуррентных соотношений { (2) (2) (2) (2) (2) qt+1 = i1 (qt ) +2 xt+1 (P1 ) (t Z+ );

(2) (2) (2) (2) (2) yt+1 = i2 (qt ) +2 xt+1 (P2 ) 2) для автомата M2 M(2) (K(1 ), AK(1 ) ), заданного системой рекуррентных со { отношений (1) (1) (1) (1) (1) qt+1 = i1 (qt ) +1 xt+1 (P1 ) (t Z+ ), (1) (1) (1) (1) yt+1 = i2 (qt+1 ) +1 P автомат 2 (M2 ) M(2) (K(2 ), AK(2 ) ) задан системой рекуррентных соотношений { (2) (2) (2) (2) (2) qt+1 = i1 (qt ) +2 xt+1 (P1 ) (t Z+ ).

(2) (2) (2) (2) yt+1 = i2 (qt+1 ) +2 P 6.4. Автоматы на параметризованных многообразиях.

Определим автоматы Мили и Мура на многообразии V V2,n (K), где K = (K, +, ·) Kf nt и n N, и исследуем свойства таких автоматов.

6.4.1. Исследуемые модели.

Пусть V V2,n (K) и v = h(t) (t K m ) – параметризация много образия V (где h = (h1,..., hn )T – набор многочленов от m (m n) переменных t1,..., tm над кольцом K). Зафиксировав семейство отобра жений = {i }iNk (где i : K m K m для всех i Nk ), мы определяем упорядоченную пару (V, ).

Упорядоченная пара (V, ) дает возможность для любого числа l N (1) определить семейство автоматов Мили Mn,k,l (V, ) и семейство автома (2) тов Мура Mn,k,l (V, ), соответственно, системой рекуррентных соотно { шений qt+1 = h(xt+1 (tt )) (t N) (6.102) yt+1 = gxt+1 (qt ) и системой рекуррентных соотношений { qt+1 = h(xt+1 (tt )) (t N), (6.103) yt+1 = g(qt+1 ) где t0 K m, q0 = h(t0 ), tt+1 = xt+1 (tt ) (t Z+ ), gi : K n K l (i Nk ), g : K n K l (i Nk ) и xt+1 Nk (t Z+ ).

(1) (2) Для каждого автомата M Mn,k,l (V, ) Mn,k,l (V, ) элементы xt, qt и yt являются, соответственно, входным символом, состоянием и выходным символом в момент t.

(1) (2) Поэтому, для каждого автомата M Mn,k,l (V, ) Mn,k,l (V, ) мно жество чисел Nk является входным алфавитом, а многообразие V – мно жеством состояний.

(1) Выходным алфавитом автомата M Mn,k,l (V, ) является множе (2) V al (gi |V ), а выходным алфавитом автомата M Mn,k,l (V, ) ство iZk – множество V al (g|V ).

Положим (r) (r) Mn,k (V, ) Mn,k,l (V, ) (r = 1, 2).

= l= Обозначим через Fm (K) множество всех отображений f : K m K m.

(1) При определении семейства автоматов Мили Mn,k,l (V, ) и семейства (2) автоматов Мура Mn,k,l (V, ) не было наложено никаких ограничений на отображения, принадлежащие семейству = {i }iNk, т.е. элементами семейства могут быть любые элементы множества Fm (K).

Такая общность естественно приводит к широкому классу семейств автоматов, определяемых формулами (6.102) и (6.103).

Охарактеризуем этот класс семейств автоматов.

Как было отмечено в п.6.2.2, каждое отображение f Fm определяет на многообразии V множество TV,f траекторий h(t0 ), h(t1 ),..., h(tj ),... (t0 K m ), (6.104) где tj+1 = f (tj ) для всех j Z+. Будем говорить, что траектория (6.104) исходит из точки h(P0 ) многообразия V.

Имеет место следующая теорема.

Теорема 6.9. Пусть v = h(t) (t K m ) – параметризация многообра зия V V2,n (K), а f Fm (K). Любые две различные траектории, при надлежащие множеству TV,f, исходят из различных точек многообразия (1) (2) V тогда и только тогда, когда не существуют такие точки t0, t0 K m, (1) (2) (1) (2) что t0 t0 (ker h) и t0 t0 (ker(h f )).



Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.