О K-теории динамических систем, соответствующих графам, и ее применении

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2013
1. Verfasser:	Устименко, В.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Видавничий дім "Академперіодика" НАН України 2013
Schriftenreihe:	Доповіді НАН України
Schlagworte:	Інформатика та кібернетика
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/85861
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	О K-теории динамических систем, соответствующих графам, и ее применении / В.А. Устименко // Доповiдi Нацiональної академiї наук України. — 2013. — № 8. — С. 44–51. — Бібліогр.: 15 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-85861
record_format	dspace
spelling	irk-123456789-858612015-08-27T03:01:56Z О K-теории динамических систем, соответствующих графам, и ее применении Устименко, В.А. Інформатика та кібернетика Определяются некоторые классы зависимых от времени дискретных динамических систем. Определение мотивировано проблемами криптографии, основанной на полиномиальных преобразованиях от многих переменных, в частности, поиском циклических групп полиномиальных преобразований неограниченного порядка, образованных преобразованиями степени, не более 3. Существование определенных аксиомами дискретных динамических систем доказывается методами конструктивной экстремальной теории графов. Некоторые динамические системы определяются по построению новых примеров семейств графов большого обхвата суперлинейного размера. В частности, приводится конструкция такого семейства графов без реберно транзитивной группы автоморфизмов. Построены также новые примеры семейств графов с большим цикловым показателем. Визначаються деякi класи залежних вiд часу дискретних динамiчних систем. Означення мотивованi проблемами криптографiї, що базується на полiномiальних перетвореннях вiд багатьох змiнних, зокрема пошуком циклiчних груп полiномiальних перетворень необмеженого порядку, утворених перетвореннями степенi не бiльше, нiж 3. Iснування визначених аксiомами дискретних динамiчних систем доводиться методами конструктивної екстремальної теорiї графiв. Деякi динамiчнi системи визначаються за побудовою нових прикладiв сiмей графiв великого обхвату суперлiнiйного розмiру. Зокрема наводиться конструкцiя такої сiм’ї графiв без реберно транзитивної групи автоморфiзмiв. Побудовано також новi приклади сiмей графiв з великим цикловим показником. Special classes of time-dependent discrete dynamical systems are defined. The definitions are motivated by problems of multivariate cryptography, in particular, by the search for sequences of cyclic groups of polynomial transformations in the increasing number of variables of unbounded order formed by elements of a degree of at most 3. The existence of the dynamical systems defined by axioms is proven by methods of the constructive extremal graph theory. Some dynamical systems are defined by new explicit constructions of the families of simple graphs of large girth with superlinear size. We introduce the construction of such family without edge transitive automorphism group. Some new families of graphs with large cycle indicator are introduced. 2013 Article О K-теории динамических систем, соответствующих графам, и ее применении / В.А. Устименко // Доповiдi Нацiональної академiї наук України. — 2013. — № 8. — С. 44–51. — Бібліогр.: 15 назв. — рос. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/85861 519.176,519.157.2 ru Доповіді НАН України Видавничий дім "Академперіодика" НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Інформатика та кібернетика Інформатика та кібернетика
spellingShingle	Інформатика та кібернетика Інформатика та кібернетика Устименко, В.А. О K-теории динамических систем, соответствующих графам, и ее применении Доповіді НАН України
description	Определяются некоторые классы зависимых от времени дискретных динамических систем. Определение мотивировано проблемами криптографии, основанной на полиномиальных преобразованиях от многих переменных, в частности, поиском циклических групп полиномиальных преобразований неограниченного порядка, образованных преобразованиями степени, не более 3. Существование определенных аксиомами дискретных динамических систем доказывается методами конструктивной экстремальной теории графов. Некоторые динамические системы определяются по построению новых примеров семейств графов большого обхвата суперлинейного размера. В частности, приводится конструкция такого семейства графов без реберно транзитивной группы автоморфизмов. Построены также новые примеры семейств графов с большим цикловым показателем.
format	Article
author	Устименко, В.А.
author_facet	Устименко, В.А.
author_sort	Устименко, В.А.
title	О K-теории динамических систем, соответствующих графам, и ее применении
title_short	О K-теории динамических систем, соответствующих графам, и ее применении
title_full	О K-теории динамических систем, соответствующих графам, и ее применении
title_fullStr	О K-теории динамических систем, соответствующих графам, и ее применении
title_full_unstemmed	О K-теории динамических систем, соответствующих графам, и ее применении
title_sort	о k-теории динамических систем, соответствующих графам, и ее применении
publisher	Видавничий дім "Академперіодика" НАН України
publishDate	2013
topic_facet	Інформатика та кібернетика
url	http://dspace.nbuv.gov.ua/handle/123456789/85861
citation_txt	О K-теории динамических систем, соответствующих графам, и ее применении / В.А. Устименко // Доповiдi Нацiональної академiї наук України. — 2013. — № 8. — С. 44–51. — Бібліогр.: 15 назв. — рос.
series	Доповіді НАН України
work_keys_str_mv	AT ustimenkova okteoriidinamičeskihsistemsootvetstvuûŝihgrafamieeprimenenii
first_indexed	2025-07-06T13:12:40Z
last_indexed	2025-07-06T13:12:40Z
_version_	1836903364863983616
fulltext	УДК 519.176,519.157.2 В.А. Устименко О K-теории динамических систем, соответствующих графам, и ее применении (Представлено членом-корреспондентом НАН Украины А.Н. Трофимчуком) Определяются некоторые классы зависимых от времени дискретных динамических сис- тем. Определение мотивировано проблемами криптографии, основанной на полиноми- альных преобразованиях от многих переменных, в частности, поиском циклических групп полиномиальных преобразований неограниченного порядка, образованных преобра- зованиями степени, не более 3. Существование определенных аксиомами дискретных динамических систем доказывается методами конструктивной экстремальной теории графов. Некоторые динамические системы определяются по построению новых приме- ров семейств графов большого обхвата суперлинейного размера. В частности, приво- дится конструкция такого семейства графов без реберно транзитивной группы авто- морфизмов. Построены также новые примеры семейств графов с большим цикловым показателем. О полиномиальной криптографии от многих переменных и стабильных груп- пах преобразований. Поиск специальных дискретных динамических систем, завися- щих от времени, мотивирован, в частности, задачами полиномиальной криптографии от многих переменных, в том числе проблемой нахождения последовательностей цикличес- ких групп полиномиальных преобразований неограниченного порядка от возрастающе- го колличества переменных, образованных преобразованиями степени меньше 4. Семей- ства образующих таких последовательностей циклических групп будем называть стабиль- ными. Cуществование заданных аксиомами динамических систем доказывается методами экстремальной теории графов. В частности, используются новые конструкции простых и ориентированных графов большого обхвата и графов с большим цикленным показате- лем. Известно, что в случае K = Fq наилучший алгоритм отыскания решения систе- мы полиномиальных уравнений fi(x1, x2, . . . , xn) = bi, i = 1, 2, . . . , n, находящейся в “об- щем положении”, имеет оценку сложности dO(n), где d — максимальная степень полино- мов. Алгебраическая задача обращения полиномиального отображения (x1, x2, . . . , xn) → → (f1(x1, x2, . . . , xn), f2(x1, x2, . . . , xn), . . . , fn(x1, x2, . . . , xn)) является еще более сложной. Полиномиальная криптография от многих переменных изучает криптосистемы, безопас- ность которых основывается на сложности приведенных выше задач. Зачастую исполь- зуется следующая общая схема алгоритма с публичным ключом. Алиса (собственник ключа) использует набор нелинейных многочленов G1, G2, . . . , Gs группы Кремоны C(Kn), для которых вычислены обратные к ним полиномиальные отобра- жения G′ 1, G ′ 2, . . . , G′ s. Она вычисляет F = T1G1G2 . . . GsT2, где T1 и T2 — биективные афин- ные преобразования свободного модуля Kn. Публичное правило x1 ⇒ f1(x1, x2, . . . , xn), x2 ⇒ f2(x1, x2, . . . , xn), . . . , xn ⇒ fn(x1, x2, . . . , xn), соответствующее отображению F , пре- доставляется пользователям. Если степень нелинейного преобразования ограничена кон- стантой, а параметр n принят за переменную, то пользователь (Боб) может кодировать за полиномиальное от n время. © В. А. Устименко, 2013 44 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2013, №8 Алиса хранит в безопасности отображения G1, G2, . . . , Gs и декодирует полученные шифрограммы при помощи T ′ 2G ′ s, G ′ s−1, . . . , G′ 1T ′ 1. Исторический обзор исследований, на- чиная от криптосистемы Имаи Мацумото и ее криптоанализа, найденного Я. Патариным, можно найти в [1]. Примеры использования последовательностей стабильных полиномов вместе с небольшим числом быстро вычислимых многочленов высокой степени, образую- щих символический ключ, приводится в [2, 3]. Cемейство Gn стабильных кубических эле- ментов большого порядка может использоваться для протокола обмена ключами по схеме Диффи–Хеллмана в случае циклической группы 〈Gn〉 преобразований модуля Kn. Пользователи (Алиса и Боб) используют посланное по открытому каналу отображе- ние Gn. Они выбирают их персональные ключи KA (Алиса) и KB (Боб), являющие- ся достаточно большими натуральными числами. После этого пользователи обмениваю- тся кубическими преобразованиями Gka n и Gkb n соответственно. По завершению протоко- ла Алиса и Боб могут использовать общее “публичное правило” x1 ⇒ g1(x1, x2, . . . , xn), x2 ⇒ g2(x1, x2, . . . , xn), . . . , xn ⇒ gn(x1, x2, . . . , xn), cooтветствующее отображению Gkakb n , в виде списка коэффициентов у стандартном порядке или какой-либо быстровычиcлимой хаш-функции от полученного вектора. Безопасность протокола основывается на трудности проблемы дискретного логарифма для циклической группы с образующей Gn. При определенных условиях возникает задача “скрытого дискретного логарифма” — для вычисления порядка циклической группы не хватает вычислительных ресурсов ([4] и дальнейшие ссылки). О некоторых классах динамических систем. Пусть K — произвольное коммутатив- ное кольцо. Последовательность элементов кольца t1, t2, . . . , ts называется аддитивно устой- чивой, если произведение d элементов (ti + ti+1), не равно нулю. Последовательность эле- ментов кольца t1, t2, . . . , ts назовем циклически антинильпотентной, если элемент d(t1 + ts) является антинильпотентным, т. е. для любого натурального x элемент dx отличен от нуля. Пусть M — мультипликативное подмножество в K, т. е. замкнутое относительно умно- жения и не содержащее нуля. Тогда последовательность элементов t1 = t, t2 = −t + m1, t3 = t−m1 +m2, t4 = −t+m1 −m2 +m3, . . . , ts = −ts−1 +ms−1, где m1, m2, . . . , ms−1 — элементы из M , является аддитивно устойчивой при четном числе элементов. Для цикли- ческой нильпотентности достаточно добавить условие принадлежности t+ ts множеству M . Пусть Pn и Ln — две копии свободного модуля Kn. Cемейства обратимых регулярных отображений Dnt, где t принадлежит K, алгебраического многообразия PnULn назовем двудольной динамической системой большого обхвата, если 1) x ∈ Pn ⇒ Dnt(x) ∈ Ln, x ∈ Ln ⇒ Dnt(x) ∈ Pn; 2) (Dnt)−1 = Dnt′ для некоторого t′ из K, отличного от нуля; 3) существует константа c, c > 0, такая, что для некоторой линейной функции a(n) = = cn + d композиция Dnt1t2 · · · ts преобразований Dnt1, D nt2, . . . , Dnts, где 0 < s < a(n) и t1, t2, . . . , ts — аддитивно устойчивая последовательность, выполняется условие отличия Dnt1t2 · · · ts(x) от Dnr1r2 · · · rj(x), для всех x из K и всех отличных от последовательностей r1, r2, . . . , rj ∈ Kj, j < s + 1; 4) пусть t1, t2, . . . , ts — циклически антинильпотентная последовательность, тогда поря- док элемента Dnt1t2 · · · ts стремится к бесконечности с ростом параметра n. Заметим, что неравенство из условия 3 можно переписать в виде Dnt1t2 · · · tsr ′ jr ′ j−1 · · · · · · r′1(x) отлично от x. Это означает, что отображения вида Dnt1t2 · · · tsr1r2 · · · rj , где t1, t2, . . . , ts — аддитивно устойчивая последовательность и r1, r2, . . . , rj не совпадает с t′s, t′s−1, . . . , t ′ 1, не имеют неподвижных точек на PnULn. ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2013, №8 45 Заменив в условии 3 определения двудольной динамической системы большого обхва- та квантор “для всех” x, x ∈ PnULn на условие существования x, x ∈ PnULn, получим определение двудольной симметрической динамической системы большого цикленного по- казателя. Если Dt такая система, то отображения Dnt1t2 · · · ts и Dnr1r2 · · · rj , где t1, t2, . . . , ts — аддитивно устойчивая последовательность, а j < s + 1 совпадают только при равенстве последовательностей t1, t2, . . . , ts и r1, r2, . . . , rj . Заменив в приведенных выше опреде- лениях алгебраические многообразия PnULn (объединение двух копий свободного моду- ля Kn) на многообразие Kn, получим определения симметрической динамической системы большого обхвата и симметрической динамической системы с большим цикленным пока- зателем. Будем говорить, что введенные выше динамические системы являются кубическими, если все нетождественные преобразования вида Dnt1t2 . . . ts являются полиномиальными отображениями третьей степени. Отметим, что обратные для Dnt1t2 . . . ts отображения ку- бической системы также являются кубическими. Группы Gn D, порожденные операторами Dn t , t 6= 0, симметрической динамической систе- мы D большого обхвата (большого цикленного индикатора), образуют семейство подгрупп группы Кремоны C(Kn). В случае двудольной динамической системы D возникают группы преобразований 1Gn D и 2Gn D многообразия PnULn, порожденные Dnt1t2 . . . ts, действующие на Pn и Ln соответственно. Простые графы и теоремы существования. Элементарные сведения о простых гра- фах приведены в [8]. Напомним, что под обхватом простого графа понимают минимальную длину его цикла. Граф называется регулярным, если каждая его вершина имеет одинаковое количество соседей. Под размером e(G) графа G понимают число его ребер. Говорят, что бесконечное семейство графов Gi порядка vi имеет суперлинейный размер если e(Gi) = O(vti), где t > 1. Последовательность простых регулярных графов Gi возрастающего порядка vi степе- ни ki и обхвата gi называется семейством графов большого обхвата, если существует кон- станта c такая, что gi > c log ki(vi). Cуществование таких семейств было установлено П. Эрдешем в конце 50-х годов XX ст. с помощью широко известного вероятностного метода. Известны две конструкции семейств связных графов большого обхвата и суперлинейного размера (графы Кэли, являющиеся графами Рамануджана [6, 7] и заданные уравнениями графы CD(n, q)) [8]. Цикловым показателем вершины простого графа называют минимальную длину про- ходящего через нее цикла. Цикловым показателем h(G) графа G называют максимальное значение цикловых показателей его вершин. Последовательность простых ki регулярных графов возрастающего порядка и циклового показателя hi называется семейством графов большого циклового показателя, если сущест- вует константа c, такая, что hi > c log ki(vi). Существование такого семейства максимально возможного суперлинейного размера e(vi) ⇔ cv1+hi/2 установлено в [4]. Пусть Dn t , t ∈ K, — двудольная симметрическая динамическая система большого обхва- та (или циклового показателя). Рассмотрим простой двудольный граф Γn D(K) с долями Pn (множество точек) и Ln (множество прямых), такой, что инцидентность точки p и прямой l определяется условием: существует t ∈ K, такой, что Dn t (p) = l. Если кольцо K — конечно и k = K, то граф Γn D(K) имеет порядок 2kn и степень k. Из определения двудольной симметричной динамической системы D(K) большого обхва- 46 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2013, №8 та (большого цикленного показателя) вытекает, что последовательность графов большого обхвата Γn D(K) является семейством графов большого обхвата (большого циклового пока- зателя). Пусть теперь D — симметрическая динамическая система большого обхвата (большого циклового показателя) над кольцом K. Однопараметрическому семейству Dn t преобразо- ваний свободного модуля Kn сопоставим граф Γn D(K) с множеством вершин Kn, соответ- ствующем симметричному бинарному отношению: xIy ⇔ существует t ∈ K-{0}, такое, что Dnt(x) = y. Очевидно, что в случае, когда кольцо K является полем, последовательность графов Γn D(K) образует семейство графов большого обхвата. Введенные выше двудольные графы имеют регулярную раскраску ребер: ребро (x, y), x ∈ Pn, y ∈ Ln, окрашено в цвет t тогда и только тогда, когда Dnt(x) = y. Теорема 1. Для произвольного коммутативного кольца K существует 1) двудольная кубическая динамическая система большого обхвата со скоростью роста больше или равно 1/2; 2) кубическая динамическая система большого обхвата со скоростью роста больше или равно 1/4; 3) двудольная кубическая динамическая система большого цикленного показателя со скоростью роста больше или равно 1; 4) кубическая динамическая система большого цикленного показателя со скоростью роста больше или равно 1/2. Лемма 1. Пусть D(K) — двудольная симметрическая динамическая система боль- шого обхвата (циклового показателя) над коммутативным кольцом большого обхвата (циклового показателя) над коммутативным кольцом характеристики больше или рав- но 2. Тогда отображения D′n t = Dn t D n t , t > 0 образуют динамическую систему большого обхвата (циклового показателя, соответственно). Если скорость роста для D(K) превышает c, то скорость роста для D′(K) превыша- ет c/2. Будем говорить, что двудольная динамическая система большого обхвата имеет полярность n, если существует автоморфизм n графа Γn D(K), такой, что n2 = e, x ∈ Pn ⇒ ⇒ n(x) ∈ Ln, x ∈ Ln ⇒ n(x) ∈ Pn, переводящий ребро x, y цвета t ребро цвета t′. Лемма 2. Пусть D(K) — двудольная симметрическая система большого обхвата с по- лярностью n, имеющая скорость c. Тогда отображения D′n = Dntn образуют симметри- ческую динамическую систему большого обхвата со скоростью, превышающей c/2. Пусть D(K) — двудольная симметрическая динамическая система большого обхвата (циклового показателя) на последовательности многообразий PnULn. Рассмотрим после- довательность P ′ nUL′ n, где P ′ n и L′ n изоморфны свободному модулю Kn+1. Произвольный элемент P ′ n(L ′ n) отождествим с парой ((p),Dnt(p)), p ∈ Pn, t ∈ K([[l],Dnt(l)], l ∈ Ln, t ∈ K, соответственно). Рассмотрим двудольный граф с долями P ′ n и L′ n, соответствующий отображе- нию D′n+1t, заданному соотношениями D′n+1 t′((p),Dnt(p)) = [Dnt(p),Dnt′ − t(Dnt(p))]; D′n+1 t′([l],Dnt[l]) = [Dnt(l)),Dnt′ − t(Dnt(l))]. Лемма 3. Отображения D′n+1 t на многообразиях Kn+1UKn+1 образуют двудольную динамическую систему D′(K). Пусть n является полярностью двудольной симметрической динамической системы боль- шого обхвата (циклового показателя). Тогда естественное действие n на Kn+1UKn+1, опре- ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2013, №8 47 деленное соотношениями n((p),Dnt(p)) = (n(p), n(Dnt(p)), n([l],Dnt[p]) = (n[l], n(Dnt[l]), является полярностью системы D′(K). Лемма 4. Пусть п является полярностью двудольной динамической системы D(K) большого обхвата, определенной на последовательности многообразий Mn(K)UMn(K). То- гда отображения D′n t = Dn t n определяют динамическую систему на последовательности многообразий Mn(K). Лемма 5. Пусть D(K) — двудольная симметрическая динамическая система C(Dn t ) −1 = Dn −t со скоростью роста c, определенная над полем K, характеристики, отлич- ной от 2. Тогда семейство операторов Dn t D n t , t > 0 определяет симметрическую динамическую систему со скоростью роста не меньше, чем c/2. Лемма 6. Пусть D(K) — двудольная симметрическая динамическая система с (Dn t ) −1 = Dn −t со скоростью роста c, определенная над полем K. Тогда семейство опе- раторов D′n t = Dn oD ntDn o также образует двудольную динамическую систему с той же скоростью роста, что и D(K). Конструктивные примеры. Пусть K — конечное коммутативное кольцо. Рассмотрим двудольный граф A(n,K), определенный на множестве точек P = Kn и прямых L = Kn через отношение инцидентности I: x I y для x = (x1, x2, . . . , xn) из P и y = [y1, y2, . . . , yn] из L тогда и только тогда, когда выполняются соотношения x1 − y1 = y1x1, x2 − y2 = x1y2, x3−y3 = y1x2, x4−y4 = x1y3, . . . , xn−yn = x1yn−1 — при четном n и xn−yn = y1xn−1 — при нечетном значении n. Круглые и квадратные скобки позволяют различать точки и прямые. Определим цвет точки (x1, x2, . . . , xn) и прямой [y1, y2, . . . , yn] как значения первых коор- динат x1 и y1 этих векторов. Определенное выше семейство графов было введено в [9]. Его применения в криптографии и теории кодирования рассматривались в [10, 11]. Теорема 2. Пусть DAnt(x) — оператор вычисления соседа вершины x в графе A(n,K), тогда семейство отображений DAn t образует двудольную симметрическую динамичес- кую систему с большим цикленным показателем, удовлетворяющую условию 3 теоре- мы 1. Рассмотрим бесконечный двудольный граф D(K), определенный на множестве P точек x = (x1, x2, x3, x ′ 3, . . . , xn, x ′ n, . . .) и множестве L прямых y = [y1, y2, y3, y ′ 3, . . . , yn, y′n, . . .] через отношение инцидентности I : x I y для x из P и y из L тогда и только тогда, когда выполняются соотношения x2− y2 = y1x1, x3− y3 = x1y2, x4− y4 = y1x3, x5− y5 = x1y4, . . . , xn − yn = x1yn−1 — при нечетном n и xn − yn = y1xn−1 — при четном значении n, вместе с соотношениями x′3 − y′3 = y1x2, x ′ 4 − y′4 = x1y ′ 3, x5 − y5 = y1x ′ 4, . . . , x′n − y′n = y1x ′ n−1 — при нечетном n и x′n − y′n = x1yn−1 — при четном значении n. Рассмотрим также двудольный граф D(n,K), определенный на множестве точек Pn = = Kn и прямых Ln = Kn следующим образом: векторы xn иyn из Pn и Ln, соответственно, отождествляются с проекциями x ∈ P и y ∈ L на первые n координат, xn и yn связаны ребром тогда и только тогда, когда выполняются первые n−1 соотношений, определяющих инцидентность векторов x и y. Для случая K = Fq cемейство графов D(n,K) = D(n, q) было определено в [12]. Индуцированные подграфы CD(n, q) графов D(n, q) были введены в [8], где изучались экстремальные свойства подграфов. В общем случае графы D(n,K) и CD(n,K) впервые введены в [13]. Наиболее общие результаты о связности CD(n,K) получены в [14], динамические системы, соответствующие этим семействам графов, впервые рассматривались в [9]. Если K является коммутативным кольцом характеристики, отличной от 2, то граф CD(n,K) просто совпадает со связной компонентой D(n, q). Множества Pn 48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2013, №8 и Ln точек и прямых графа D(n, q) отождествляются с Kt, где t = [3/4n] + 1 для n = 0, 2, 3 mod 4 и t = [3/4n] + 2 для n = 1 mod 4. Теорема 3. Пусть Dnt(x) — оператор вычисления соседа вершины x в графе D(n,K), CDnt(x) — его ограничение на множество вершин графа CD(n,K). Тогда семейства ото- бражений Dn t и CDn t образуют двудольные симметрические динамические системы D(K) и CD(K) большого обхвата, удовлетворяющие условиям 1 и 2 теоремы 1, соответст- венно. Из этого утверждения следуют полученные ранее результаты, опубликованные в [9, 15]. Двудольные симметрические динамические последовательности D2n(K) и CD2n(K) систем D(K) и CD(K), соответственно, большого обхвата теоремы 3 имеют полярность n и ско- рость роста больше или равно 1/2 и больше или равно 2/3. Применение конструкции лем- мы 3 к этим последовательностям определяет кубическую симметрическую динамическую последовательность D12n(K) большого обхвата со скоростью роста больше или равно 1/4 и симметричесую последовательность CD12n(K) со скоростью роста больше или равно 1/3. Семейства графов Γ2n 1 (K) и CΓ2n 1 (K), соответствующие этим последовательностям, при K = Fq являются cемействами q − 1 регулярных графов большого обхвата (см. [9]). Пусть D(K) и CD(K) — двудольная симметрическая динамическая система большо- го обхвата теоремы 3, определенная над коммутативным кольцом K. Отображения Dn+1 2t на многообразиях Kn+1UKn+1, полученные применением построения леммы 4, образу- ют двудольную кубическую динамическую систему D2(K) большого обхвата со скоро- стью больше или равно 1/2. А отображения CDn+1 2 t образуют двудольную динамиче- скую систему CD2(K). Полярность n двудольной симметрической динамической после- довательности D2n(K)(CD2n(K)) индуцирует полярность двудольной динамической по- следовательности D2n+1 2 (K) (CD2n+1 2 (K), соответственно) большого обхвата. Конструкция леммы 5 определяет динамические последовательности D2n+1 3 (K) и CD2n+1 3 (K) большого обхвата. Приведенные выше примеры динамических систем определены над произвольным ком- мутативным кольцом. Пусть CD(F ) и DA(F ) — введенные выше двудольные симметри- ческие динамические системы большого обхвата и цикленного показателя над полем F характеристики больше или равно 2. Тогда отображения CD′nt = CDntCDnt, t — отлично от 0 и DA′nt = DAntDAnt, t — отлично от 0, согласно лемме 1, образуют симметрические динамические системы CD4(F ) и DA1(F ) большого обхвата и циклового показателя соответственно. Обозначим через Γ4(F ) и ΓA1(F ) семейства простых графов динамических систем CD4(F ) и DA1(F ). Конструкции леммы 2 и леммы 6, примененные к двудольным симметрическим динамическим системам CD(F ) и DA(F ), определяют новые двудольные симметрические динамические системы Γ5(F ) и ΓA2(F ) и Γ6(F ) и ΓA3(F ) соответственно. Теорема 6. Cемейства графов Γ4(Fq), charFq > 3, Γ5(Fq), Γ6(Fq), зависящие от неограниченного параметра q, являются семействами графов большого обхвата, суперли- нейного размера без реберно-транзитивной группы автоморфизмов. Cемейства графов ΓA1(Fq), charFq > 3, ΓA2(Fq), ΓA3(Fq) образуют новые суперли- нейные семейства простых графов с большим цикловым показателем. 1. Ding J., Gower J. E., Schmidt D. S. Multivariate public key cryptosystems. – Berlin: Springer, 2006. – 260 p. 2. Ustimenko V. Graphs with special arcs and cryptography // Acta Appl. Math. – 2002. – No 2. – P. 117–153. ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2013, №8 49 3. Ustimenko V. Maximality of affine group and hidden graph cryptosystems // J. Algebra Discrete Math. – 2005. – 1. – P. 133–150. 4. Устименко В.А. Об экстремальной теории графов и символьных вычислениях // Доп. НАН Украї- ни. – 2013. – № 2. – С. 42–49. 5. Bollobas B. Extremal graph theory. – London: Academic Press, 1978. – 320 p. 6. Margulis G.A. Explicit construction of graphs without short cycles and low density codes // Combinatori- ca. – 1982. – 2. – P. 71–78. 7. Lubotsky A., Philips R., Sarnak P. Ramanujan graphs // J. Comb. Theory. – 1989. – 115, Nо 2. – P. 62–89. 8. Lazebnik F., Ustimenko V.A., Woldar A. J. New series of dense graphs of high girth // Bull (New Series) of AMS. – 1995. – 32, Nо 1. – P. 73–79. 9. Ustimenko V. Linguistic Dynamical systems, graphs of large girth and cryptography // J. Math. Sci. – 2007. – 140, No 3. – P. 412–434. 10. Romanczuk U., Ustimenko V. On the key exchange with new cubical maps based on graphs // Annales UMCS Informatica. – 2011. – 4, No 11. – P. 11–19. 11. Polak M., Ustimenko V. On LDPC codes corresponding to infinite family of graphs A(n,K). – Procee- dings of Federated Conference on Computer Science and Informations Systems. – September 9–12, 2012. – Wroclaw, Poland. – P. 567–570. 12. Lazebnik F., Ustimenko V. Some algebraic constractions of dense graphs of large girth and of large size, DIMACS series // Discrete Mathematics and Theoret. Computer Science. – 1993. – 10. – P. 75–93. 13. Ustimenko V. Coordinatisation of trees and their quotients // Voronoj’s Impact on Modern Science. – 1998. – 2. – P. 125–152. 14. Ustimenko V. Algebraic groups and small world graphs of high girth // Albanian J. Math. – 2009. – 3, No 1. – P. 25–33. 15. Wroblewska A. On some applications of graph based public key // Ibid. – 2008. – 2, No 3. – P. 229–234. Поступило в редакцию 24.12.2012Институт телекоммуникаций и глобального информационного пространства НАН Украины, Киев Университет Марии Кюри–Склодовской, Люблин В.О. Устименко Про K-теорiю динамiчних систем, що вiдповiдають графам, та її застосування Визначаються деякi класи залежних вiд часу дискретних динамiчних систем. Означення мотивованi проблемами криптографiї, що базується на полiномiальних перетвореннях вiд багатьох змiнних, зокрема пошуком циклiчних груп полiномiальних перетворень необмеже- ного порядку, утворених перетвореннями степенi не бiльше, нiж 3. Iснування визначених аксiомами дискретних динамiчних систем доводиться методами конструктивної екстре- мальної теорiї графiв. Деякi динамiчнi системи визначаються за побудовою нових прикла- дiв сiмей графiв великого обхвату суперлiнiйного розмiру. Зокрема наводиться конструкцiя такої сiм’ї графiв без реберно транзитивної групи автоморфiзмiв. Побудовано також новi приклади сiмей графiв з великим цикловим показником. 50 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2013, №8 V.А. Ustimenko On the K-theory of graph-based dynamical systems and its application Special classes of time-dependent discrete dynamical systems are defined. The definitions are moti- vated by problems of multivariate cryptography, in particular, by the search for sequences of cyclic groups of polynomial transformations in the increasing number of variables of unbounded order formed by elements of a degree of at most 3. The existence of the dynamical systems defined by axioms is proven by methods of the constructive extremal graph theory. Some dynamical systems are defined by new explicit constructions of the families of simple graphs of large girth with superlinear size. We introduce the construction of such family without edge transitive automorphism group. Some new families of graphs with large cycle indicator are introduced. ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2013, №8 51

О K-теории динамических систем, соответствующих графам, и ее применении

Institution

Ähnliche Einträge