Характеристики линейных одномерных автоматов с лагом l над конечным кольцом
Збережено в:
| Опубліковано в: : | Труды Института прикладной математики и механики НАН Украины |
|---|---|
| Дата: | 2008 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2008
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/19998 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Характеристики линейных одномерных автоматов с лагом l над конечным кольцом / В.В. Скобелев // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 16. — С. 190-196. — Бібліогр.: 11 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859912356192059392 |
|---|---|
| author | Скобелев, В.В. |
| author_facet | Скобелев, В.В. |
| citation_txt | Характеристики линейных одномерных автоматов с лагом l над конечным кольцом / В.В. Скобелев // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 16. — С. 190-196. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Труды Института прикладной математики и механики НАН Украины |
| first_indexed | 2025-12-07T16:03:02Z |
| format | Article |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2008. Том 16
УДК 518.6+681.3
c©2008. В.В. Скобелев
ХАРАКТЕРИСТИКИ ЛИНЕЙНЫХ ОДНОМЕРНЫХ АВТОМАТОВ С
ЛАГОМ l НАД КОНЕЧНЫМ КОЛЬЦОМ
Для линейных одномерных автоматов с лагом l над кольцом Zpk охарактеризован подкласс, со-
стоящий из БПИ-автоматов. Исследована структура классов сильно связных и перестановочных
линейных одномерных автоматов с лагом l над кольцом Zpk .
Введение. Естественным обобщением регистров сдвига с линейной обратной
связью [1], построенных над полемGF(pk) (где p – простое число, а k ∈ N), являются
линейные управляемые последовательности над кольцом
Zpk = (Zpk ,⊕, ◦),
где
a⊕ b = a + b (mod pk),
a ◦ b = ab (mod pk).
В [2] с позиции как современной теории кодирования, так и с позиции совре-
менной криптографии, исследованы свойства таких последовательностей, в случае,
когда управление – тождественный нуль.
Однако с указанных выше позиций, а также с позиции теории автоматов [3–
5], значительно больший интерес представляет исследование поведения такой пары
взаимодействующих линейных управляемых последовательностей, что одна из них
определяет изменение состояния, а вторая – выходной символ. Таким образом, мы
естественно приходим к одномерным линейным автоматам с лагом l над конечным
кольцом. Отметим следующие три обстоятельства.
Во-первых, по-видимому, первая попытка систематического исследования таких
автоматов именно с позиции математической теории систем [6, 7] предпринята в [8,
9].
Во-вторых, фрагменты схем, построенных на основе указанных пар последова-
тельностей являются типичными, практически, для всех кандидатов, представлен-
ных в реализуемых в настоящее время европейском и японском проектах, соответ-
ственно, NESSIE и CRYPTREC, разработки схем поточного шифрования.
В третьих, такие автоматы являются нетривиальным обобщением специального
случая n-мерных линейных автоматов над конечным кольцом, исследованных в [10].
Отличие настоящей работы от [8, 9] состоит в том, что мы исследуем именно
те свойства, которые естественно формулируются в классических терминах теории
автоматов.
190
Линейные одномерные автоматы
Структура работы – следующая. В п.1 введены необходимые понятия и опреде-
ления. В п.2 охарактеризованы некоторые подклассы исследуемых моделей. Заклю-
чение содержит ряд выводов.
1. Основные понятия и определения.Объектом исследования являются ини-
циальные автоматы Мили и Мура, определяемые, соответственно, уравнениями
(M1,q0) :
qn+l =
l⊕
i=1
ai ◦ qn+l−i ⊕ b ◦ xn+1
yn+1 =
l⊕
i=1
ci ◦ qn+l−i ⊕ d ◦ xn+1
(1)
и
(M2,q0) :
qn+l =
l⊕
i=1
ai ◦ qn+l−i ⊕ b ◦ xn+1
yn+1 =
l⊕
i=1
ci ◦ qn+l+1−i
, (2)
где ai, bi, c, d ∈ Zpk (i = 1, . . . , l) – параметры, x и y – соответственно, входная и
выходная переменная, а q0 = (q0, q1, . . . , ql−1) ∈ Zl
pk – начальное состояние автомата
Mj (j = 1, 2).
Обозначим через Al,j (j = 1, 2) – множество всех автоматов Mj . Из (1) и (2)
вытекает, что для всех l ∈ N
|Al,j | = pk·(2·l+3−j) (j = 1, 2). (3)
При решении задач разработки методов защиты информации особый интерес
представляет случай, когда Mj (j = 1, 2) – БПИ-автомат [11], т.е. когда ограниченно-
детерминированная функция f : Z+
pk → Z+
pk , реализуемая инициальным автоматом
(Mj ,q0) (j = 1, 2), является биекцией при любом начальном состоянии q0 ∈ Zl
pk . В
связи с этим обозначим через Ainv
l,j (j = 1, 2) множество всех обратимых автоматов
Mj ∈ Al,j .
Из (1) и (2) вытекает
Утверждение 1. Для всех l ∈ N:
1) M1 ∈ Ainv
l,1 тогда и только тогда, когда d – обратимый элемент кольца Zpk .
2) M2 ∈ Ainv
l,2 тогда и только тогда, когда c1 и b – обратимые элементы кольца
Zpk .
Из утверждения 1 вытекает, что обратные автоматы имеют следующий вид:
(M−1
1 ,q0) :
qn+1 =
l⊕
i=1
αi ◦ qn+l−i ⊕ β ◦ xn+1
yn+1 =
l⊕
i=1
γi ◦ qn+l−i ⊕ δ ◦ xn+1
,
191
В.В. Скобелев
где β = b ◦ d−1, δ = d−1 и αi = ai ª b ◦ d−1 ◦ ci, γi = ªd−1 ◦ ci для всех i = 1, . . . , l,
(M−1
2 ,q0) :
qn+l =
l⊕
i=2
αi ◦ qn+l+1−i ⊕ β ◦ xn+1
yn+1 =
l⊕
i=1
γi ◦ qn+l+1−i ⊕ δ ◦ xn+1
,
где β = c−1
1 , δ = b−1 ◦ c−1
1 , αi = c−1
1 ◦ ci (i = 2, . . . , l) и
γi =
{
ªb−1 ◦ (c−1
1 ◦ ci+1 ⊕ ai), i = 1, . . . , l − 1
ªb−1 ◦ al, i = l
.
Из (3) и утверждения 1 вытекает, что для всех l ∈ N
|Ainv
l,j | = p−j · (p− 1)j · |Al,j | (j = 1, 2). (4)
Из (4) вытекает, что истинно
Следствие 1. Для всех l ∈ N
|Ainv
l,j |
|Al,j | = p−j · (p− 1)j (j = 1, 2).
Итак, показано, что в множестве Al,j (j = 1, 2) доля обратимых автоматов не
зависит от значения числа k.
2. Основные результаты. Охарактеризуем некоторые подмножества множеств
Al,j (j = 1, 2) и Ainv
l,j (j = 1, 2), естественно определяемые в терминах теории авто-
матов.
Теорема 1. Для всех l ∈ N автомат Mi ∈ Al,j (j = 1, 2) – сильно связный
тогда и только тогда, когда b – обратимый элемент кольца Zpk .
Доказательство.
1. Необходимость. Пусть автомат Mi ∈ Al,j (j = 1, 2) – сильно связный. Тогда
для любых двух его состояний q = (q0, q1, . . . , ql−1) ∈ Zl
pk и q′ = (q′0, q
′
1, . . . , q
′
l−1) ∈
Zl
pk существует входное слово x1x2 . . . xn ∈ Zn
pk , переводящее состояние q в состояние
q′.
Предположим противное, т. е. что b – необратимый элемент кольца Zpk . Тогда
b ≡ 0 (mod p).
Рассмотрим любое такое состояние q0 = (q0, q1, . . . , ql−1) автомата Mj (j = 1, 2),
что
qi ≡ 0 (mod p)
для всех i = 0, 1, . . . , l − 1.
Из 1-го уравнения, определяющего автомат Mj , вытекает, что
ql ≡ 0 (mod p)
192
Линейные одномерные автоматы
для любого входного символа x ∈ Zpk . Таким образом, состояние q0 под действием
любого входного символа x ∈ Zpk переходит в такое состояние q1 = (q1, . . . , ql−1, ql) ∈
Zl
pk , что qi ≡ 0 (mod p) для всех i = 1, . . . , l.
Отсюда вытекает (что доказывается индукцией по длине входного слова), что
для любого входного слова x1x2 . . . xn ∈ Zn
pk состояние q0 переходит в такое состоя-
ние qn = (qn, qn+1, . . . , qn+l−1) ∈ Zl
pk , что qi ≡ 0 (mod p) для всех i = n, n + 1, . . . , n +
l − 1.
Это означает, что из состояния q0 недостижимо ни одно состояние q′ =
(q′0, . . . , q
′
l−1) ∈ Zl
pk , удовлетворяющее следующему условию: существует такое j ∈
{0, 1, . . . , l − 1}, что q′j ≡ m (mod p), где m ∈ {1, 2, ..., l − 1}. Отсюда вытекает, что
автомат Mj не является сильно связным.
Полученное противоречие показывает, что предположение – ложное, т. е. если
Mj ∈ Al,j (j = 1, 2) – сильно связный автомат, то b – обратимый элемент кольца
Zpk , что и требовалось показать.
2. Достаточность. Пусть b – обратимый элемент кольца Zpk . Покажем, что из
любого состояния q0 = (q0, q1, ..., ql−1) ∈ Zl
pk автомата Mj (j = 1, 2) достижимо
любое его состояние q′0 = (q′0, q
′
1, ..., q
′
l−1) ∈ Zl
pk .
Выберем такое входное слово x1...xl ∈ Zl
pk , что
b ◦ xi+1 = q′i ª
i⊕
m=1
am ◦ q′i−m ª
l−1⊕
m=i
am ◦ qm (i = 0, 1, ..., l − 1). (5)
Так как b – обратимый элемент кольца Zpk , то система (5) имеет единственное
решение
xi+1 = b−1 ◦ (q′i ª
i⊕
m=1
am ◦ q′i−m ª
l−1⊕
m=i
am ◦ qm) (i = 0, 1, ..., l − 1). (6)
Из 1-го уравнения, определяющего автомат Mj (j = 1, 2) вытекает, что входное
слово x1...xl ∈ Zl
pk , где xi+1 (i = 0, 1, ..., l−1) определяется равенством (6), порождает
следующую последовательность переходов состояний автомата Mj (j = 1, 2)
q0 → q1 → ... → ql−1 → ql = q′0, (7)
где
qi = (qi, ..., ql−1, q
′
0, q
′
1, ..., q
′
i−1) (i = 1, ..., l). (8)
Из (8) вытекает, что если b – обратимый элемент кольца Zpk , то из любого состо-
яния q0 ∈ Zl
pk автомата Mj (j = 1, 2) достижимо любое его состояние q′0 ∈ Zl
pk . Это
означает, что Mj (j = 1, 2) – сильно связный автомат, что и требовалось показать.
Теорема доказана.
Обозначим через Asc
l,j (j = 1, 2) множество всех сильно связных автоматов Mj ∈
Al,j .
193
В.В. Скобелев
Из теоремы 1 вытекает, что для всех l ∈ N
|Asc
l,j | = p−1 · (p− 1) · |Al,j | (j = 1, 2).
Следующее утверждение характеризует степень достижимости [5] автомата Mj ∈
Asc
l,j (j = 1, 2).
Утверждение 2. Для всех l ∈ N диаметр графа переходов любого автомата
Mj ∈ Asc
l,j (j = 1, 2) равен l.
Доказательство. Выберем такие состояния q0 = (q0, q1, ..., ql−1) ∈ Zl
pk и q′0 =
(q′0, q
′
1, ..., q
′
l−1) ∈ Zl
pk , что
q′i 6= qi
для всех i = 0, 1, ..., l − 1.
Из (5)–(8) вытекает, что x1, ..., xl ∈ Zl
pk – кратчайшее входное слово, переводящее
состояние q0 в состояние q′0. Следовательно, диаметр графа переходов автомата Mj
равен l.
Утверждение доказано.
Положим
Asc−inv
l,j = Asc
l,j
⋂
Ainv
l,j (j = 1, 2).
Из утверждения 1 и теоремы 1 вытекает, что для всех l ∈ N
Ainv
l,2 ⊂ Asc−inv
l,2
и
|Asc−inv
l,j | = p−2 · (p− 1)2 · |Al,i| = (1− p−1)2 · |Al,j | (j = 1, 2).
Теорема 2. Для всех l ∈ N автомат Mj ∈ Al,j (j = 1, 2) – перестановочный
тогда и только тогда, когда al – обратимый элемент кольца Zpk .
Доказательство. Автомат Mj ∈ Al,j (j = 1, 2) не является перестановочным то-
гда и только тогда, когда существуют два такие его состояния q0 = (q0, q1, ..., ql−1) ∈
Zl
pk и q′0 = (q′0, q
′
1...., q
′
l−1) ∈ Zl
pk и такой входной символ x ∈ Zpk , что
q1 = q′1, (9)
где q1 = (q1, ..., ql−1, ql) и q′1 = (q′1, ..., q
′
l−1, q
′
l), а ql и q′l вычисляются из 1-го уравне-
ния, определяющего автомат Mj .
Из (9) вытекает, что
qi = q′i (i = 1, ..., l). (10)
Так как
q0 6= q′0,
то равенство (9) эквивалентно тому, что
q0 = (q0, q1, ..., ql−1),
194
Линейные одномерные автоматы
q′0 = (q′0, q1, ..., ql−1),
где
q0 6= q′0
и
ql = q′l.
Из 1-го уравнения, определяющего автомат Mj (j = 1, 2) вытекает, что равенство
ql = q′l эквивалентно тому, что q′0 ª q0 — ненулевое решение уравнения
al ◦ u = 0. (11)
Уравнение (11) имеет ненулевое решение тогда и только тогда, когда al ≡ 0 (mod
p), т. е. когда al – необратимый элемент кольца Zpk .
Итак, показано, что автомат Mj ∈ Al,j (j = 1, 2) не является перестановочным
автоматом тогда и только тогда, когда элемент al ∈ Zpk не является обратимым
элементом кольца Zpk .
Теорема доказана.
Обозначим через Ap
l,j (j = 1, 2) множество всех перестановочных автоматов Mj ∈
Al,i. Из (3) и теоремы 2 вытекает, что для всех l ∈ N
|Ap
l,j | = (1− p−1) · |Al,j | (j = 1, 2).
Положим
Ap−inv
l,j = Ainv
l,j
⋂
Ap
l,j (j = 1, 2).
Из утверждения 1, теоремы 2 и (3) вытекает, что для всех l ∈ N
|Ap−inv
l,j | = (1− p−1)j+1 · |Al,j | (j = 1, 2).
Заключение. В настоящей работе установлен ряд характеристик для линей-
ных одномерных автоматов Мили и Мура с лагом l над кольцом Zpk . Исследована
структура подклассов, состоящих из сильно связных автоматов, из перестановочных
автоматов, а также подсчитано число автоматов в этих классах. Охарактеризована
структура подкласса БПИ-автоматов, которые представляют особый интерес при
решении задач защиты информации.
Характеристика структуры классов эквивалентных состояний для автоматов,
принадлежащих множествам Al,j , Ainv
l,j (j = 1, 2), а также поиск критерия эквива-
лентности автоматов, принадлежащих этим множествам, представляет собой одно
из направлений дальнейших исследований.
Другое направление исследований состоит в анализе сложности параметриче-
ской идентификации и сложности идентификации начального состояния для авто-
матов, принадлежащих множествам Al,j , Ainv
l,j (j = 1, 2).
195
В.В. Скобелев
1. Блейхут Р. Теория и практика кодов, контролирующих ошибки. – М.: Мир, 1986. – 576с.
2. Кузьмин А.С., Куракин В.Л., Нечаев А.А. Свойства линейных и полилинейных рекуррент над
кольцами Галуа (I) / В кн.: Труды по дискретной математике. Т.2. – М.: ТВП, 1998. – С.191-222.
3. Глушков В.М. Синтез цифровых автоматов. – М: Физматгиз, 1962. – 476c.
4. Кудрявцев В.Б. и др. Введение в теорию конечных автоматов. – М: Наука, 1985. – 320c.
5. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы: поведение и синтез. – М: Наука, 1970.
– 400c.
6. Калман Р., Фалб П., Арбиб М. Очерки по математической теории систем. – М: Мир, 1971. –
400c.
7. Месарович М., Такахара Я. Общая теория систем: математические основы. – М: Мир, 1978. –
311c.
8. Фараджев Р.Г. Линейные последовательностные машины. – М: Советское радио, 1975. – 248c.
9. Гилл А. Линейные последовательностные машины. – М: Наука, 1974. – 287c.
10. Скобелев В.В. Исследование структуры множества линейных БПИ-автоматов над кольцом Zpk
// Доповiдi НАН України. – 2007. – №10. – С.44-49.
11. Курмит А.А. Автоматы без потери информации конечного порядка. – Рига: Зинатне, 1972. –
266c.
Ин-т прикл. математики и механики НАН Украины, Донецк
vv_skobelev@iamm.ac.donetsk.ua
Получено 20.03.08
196
содержание
Том 16
Донецк, 2008
Основан в 1997г.
содержание
Том 16
Донецк, 2008
Основан в 1997г.
|
| id | nasplib_isofts_kiev_ua-123456789-19998 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1683-4720 |
| language | Russian |
| last_indexed | 2025-12-07T16:03:02Z |
| publishDate | 2008 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Скобелев, В.В. 2011-05-19T19:31:21Z 2011-05-19T19:31:21Z 2008 Характеристики линейных одномерных автоматов с лагом l над конечным кольцом / В.В. Скобелев // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 16. — С. 190-196. — Бібліогр.: 11 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/19998 518.6+681.3 ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики НАН Украины Характеристики линейных одномерных автоматов с лагом l над конечным кольцом Article published earlier |
| spellingShingle | Характеристики линейных одномерных автоматов с лагом l над конечным кольцом Скобелев, В.В. |
| title | Характеристики линейных одномерных автоматов с лагом l над конечным кольцом |
| title_full | Характеристики линейных одномерных автоматов с лагом l над конечным кольцом |
| title_fullStr | Характеристики линейных одномерных автоматов с лагом l над конечным кольцом |
| title_full_unstemmed | Характеристики линейных одномерных автоматов с лагом l над конечным кольцом |
| title_short | Характеристики линейных одномерных автоматов с лагом l над конечным кольцом |
| title_sort | характеристики линейных одномерных автоматов с лагом l над конечным кольцом |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/19998 |
| work_keys_str_mv | AT skobelevvv harakteristikilineinyhodnomernyhavtomatovslagomlnadkonečnymkolʹcom |