Проблема достижимости в непрерывных кусочно-аффинных отображениях окружности степени 2

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Таблица 1
n Б 6 т
Nl 12 26 Бб
Таблица 2
і n Б 6 т
2 236 2ЬЬ 278
4 — 283 2118
б — - 2: Ь С
& gt- 0 214Ь 2364 2868
Известно, что для нечётных n оценка Сидельникова точна на классе AB-функций, причём AB-функции существуют при всех нечётных n. Из табл. 2 видно, что оценка, полученная в теореме 2, применима только к значениям нелинейности, далёким от максимальных. Однако доказательство теоремы 2 конструктивно и может оказаться полезным, поскольку описывает метод построения функций с фиксированной нелинейностью.
ЛИТЕРАТУРА
1. Логачев О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. 2-е изд. М.: МЦНМО, 2012. 584с.
2. Панкратова И. А. Булевы функции в криптографии: учеб. пособие. Томск: Издательский Дом Томского государственного университета, 2014. 88 с.
3. Carlet C. Boolean functions for cryptography and error-correcting codes // Boolean Models and Methods in Mathematics, Computer Science, and Engeneering / eds. P. Hammer, Y. Crama. Cambridge Univ. Press, 2010. Ch. 8. P. 257−397. www. math. univ-paris13. fr/~carlet/
4. Сидельников В. М. О взаимной корреляции последовательностей // Проблемы кибернетики. 1971. Т. 24. С. 15−42.
УДК 510. 53
ПРОБЛЕМА ДОСТИЖИМОСТИ В НЕПРЕРЫВНЫХ КУСОЧНО-АФФИННЫХ ОТОБРАЖЕНИЯХ ОКРУЖНОСТИ
СТЕПЕНИ 2
А. Н. Курганский
На примере непрерывных кусочно-аффинных отображений окружности в себя степени два, для которых в работе доказывается алгоритмическая разрешимость проблемы достижимости из точки точки, обсуждаются некоторые алгоритмические аспекты моделирования дискретных систем непрерывными в контексте криптографического преобразования информации. Все такие кусочно-аффинные отображения топологически сопряжены с хаотическим отображением E2(x) = 2x (mod 1): R/Z ^ R/Z. Из доказательства основного результата работы следует, что любое другое непрерывное кусочно-аффинное отображение с рациональными коэффициентами и сопряжённое с Е2 показывает хаотическое поведение для некоторых рациональных чисел, что делает их интересными в задачах криптографического преобразования информации.
Ключевые слова: хаотические системы, криптография, кусочно-аффинные отображения, проблема достижимости.
Непрерывные хаотические динамические системы привлекают к себе внимание со стороны теории алгоритмов и дискретной математики благодаря полезным аналогиям между их наблюдаемыми свойствами и свойствами, предъявляемым к криптографическим преобразователям информации [1]. В ряде публикаций встречаются исследования непрерывных хаотических систем в качестве прототипов для конечно-автоматных криптографических преобразователей информации [2]. В связи с этим, а также в силу принципиального противопоставления языка непрерывной и дискретной (компьютерной) математики является фундаментальной проблема развития интуитивных аналогий между хаотическими и криптографическими системами до уровня математических взаимосвязей. Отсюда возникает интерес к непрерывным системам с дискретным или непрерывным временем как к моделям вычислений. Это в первую очередь связано с вопросом: можно ли с помощью рассматриваемой непрерывной динамической системы моделировать дискретные системы, в частности универсальную машину Тьюринга? Проблема доказательства вычислительной универсальности тесно связана с проблемой достижимости. Обратим внимание на следующий важный момент при изучении хаотических систем в контексте моделирования с их помощью универсальных вычислений. В [3] приведено следующее замечание: поскольку реальную хаотическую систему физически невозможно установить с бесконечной точностью в заданное состояние, в частности в рациональную точку, то для таких систем идея брать в качестве основы для определения или доказательства вычислительной универсальности проблему достижимости из точки точки («point-to-point reachability») имеет недостатки в силу чувствительности системы к начальным условиям, из-за которой любые возмущения могут разрушить вычисления. Однако в проблеме моделирования хаотическими системами универсальных вычислений в контексте криптографических задач речь идёт не о реальном физическом моделировании, а о компьютерном моделировании математических нелинейных моделей, и бесконечная точность начальных условий в виде рациональных чисел вполне имеет смысл. В качестве примера можно привести системы, аналогичные кусочно-аффинным, в которых вместе с аффинными отображениями используются функции 3Х, V#, x2, x3. Для таких кусочно-элементарных отображений было выделено [4] подмножество рациональных точек, орбиты которых остаются рациональными, благодаря чему доказана их вычислительная универсальность.
Будем рассматривать непрерывные кусочно-аффинные отображения f: S1 ^ S1 степени 2 окружности S1 = R/Z. Все такие отображения топологически сопряжены с y = E2(x) = 2x (mod 1) и являются частными случаями кусочно-аффинных отображений с двумя интервалами. Для них доказывается алгоритмическая разрешимость проблемы достижимости, и, следовательно, такие системы не являются вычислительно универсальными. Утверждение практически тривиальное, но тем не менее важное по следующим причинам. Во-первых, проблема достижимости в кусочно-аффинных отображениях с двумя интервалами в общем случае является открытой проблемой [5]. Во-вторых, отображение Е2 является классическим примером хаотической системы, в которой для почти всех точек x? S1 их орбиты демонстрируют хаотическое поведение. Однако ни одна точка из этих «почти всех» не представима на компьютере, поскольку они являются иррациональными числами, и наоборот, для всех известных в программировании типов данных система Е2 ведёт себя регулярно. Математическая теорема о хаотичности системы Е2 с точки зрения дискретной (компьютерной) ма-
тематики является бессодержательной. И даже если под числом понимать алгоритм, потенциально его порождающий, то теорема о хаотичности Е2 должна принять вид, раскрывающий тот факт, что сложность поведения системы заключается или скрыта не в самом отображении, а в сложности начальной точки х. Вместе с тем, как следует из доказательства ниже, любое другое топологически сопряжённое с Е2 кусочноаффинное отображение с рациональными коэффициентами показывает хаотическое поведение не только орбит иррациональных чисел, но и некоторого подмножества рациональных чисел. Рациональные числа представимы на компьютере, поэтому такие отображения уже интересны в контексте криптографического преобразования информации.
Пусть X = Ж/Ъ П Q, /: X ^ X — непрерывное кусочно-аффинное отображение
степени 2, т. е. такое, что X = X1 U X2, X1
n / m
o, m
n
и
X
2=
m n
n
, f (x) = - x при
m
х Є Хь / (х) = -П- (х — -) при х Є Х2, -, п Є N. Обозначим через О (ж) = п — т V п /
= {/п (х): п Є М} орбиту точки х. Проблема достижимости из точки точки звучит так: существует ли алгоритм, определяющий по произвольным точкам х0, х1 Є X принадлежность хі Є О (х0).
Теорема 1. Проблема достижимости в непрерывных кусочно-аффинных отображениях / окружности в себя степени 2 алгоритмически разрешима.
Доказательство. Числа -, п, п — - взаимно простые. Через |х|р обозначим
p-адическую норму x. Если простое s Є P не делит m и n — m, то
Если p Є P делит m, а q Є P делит n — m, то
n
-x m
& gt- |x|p,
n
-x m
f (x)|s ^ max{|x|s, 0}. = |x |q. Пусть |x |p & gt-
m m
& gt- n и | x| q & gt- p n, тогда q
n
nm
-(x — m)
-n
& gt- | x| q,
n
m
(x)
n m n
|x|p и, следова-
тельно, |/г+1 (ж)|р + |/г+1(ж)|д & gt- |/г (ж)|р + |/г (ж)|д, т. е. для проверки у € О (ж) достаточно вычислить начальный отрезок орбиты длины I, такой, что |/г (ж)|р + |/г (ж)|д & gt- |у|р + |у|д.
не выполняется. Если |/г (ж)|р ^ |у|р,
Пусть условие I |x|p & gt-
m
n
и | x| q & gt-
m
n
|/*(x)|q ^ |y|q для всех i, то последовательность O (x) зацикленная, причём с вычислимого места, поскольку существует лишь конечное множество чисел 0 ^ x ^ 1, таких, что |x|s ^ max {0, |y|r: r G P}, s G P. ¦
Следствие 1. Если |x|p & gt-
m
n
її m
и |x|q & gt- -, то O (x) не зацикливается и рацио-n
нальное x ведет себя в / как некоторое действительное число в E2.
ЛИТЕРАТУРА
1. Птицын Н. В. Приложение теории детерминированного хаоса в криптографии. М.: Изд-во МГТУ им. Н. Э. Баумана, 2002. 80с.
2. Savchenko A. Ya., Kovalev A.M., Kozlovskii V. A., and ScherbakV.F. Inverse dynamical systems in secure communication and its discrete analogs for information transfer // Proc. NDES. 2003. P. 112−116.
3. Delvenne J. -C. What is a universal computing machine? // Appl. Math. Comput. 2009. V. 215. No. 4. P. 1368−1374.
4. Kurganskyy O., Potapov I., and Sancho-Caparrini F. Reachability problems in low-dimensional iterative maps // Int. J. Found. Comput. Sci. 2008. No. 19(4). P. 935−951.
5. AsarinE., Mysore V., PnueliA., and Schneider G. Low dimensional hybrid systems — decidable, undecidable, don’t know // Inform. Comput. 2012. V. 211. P. 138−159.
q
q
p
p
q

ПоказатьСвернуть
Заполнить форму текущей работой