Восстановление вектора начального состояния нелинейных автоматов над конечным кольцом
Для автоматів Мілі та Мура над скінченним комутативно-асоціативним кільцем з одиницею, функція переходів яких визначена за допомогою нелінійних рівнянь другого степеня, а функція виходу є відповідно афінним та лінійним відображенням множини станів, розв’язано задачу відновлення вектора початкового с...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/210844 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Восстановление вектора начального состояния нелинейных автоматов над конечным кольцом / В.Г. Скобелев // Проблемы управления и информатики. — 2010. — № 6. — С. 31-34. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859651656435630080 |
|---|---|
| author | Скобелев, В.Г. |
| author_facet | Скобелев, В.Г. |
| citation_txt | Восстановление вектора начального состояния нелинейных автоматов над конечным кольцом / В.Г. Скобелев // Проблемы управления и информатики. — 2010. — № 6. — С. 31-34. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Для автоматів Мілі та Мура над скінченним комутативно-асоціативним кільцем з одиницею, функція переходів яких визначена за допомогою нелінійних рівнянь другого степеня, а функція виходу є відповідно афінним та лінійним відображенням множини станів, розв’язано задачу відновлення вектора початкового стану. Розглянуто випадок, коли ця задача тривіальна. Виявлено, що у інших випадках ця задача є важкою. Встановлено, що властивість «бути оборотним автоматом» взагалі не впливає на складність розв’язання задачі відновлення вектора початкового стану для досліджуваних автоматів.
For Mealy and Moore automata presented via quadric equations over any finite associative-commutative ring with the unit it is resolved the problem of reconstruction of initial state vector. Situation when this problem is a trivial one is considered. It is shown that in any other situation investigated problem is difficult. It is also established that for investigated automata the quality «to be reversible one» has no influence onto hardness of resolving reconstruction problem of initial state vector.
|
| first_indexed | 2026-03-14T15:27:02Z |
| format | Article |
| fulltext |
© В.Г. СКОБЕЛЕВ, 2010
Международный научно-технический журнал
«Проблемы управления и информатики», 2010, № 6 31
УДК 519.712+681.3
В.Г. Скобелев
ВОССТАНОВЛЕНИЕ ВЕКТОРА
НАЧАЛЬНОГО СОСТОЯНИЯ НЕЛИНЕЙНЫХ
АВТОМАТОВ НАД КОНЕЧНЫМ КОЛЬЦОМ
Введение
Для автоматов, представленных уравнениями над конечной алгебраической
системой, естественной является формулировка задач в терминах теории систем
с последующим анализом решений систем уравнений. В частности, задача распо-
знавания начального состояния автомата (построение диагностического экспери-
мента с автоматом [1]) является задачей восстановления вектора начального со-
стояния соответствующей динамической системы. Рассмотрим решение этой
задачи для некоторых нелинейных автоматов над конечным коммутативно-ассо-
циативным кольцом ),,( KK с единицей (в дальнейшем кольцо ),K которые
выступают аналогами ряда модельных хаотических динамических систем [2] над
этим кольцом. Выбор кольца K в качестве алгебраической системы обусловлен
тем, что такие обратимые автоматы являются математическими моделями фраг-
ментов большинства из кандидатов на современные поточные шифры [3, 4].
1. Исследуемые модели
Пусть nM — множество всех )( nn -матриц над кольцом ,K а inv
nM —
множество всех обратимых матриц .nX M
В [5] рассмотрено решение задачи параметрической идентификации для та-
ких автоматов Мили 11 AM и Мура 22 AM , что 1A — множество всех авто-
матов, определенных уравнениями
,
11
1
T
1
ttt
ttttt
FG
ECA
xqy
xdqbqqq
),( Zt (1)
а 2A — множество всех автоматов, определенных уравнениями
,
11
1
T
1
tt
ttttt
G
ECA
qy
xdqbqqq
),( Zt (2)
где ,),,( T)()1( n
ttt qq q
T)()1(
),,(
n
ttt xx x и
T)()1(
),,(
n
ttt yy y — соответ-
ственно состояние автомата, входной и выходной символ в момент t, A, C, E,
G, nF M — фиксированные матрицы, а
nn Kbb T)()1( ),,( b и ,( )1(dd
nn Kd T)( ), — фиксированные векторы.
Рассмотрим задачу восстановления вектора начального состояния nK0q
автомата iiM A )2,1( i в предположении, что A, G, E, }{\ OF nM , .0b
Отметим, что в результате любого эксперимента с автоматом iiM A
)2,1( i вектор начального состояния
nK0q может быть восстановлен только
с точностью до множества )(
0 iMSq состояний, эквивалентных состоянию .0q
32 ISSN 0572-2691
Поэтому решение задачи восстановления вектора начального состояния nK0q
для автомата iiM A )2,1( i сводится к поиску такого множества W
),( nKW что истинно включение ).(
0 iMSW q
2. Восстановление вектора начального состояния автомата Мили
Рассмотрим автомат .11 AM Перепишем второе уравнение системы урав-
нений (1) в виде
11 ttt FG xyq ).( Zt (3)
Пусть .inv
nG M Положив 0t в (3), получим, что )( 11
1
0 xyq FG для
любого входного символа ,1
nKx т.е. вектор начального состояния автомата
11 AM однозначно определяется в результате любого простого эксперимента
длины 1.
Отсюда, в частности, вытекает, что если ,inv
nG M то 1M — приведенный
автомат (т.е. не имеющий эквивалентных состояний), все состояния которого яв-
ляются 1-различимыми.
Пусть .inv
nG M Из первого уравнения системы уравнений (1) вытекает, что
для любого входного слова in
i Kxx 1 в системе уравнений
iii FG
FG
FG
xyq
xyq
xyq
1
221
110
,
,
(4)
каждый из векторов состояния n
i K11 ,, qq может быть выражен через вектор
начального состояния .0
nKq Следовательно, (4) — это система (нелинейных,
если )1i уравнений над кольцом ,K в которой неизвестным является вектор
начального состояния .0q Пусть )( 1 iU xx — множество решений системы
уравнений (4). Тогда решение задачи восстановления вектора начального состоя-
ния
nK0q для автомата 11 AM имеет следующий вид:
1) в случае простого эксперимента с автоматом оно сводится к поиску такого
входного слова
nt
t Kxx 1 заранее неизвестной минимальной длины t, что
)()( 11 0
MSU t qxx и )()( 11 0
MSU i qxx для всех 1,,1 ti (множество
)( 1 tU xx — решение задачи восстановления вектора начального состояния
nK0q для автомата );11 AM
2) в случае l-кратного эксперимента )2( l с автоматом решение сводится
к поиску такого множества входных слов i
i
nti
t
i
K
)()(
1 xx ),,,1( li что
)()( 1
)()(
1
1
0
MSU
i
t
i
l
i
i
qxx
и )()( 1
)()(
1
1
0
MSU
i
jt
i
l
i
ii
qxx
для любых таких чи-
сел ij ),0( ii tj что 1
1
l
i
ij (множество )(
)()(
1
1
i
t
i
l
i
i
U xx
— решение задачи
восстановления вектора начального состояния
nK0q для автомата ).11 AM
Международный научно-технический журнал
«Проблемы управления и информатики», 2010, № 6 33
3. Восстановление вектора начального состояния автомата Мура
Рассмотрим автомат .22 AM Из системы уравнений (2) вытекает, что
).()( 11
T
dxyqbqq ttttt EGCAG
Из первого уравнения системы уравнений (2) следует, что для любого вход-
ного слова in
i Kxx 1 в системе уравнений
)()(
),()(
),()(
1
T
11
221
T
11
110
T
00
dxyqbqq
dxyqbqq
dxyqbqq
iiiii EGCAG
EGCAG
EGCAG
(5)
каждый из векторов состояния n
i K11 ,, qq может быть выражен вектором
начального состояния .0
nKq Следовательно, (5) — это система нелинейных
уравнений над кольцом ,K в которой неизвестным является вектор начального
состояния .0q Пусть )( 1 iV xx — множество решений системы уравнений (5).
Тогда решение задачи восстановления вектора начального состояния
nK0q для
автомата 22 AM имеет следующий вид:
1) в случае простого эксперимента с автоматом оно сводится к поиску такого
входного слова
nt
t Kxx 1 заранее неизвестной минимальной длины, что
)()( 11 0
MSV t qxx и )()( 11 0
MSV i qxx для всех 1,,1 ti (множество
)( 1 tV xx — решение задачи восстановления вектора начального состояния
nK0q для автомата );22 AM
2) в случае l-кратного эксперимента с автоматом решение сводится к поиску
такого множества входных слов i
i
nti
t
i
K
)()(
1 xx ),,,1( li что
)(
)()(
1
1
i
t
i
l
i
i
V xx
)( 10
MSq и )()( 1
)()(
1
1
0
MSV
i
jt
i
l
i
ii
qxx
для любых таких чисел ij ),0( ii tj
что 1
1
l
i
ij (множество
l
i
i
t
i
i
V
1
)()(
1 )(
xx — решение задачи восстановления век-
тора начального состояния
nK0q для автомата ).22 AM
Заключение
Полученные результаты дают возможность сделать следующие выводы.
Восстановление вектора начального состояния
nK0q для автомата Мили
11 AM — тривиальная задача, если .inv
nG M Во всех остальных случаях вос-
становление вектора начального состояния
nK0q для автомата iiM A
)2,1( i — трудная задача. Высокая сложность ее решения обусловлена следую-
щими обстоятельствами. Во-первых, это сложность поиска по множеству вход-
ных слов. Во-вторых, это сложность поиска решений систем уравнений над коль-
цом K (даже над полями Галуа )2( kGF решение системы уравнений 2-й степени
от многих переменных — NP-полная задача). В-третьих, это сложность проверки
свойства «быть подмножеством множества эквивалентных состояний автомата».
В [5] отмечено, следующее: 1) 11 AM — обратимый автомат тогда и только
тогда, когда F — обратимая матрица; 2) 22 AM — обратимый автомат тогда
34 ISSN 0572-2691
и только тогда, когда E и G — обратимые матрицы. Таким образом, переход к об-
ратимым автоматам ничуть не упрощает решение задачи восстановления вектора
начального состояния для исследуемых автоматов. При использовании обрати-
мого автомата iiM A )2,1( i в качестве поточного шифра вектор начального
состояния nK0q играет роль секретного сеансового ключа. Поэтому при ис-
пользовании обратимого автомата Мили в качестве поточного шифра должно
быть обеспечено условие .inv
nG M
Дальнейшие исследования предполагают выделение и исследование под-
множеств автоматов, определяемых ограничениями на структуру параметров, для
которых решение задачи восстановления вектора начального состояния проще,
чем в общем случае. Это можно осуществить, по крайней мере, следующими дву-
мя способами: во-первых, выделив подмножества автоматов с достаточно простой
структурой множеств эквивалентных состояний; во-вторых, выделив подмноже-
ства автоматов, для которых решение систем уравнений (4) или (5) сводится
к стандартным методам решения сравнений.
В.Г. Скобелєв
ВІДНОВЛЕННЯ ВЕКТОРА
ПОЧАТКОВОГО СТАНУ НЕЛІНІЙНИХ
АВТОМАТІВ НАД СКІНЧЕННИМ КІЛЬЦЕМ
Для автоматів Мілі та Мура над скінченним комутативно-асоціативним кіль-
цем з одиницею, функція переходів яких визначена за допомогою нелінійних
рівнянь другого степеня, а функція виходу є відповідно афінним та лінійним
відображенням множини станів, розв’язано задачу відновлення вектора по-
чаткового стану. Розглянуто випадок, коли ця задача тривіальна. Виявлено,
що у інших випадках ця задача є важкою. Встановлено, що властивість «бути
оборотним автоматом» взагалі не впливає на складність розв’язання задачі
відновлення вектора початкового стану для досліджуваних автоматів.
V.G. Skobelev
RECONSTRUCTION OF INITIAL STATE VECTOR
FOR NONLINEAR AUTOMATA OVER FINITE RING
For Mealy and Moore automata presented via quadric equations over any finite as-
sociative-commutative ring with the unit it is resolved the problem of reconstruc-
tion of initial state vector. Situation when this problem is a trivial one is consi-
dered. It is shown that in any other situation investigated problem is difficult. It is
also established that for investigated automata the quality «to be reversible one»
has no influence onto hardness of resolving reconstruction problem of initial state
vector.
1. Гилл А. Введение в теорию конечных автоматов. — М. : Наука, 1966. — 272 с.
2. Кузнецов С.П. Динамический хаос. — М. : Физматлит, 2001. — 296 с.
3. Харин Ю.С., Берник В.И., Матвеев Г.В. и др. Математические и компьютерные основы
криптологии. — Минск : Новое знание, 2003. — 382 с.
4. Алферов А.П., Зубов А.Ю., Кузьмин А.С. и др. Основы криптографии. — М. : Гелиос АРВ,
2002. — 480 с.
5. Скобелев В.Г.Анализ задачи параметрической идентификации нелинейных автоматов над
конечным кольцом // Международный научно-технический журнал «Проблемы управления
и информатики». — 2010. — № 5. — С. 37–41.
Получено 24.06.2010
|
| id | nasplib_isofts_kiev_ua-123456789-210844 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2026-03-14T15:27:02Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Скобелев, В.Г. 2025-12-18T09:36:45Z 2010 Восстановление вектора начального состояния нелинейных автоматов над конечным кольцом / В.Г. Скобелев // Проблемы управления и информатики. — 2010. — № 6. — С. 31-34. — Бібліогр.: 5 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210844 519.712+681.3 10.1615/JAutomatInfScien.v42.i11.30 Для автоматів Мілі та Мура над скінченним комутативно-асоціативним кільцем з одиницею, функція переходів яких визначена за допомогою нелінійних рівнянь другого степеня, а функція виходу є відповідно афінним та лінійним відображенням множини станів, розв’язано задачу відновлення вектора початкового стану. Розглянуто випадок, коли ця задача тривіальна. Виявлено, що у інших випадках ця задача є важкою. Встановлено, що властивість «бути оборотним автоматом» взагалі не впливає на складність розв’язання задачі відновлення вектора початкового стану для досліджуваних автоматів. For Mealy and Moore automata presented via quadric equations over any finite associative-commutative ring with the unit it is resolved the problem of reconstruction of initial state vector. Situation when this problem is a trivial one is considered. It is shown that in any other situation investigated problem is difficult. It is also established that for investigated automata the quality «to be reversible one» has no influence onto hardness of resolving reconstruction problem of initial state vector. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы идентификации и адаптивного управления Восстановление вектора начального состояния нелинейных автоматов над конечным кольцом Відновлення вектора початкового стану нелінійних автоматів над скінченним кільцем Reconstruction of initial state vector for nonlinear automata over finite ring Article published earlier |
| spellingShingle | Восстановление вектора начального состояния нелинейных автоматов над конечным кольцом Скобелев, В.Г. Методы идентификации и адаптивного управления |
| title | Восстановление вектора начального состояния нелинейных автоматов над конечным кольцом |
| title_alt | Відновлення вектора початкового стану нелінійних автоматів над скінченним кільцем Reconstruction of initial state vector for nonlinear automata over finite ring |
| title_full | Восстановление вектора начального состояния нелинейных автоматов над конечным кольцом |
| title_fullStr | Восстановление вектора начального состояния нелинейных автоматов над конечным кольцом |
| title_full_unstemmed | Восстановление вектора начального состояния нелинейных автоматов над конечным кольцом |
| title_short | Восстановление вектора начального состояния нелинейных автоматов над конечным кольцом |
| title_sort | восстановление вектора начального состояния нелинейных автоматов над конечным кольцом |
| topic | Методы идентификации и адаптивного управления |
| topic_facet | Методы идентификации и адаптивного управления |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/210844 |
| work_keys_str_mv | AT skobelevvg vosstanovlenievektoranačalʹnogosostoâniânelineinyhavtomatovnadkonečnymkolʹcom AT skobelevvg vídnovlennâvektorapočatkovogostanunelíníinihavtomatívnadskínčennimkílʹcem AT skobelevvg reconstructionofinitialstatevectorfornonlinearautomataoverfinitering |