Исследование структуры множества линейных БПИ-автоматов над кольцом Zpk
For linear information-lossless automata over the ring Zp , we have established conditions and estimated cardinalities for sets of automata characterized via basic characteristics of automata theory (the transition graph is complete with a loop at each vertex, permutation and reduced automata, au...
Збережено в:
| Дата: | 2007 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2007
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/3161 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Исследование структуры множества линейных БПИ-автоматов над кольцом Zpk / В.В. Скобелев // Доп. НАН України. — 2007. — № 10. — С. 44-49. — Бібліогр.: 11 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859764062776197120 |
|---|---|
| author | Скобелев, В.В. |
| author_facet | Скобелев, В.В. |
| citation_txt | Исследование структуры множества линейных БПИ-автоматов над кольцом Zpk / В.В. Скобелев // Доп. НАН України. — 2007. — № 10. — С. 44-49. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| description | For linear information-lossless automata over the ring Zp , we have established conditions and
estimated cardinalities for sets of automata characterized via basic characteristics of automata
theory (the transition graph is complete with a loop at each vertex, permutation and reduced
automata, automata with twin states). For the investigated automata, a criterion of equivalence
is established, the problem of parametric identification is resolved, and the canonical presentati-
ons, in which all linear transformation are reduced to component-wise multiplication in the ring
and to the application of reversible matrices, are designed.
|
| first_indexed | 2025-12-02T04:37:22Z |
| format | Article |
| fulltext |
УДК 510.5+681.3
© 2007
В.В. Скобелев
Исследование структуры множества линейных
БПИ-автоматов над кольцом Zpk
(Представлено членом-корреспондентом НАН Украины А.А. Летичевским)
For linear information-lossless automata over the ring Zpk , we have established conditions and
estimated cardinalities for sets of automata characterized via basic characteristics of automata
theory (the transition graph is complete with a loop at each vertex, permutation and reduced
automata, automata with twin states). For the investigated automata, a criterion of equivalence
is established, the problem of parametric identification is resolved, and the canonical presentati-
ons, in which all linear transformation are reduced to component-wise multiplication in the ring
and to the application of reversible matrices, are designed.
1. Естественным обобщением линейных автоматов над конечным полем [1] являются ли-
нейные автоматы над конечным кольцом. Наличие в кольце делителей нуля и необратимых
элементов требует тщательной проработки методов анализа и синтеза таких автоматов, так
как происходит переход от структуры векторного пространства над конечным полем [2, 3]
к модулю линейных форм над конечным кольцом [4]. Известно [5], что БПИ-автомат при
каждом фиксированном начальном состоянии осуществляет взаимно-однозначное преобра-
зование входной полугруппы в выходную. Поэтому БПИ-автоматы над конечным кольцом
имеют нетривиальную область приложений, а именно: преобразование информации, в том
числе и разработка методов защиты информации. Сказанное подтверждается тем, что мо-
дели и методы теории конечных полей присутствуют, практически, во всех современных
стандартах шифрования [6, 7].
Зафиксируем кольцо Zpk = (Zpk ,⊕, ◦) (p — простое число, k ∈ N), где операции ⊕ и ◦
определены равенствами a ⊕ b = a + b(mod pk) и a ◦ b = a · b(mod pk). В соответствии с [8]
в качестве исследуемых моделей выберем инициальный автомат Мили
(M1,q0) :
{
qt+1 = A ◦ qt ⊕ B ◦ xt+1
yt+1 = C ◦ qt ⊕ D ◦ xt+1
(t ∈ Z+) (1)
и инициальный автомат Мура
(M2,q0) :
{
qt+1 = A ◦ qt ⊕ B ◦ xt+1
yt+1 = C ◦ qt+1
(t ∈ Z+), (2)
где A, B, C и D — (n×n)-матрицы над кольцом Zpk , а qt, xt, yt ∈ Zn
pk — векторы-столбцы,
представляющие, соответственно, состояние, входной и выходной символы в момент t.
Обозначим через An,1 множество всех автоматов M1, определяемых формулой (1), а че-
рез An,2 — множество всех автоматов M2, определяемых формулой (2).
Для того чтобы автоматы (1) и (2) были БПИ-автоматами (т. е. были обратимыми ав-
томатами), необходимо и достаточно, чтобы для автомата (1) была обратимой матрица D,
а для автомата (2) — матрицы B и C. При этом обратные автоматы имеют вид
(M−1
1 ,q0) :
{
qt+1 = A1 ◦ qt ⊕ B1 ◦ xt+1
yt+1 = C1 ◦ qt ⊕ D1 ◦ xt+1
(t ∈ Z+),
44 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2007, №10
где A1 = A⊖B◦D−1◦C (⊖ — операция, обратная операции ⊕), B1 = B◦D−1, C1 = ⊖D−1◦C,
D1 = D−1 и
(M−1
2 ,q0) :
{
qt+1 = B1 ◦ xt+1
yt+1 = C1 ◦ qt ⊕ D1 ◦ xt+1
(t ∈ Z+)
(B1 = C−1, C1 = ⊖A, D1 = B−1 ◦ C−1). Обозначим через Ainv
n,i (i = 1, 2) множество всех
обратимых автоматов Mi ∈ An,i.
2. Исследуем конечно-автоматные характеристики автоматов M ∈ Ainv
n,i (i = 1, 2).
Пусть Mn и M
inv
n — множество, соответственно, всех и всех обратимых (n × n)-матриц
над кольцом Zpk . Ясно, что |Mn| = pk·n2
. Так как a ∈ Zpk — обратимый элемент кольца Zpk
тогда и только тогда, когда a 6= 0 (mod p), то число обратимых и необратимых элементов
кольца Zpk равно, соответственно, (p − 1) · pk−1 и pk−1. Из этих оценок вытекает
Теорема 1. Для любого простого числа p при всех k, n ∈ N
n! · (p − 1)n · p−n2
· |Mn| 6 |Minv
n | 6 (1 − p−n)n · |Mn|. (3)
Следствие 1. Для любого простого числа p при всех k, n ∈ N
(1 − (1 − p−n)n) · |Mn| 6 |Mn \ M
inv
n | 6 (1 − n! · (p − 1)n · p−n2
) · |Mn|. (4)
Так как |An,i| = |Mn|
5−i (i = 1, 2), |Ainv
n,1 | = |Mn|
3 · |Minv
n | и |Ainv
n,2 | = |Mn| · |M
inv
n |2, то из
теоремы 1 вытекает
Теорема 2. Для любого простого числа p при всех k, n ∈ N
(n! · (p − 1)n · p−n2
)i · |An,i| 6 |Ainv
n,i | 6 (1 − p−n)n·i · |An,i| (i = 1, 2). (5)
Обозначим через D
(1)
n и D
(2)
n — множество диагональных (n×n)-матриц, на главной диа-
гонали которых расположены, соответственно, обратимые и необратимые элементы кольца
Zpk . Тогда D
(1)
n ⊆ M
inv
n и D
(2)
n ⊆ Mn \ M
inv
n , причем для любого простого числа p при всех
k, n ∈ N истинны равенства
|D(1)
n | = (p − 1)n · p(k−1)·n, (6)
|D(2)
n | = p(k−1)·n. (7)
Пусть Binv
n,1 — множество всех таких автоматов M1 ∈ Ainv
n,1 , что D ∈ D
(1)
n , а Binv
n,2 —
множество всех таких автоматов M2 ∈ Ainv
n,2 , что B, C ∈ D
(1)
n . Из (6) вытекает, что для
любого простого числа p при всех k, n ∈ N
|Binv
n,i | = ((p − 1)n · p(k−1−k·n)·n)i · |An,i| (i = 1, 2). (8)
Обозначим через Gn,i (i = 1, 2) множество всех автоматов M ∈ An,i, у которых граф
переходов — полный граф с петлями, и Ginv
n,i = Gn,i
⋂
Ainv
n,i (i = 1, 2). Из (1) и (2) вытекает, что
если для автомата M ∈ An,i (i = 1, 2) матрица B обратимая, то M ∈ Gn,i. Следовательно,
для любого простого числа p при всех k, n ∈ N истинны равенство Ginv
n,2 = Ainv
n,2 и неравенства
((n!) · (p − 1)n · p−n2
)2 · |An,1| 6 |Ginv
n,1 | 6 (1 − p−n)2·n · |An,1|. (9)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2007, №10 45
Пусть Cinv
n,i (i = 1, 2) — множество всех перестановочных автоматов M ∈ Ainv
n,i . Из (1)
и (2) вытекает, что если для автомата M ∈ An,i (i = 1, 2) матрица A обратимая, то M —
перестановочный автомат, т. е. для любого простого числа p при всех k, n ∈ N
|Cinv
n,i | > (n! · (p − 1)n · p−n2
)i+1 · |An,i| (i = 1, 2). (10)
Обозначим через Dinv
n,i (i = 1, 2) множество всех приведенных автоматов M ∈ Ainv
n,i .
Из (1) и (2) вытекает, что:
1) если для автомата M ∈ An,1 матрица C обратимая, то M — приведенный автомат,
степень различимости [9] которого равна 1;
2) если для автомата M ∈ An,2 матрицы A и C обратимые, то M — приведенный автомат,
степень различимости которого равна 1. Следовательно, для любого простого числа p при
всех k, n ∈ N
|Dinv
n,i | > (n! · (p − 1)n · p−n2
)i+1 · |An,i| (i = 1, 2). (11)
Пусть E inv
n,i (i = 1, 2) — множество всех автоматов M ∈ Ainv
n,i , имеющих состояния-бли-
знецы. Из (1) и (2) вытекает, что:
1) если для автомата M ∈ An,1 матрицы A и C необратимые и система уравнений
{
A ◦ u = 0,
C ◦ u = 0
имеет ненулевое решение, то в автомате M существуют состояния-близнецы;
2) если для автомата M ∈ An,2 матрица A необратимая, то в автомате M существуют
состояния-близнецы. Следовательно, для любого простого числа p при всех k, n ∈ N
|E inv
n,1 | > n! · (p − 1)n · p−n2
· (1 − (1 − p−n)n)2 · |An,1|, (12)
|E inv
n,2 | > (1 − (1 − p−n)n) · (n! · (p − 1)n · p−n2
)2 · |An,2|. (13)
Обозначим через F inv
n,1 множество всех таких автоматов M ∈ E inv
n,1 , что A, C ∈ D
(2)
n ,
а F inv
n,2 — множество всех таких автоматов M ∈ E inv
n,2 , что A ∈ D
(2)
n . Из (3), (7) вытекает, что
для любого простого числа p при всех k, n ∈ N
|F inv
n,1 | > n! · (p − 1)n · p−n2
· p2·n·(k−1−k·n) · |An,1|, (14)
|F inv
n,2 | > pn·(k−1−k·n) · (n! · (p − 1)n · p−n2
)2 · |An,2|. (15)
Отметим, что параметр k ∈ N в (3)–(5), (9)–(13) не встречается в явном виде, а в (6)–
(8), (14), (15) присутствует в явном виде. Следовательно, в первом случае доля соответ-
ствующих объектов не меняется при изменении параметра k, а во втором случае доля соо-
тветствующих объектов существенно зависит от параметра k.
3. Пусть M , M ′ ∈ An,i (i = 1, 2), т. е. если M = M1, то
M ′
1 :
{
q′
t+1 = A′ ◦ q′
t ⊕ B′ ◦ xt+1
y′
t+1 = C ′ ◦ q′
t ⊕ D′ ◦ xt+1
(t ∈ Z+),
46 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2007, №10
а если M = M2, то
M ′
2 :
{
q′
t+1 = A′ ◦ q′
t ⊕ B′ ◦ xt+1
y′
t+1 = C ′ ◦ q′
t+1
(t ∈ Z+).
Автоматы M , M ′ ∈ An,i (i = 1, 2) эквивалентные, если для любого q0 ∈ Zn
pk суще-
ствует такое q′
0 ∈ Zn
pk и, наоборот, для любого q′
0 ∈ Zn
pk существует такое q0 ∈ Zn
pk , что
инициальные автоматы (M,q0) и (M ′,q′
0) реализуют один и тот же оператор [9].
Теорема 3. Автоматы M , M ′ ∈ An,1 эквивалентные тогда и только тогда, когда
выполнены следующие условия:
(i) D = D′;
(ii) C ′ ◦ q′
0 ⊖ C ◦ q0 = 0;
(iii) для любого q0 ∈ Zn
pk существует такое q′
0 ∈ Zn
pk и, наоборот, для любого q′
0 ∈ Zn
pk
существует такое q0 ∈ Zn
pk, что C ′ ◦ (A′)j ◦ q′
0 ⊖ C ◦ Aj ◦ q0 = 0 (j = 1, . . . , 2 · pk·n − 2);
(iv) C ′◦(A′)j ◦B′⊖C◦Aj ◦B = O (j = 1, . . . , 2·pk·n−3), где O — нулевая (n×n)-матрица;
(v) C ′ ◦ B′ ⊖ C ◦ B = O.
Теорема 4. Автоматы M , M ′ ∈ An,2 эквивалентные тогда и только тогда, когда
выполнены следующие условия:
(i) C ′ ◦ B′ ⊖ C ◦ B = O, где O — нулевая (n × n)-матрица;
(ii) для любого q0 ∈ Zn
pk существует такое q′
0 ∈ Zn
pk и, наоборот, для любого q′
0 ∈ Zn
pk
существует такое q0 ∈ Zn
pk, что C ′ ◦ (A′)j ◦ q′
0 ⊖ C ◦ Aj ◦ q0 = 0 (j = 1, . . . , 2 · pk·n − 1);
(iii) C ′ ◦ (A′)j ◦ B′ ⊖ C ◦ Aj ◦ B = O (j = 1, . . . , 2 · pk·n − 2).
4. Рассмотрим задачy параметрической идентификации автомата M ∈ An,1.
Теорема 5. Каждая из матриц C и D автомата M ∈ An,1 идентифицируется един-
ственным образом посредством n-кратного эксперимента высоты 1.
Следствие 2. Если в автомате M ∈ An,1 матрица C обратимая, то автомат M
идентифицируется единственным образом посредством двух n-кратных экспериментов
высоты 1, двух n-кратных экспериментов высоты 2 и решения 2 · n систем линейных
уравнений n-го порядка над кольцом Zpk.
Если матрица C необратимая, то идентификация матриц A и B для автомата M ∈ An,1
сводится к решению при известных матрицах C и D системы нелинейных уравнений
C ◦ (Ai ◦ q0 ⊕
i−1
⊕
j=1
Ai−j ◦ B ◦ xj ⊕ B ◦ xi) = yi+1 ⊖ D ◦ xi+1
для всех q0 ∈ Zn
pk и x1 · · ·xi+1 ∈ (Zn
pk)i+1 (i = 1, . . . , pn·k − 1).
Решение задачи параметрической идентификации автомата M ∈ An,2 значительно сло-
жнее, так как возникает необходимость решения системы нелинейных уравнений
C ◦ (Ai+1 ◦ q0 ⊕
i−1
⊕
j=0
Ai−j ◦ B ◦ xj+1 ⊕ B ◦ xi+1) = yi+1
при неизвестной обратимой матрице C.
5. Построим каноническое представление автоматов (1) и (2). Множество Zn
pk представ-
ляет собой Zpk-модуль линейных форм [4]. Следовательно, каждое линейное преобразование
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2007, №10 47
Zn
pk в Zn
pk , иными словами, каждая матрица H ∈ Mn с помощью элементарных операций
(т. е. умножением слева и справа на соответствующие матрицы G, F ∈ M
inv
n , может быть
представлено в виде
G ◦ H ◦ F =
(
U Or,h
Oh,r V
)
, (16)
где U ∈ D
(1)
r , V ∈ D
(2)
h
(r+h = n), а Or,h — нулевая (r×h)-матрица. Обозначим через D
(1),(2)
n
множество всех матриц вида (16). Отметим, что матрица X ∈ D
(1),(2)
n осуществляет умно-
жение компонент вектора z ∈ Zn
pk на соответствующие элементы кольца Zpk , а множество
M
inv
n — группа, изоморфная подгруппе симметрической группы Spk·n .
Будем говорить, что автомат (M,q0) (M ∈ An,1
⋃
An,2) представлен в канонической
форме, если все выполняемые в его представлении линейные преобразования — элемен-
ты множеств D
(1),(2)
n и M
inv
n . Канонические формы автоматов (M1,q0) и (M2,q0) имеют,
соответственно, следующий вид:
(M1,q0) :
{
F−1
1 ◦ qt+1 = R1 ◦ X1 ◦ (F−1
1 ◦ qt) ⊕ R2 ◦ X2 ◦ (F−1
2 ◦ xt+1)
G3 ◦ yt+1 = X3 ◦ R3 ◦ (F−1
1 ◦ qt) ⊕ R4 ◦ X4 ◦ (F−1
4 ◦ xt+1)
(t ∈ Z+), (17)
(M2,q0) :
{
F−1
1 ◦ qt+1 = R1 ◦ X1 ◦ (F−1
1 ◦ qt) ⊕ R2 ◦ X2 ◦ (F−1
2 ◦ xt+1)
G3 ◦ yt+1 = X3 ◦ R3 ◦ (F−1
1 ◦ qt+1)
(t ∈ Z+), (18)
где Xi ∈ D
(1),(2)
n (i = 1, . . . , 4), Gi, Ri ∈ M
inv
n (i = 1, . . . , 4), причем X1 = G1 ◦ A ◦ F1,
X2 = G2 ◦ B ◦ F2, X3 = G3 ◦ C ◦ F3, X4 = G4 ◦ D ◦ F4, R1 = F−1
1 ◦ G−1
1 , R2 = F−1
1 ◦ G−1
2 ,
R3 = F−1
3 ◦ F1, а R4 = G3 ◦ G−1
4 .
Для автомата (M,q0) (M ∈ Ainv
n,1
⋃
Ainv
n,2) представления в канонической форме имеют
более простой вид, а именно:
(M1,q0) :
{
F−1
1 ◦ qt+1 = R1 ◦ X1 ◦ (F−1
1 ◦ qt) ⊕ R2 ◦ X2 ◦ (F−1
2 ◦ xt+1)
G3 ◦ yt+1 = X3 ◦ R3 ◦ (F−1
1 ◦ qt) ⊕ Y1 ◦ xt+1
(t ∈ Z+), (19)
(M2,q0) :
{
F−1
1 ◦ qt+1 = R1 ◦ X1 ◦ (F−1
1 ◦ qt) ⊕ Y2 ◦ xt+1
yt+1 = Y3 ◦ (F−1
1 ◦ qt+1)
(t ∈ Z+), (20)
где Y1 = G3 ◦ D ∈ M
inv
n , Y2 = F−1
1 ◦ B ∈ M
inv
n и Y3 = C ◦ F1 ∈ M
inv
n .
В заключение отметим, что при логарифмическом весе [11] емкостная сложность пред-
ставления элемента z ∈ Zn
pk равна n · ⌈k · log p⌉, а емкостная сложность представления
матрицей W ∈ M
inv
n подстановки, определенной на множестве Zn
pk , равна n2 · ⌈k · log p⌉. Пе-
рестановку на множестве Zn
pk назовем легко вычислимой, если при логарифмическом весе
емкостная сложность ее представления и временная сложность ее применения к элемен-
ту z ∈ Zn
pk равна O(n · ⌈k · log p⌉). Изучение структуры множества таких подстановок —
предмет дальнейших исследований.
1. Гилл А. Линейные последовательностные машины. – Москва: Наука, 1974. – 288 с.
2. Лидл Р., Нидеррайтер Г. Конечные поля. Т. 1. – Москва: Мир, 1988. – 394 с.
48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2007, №10
3. Лидл Р., Нидеррайтер Г. Конечные поля. Т. 2. – Москва: Мир, 1988. – 428 с.
4. ван дер Варден Б.Л. Алгебра. – Москва: Наука, 1979. – 634 с.
5. Курмит А.А. Автоматы без потери информации конечного порядка. – Рига: Зинатне, 1972. – 266 с.
6. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке СИ. –
Москва: ТРИУМФ, 2003. – 816 с.
7. Харин Ю.С. и др. Математические и компьютерные основы криптологии. – Минск: Новое знание,
2003. – 382 с.
8. Глушков В.М. Синтез цифровых автоматов. – Москва: Физматлит, 1962. – 476 с.
9. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы (поведение и синтез). – Москва: Наука,
1970. – 400 с.
10. Коршунов А.Д. О перечислении конечных автоматов // Проблемы кибернетики. Вып. 34. – Москва:
Наука, 1978. – С. 5–82.
11. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – Москва:
Мир, 1979. – 536 с.
Поступило в редакцию 16.02.2007Институт прикладной математики
и механики НАН Украины, Донецк
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2007, №10 49
|
| id | nasplib_isofts_kiev_ua-123456789-3161 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-02T04:37:22Z |
| publishDate | 2007 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Скобелев, В.В. 2009-07-02T08:21:41Z 2009-07-02T08:21:41Z 2007 Исследование структуры множества линейных БПИ-автоматов над кольцом Zpk / В.В. Скобелев // Доп. НАН України. — 2007. — № 10. — С. 44-49. — Бібліогр.: 11 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/3161 510.5+681.3 For linear information-lossless automata over the ring Zp , we have established conditions and estimated cardinalities for sets of automata characterized via basic characteristics of automata theory (the transition graph is complete with a loop at each vertex, permutation and reduced automata, automata with twin states). For the investigated automata, a criterion of equivalence is established, the problem of parametric identification is resolved, and the canonical presentati- ons, in which all linear transformation are reduced to component-wise multiplication in the ring and to the application of reversible matrices, are designed. ru Видавничий дім "Академперіодика" НАН України Інформатика та кібернетика Исследование структуры множества линейных БПИ-автоматов над кольцом Zpk Article published earlier |
| spellingShingle | Исследование структуры множества линейных БПИ-автоматов над кольцом Zpk Скобелев, В.В. Інформатика та кібернетика |
| title | Исследование структуры множества линейных БПИ-автоматов над кольцом Zpk |
| title_full | Исследование структуры множества линейных БПИ-автоматов над кольцом Zpk |
| title_fullStr | Исследование структуры множества линейных БПИ-автоматов над кольцом Zpk |
| title_full_unstemmed | Исследование структуры множества линейных БПИ-автоматов над кольцом Zpk |
| title_short | Исследование структуры множества линейных БПИ-автоматов над кольцом Zpk |
| title_sort | исследование структуры множества линейных бпи-автоматов над кольцом zpk |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/3161 |
| work_keys_str_mv | AT skobelevvv issledovaniestrukturymnožestvalineinyhbpiavtomatovnadkolʹcomzpk |