Reachability problem for continuous piece-wise-affine mappings of a circle having degree 2.pdf Непрерывные хаотические динамические системы привлекают к себе внимание со стороны теории алгоритмов и дискретной математики благодаря полезным аналогиям между их наблюдаемыми свойствами и свойствами, предъявляемым к криптографическим преобразователям информации [1]. В ряде публикаций встречаются исследования непрерывных хаотических систем в качестве прототипов для конечно-автоматных криптографических преобразователей информации [2]. В связи с этим, а также в силу принципиального противопоставления языка непрерывной и дискретной (компьютерной) математики является фундаментальной проблема развития интуитивных аналогий между хаотическими и криптографическими системами до уровня математических взаимосвязей. Отсюда возникает интерес к непрерывным системам с дискретным или непрерывным временем как к моделям вычислений. Это в первую очередь связано с вопросом: можно ли с помощью рассматриваемой непрерывной динамической системы моделировать дискретные системы, в частности универсальную машину Тьюринга? Проблема доказательства вычислительной универсальности тесно связана с проблемой достижимости. Обратим внимание на следующий важный момент при изучении хаотических систем в контексте моделирования с их помощью универсальных вычислений. В [3] приведено следующее замечание: поскольку реальную хаотическую систему физически невозможно установить с бесконечной точностью в заданное состояние, в частности в рациональную точку, то для таких систем идея брать в качестве основы для определения или доказательства вычислительной универсальности проблему достижимости из точки точки ("point-to-point reachability") имеет недостатки в силу чувствительности системы к начальным условиям, из-за которой любые возмущения могут разрушить вычисления. Однако в проблеме моделирования хаотическими системами универсальных вычислений в контексте криптографических задач речь идёт не о реальном физическом моделировании, а о компьютерном моделировании математических нелинейных моделей, и бесконечная точность начальных условий в виде рациональных чисел вполне имеет смысл. В качестве примера можно привести системы, аналогичные кусочно-аффинным, в которых вместе с аффинными отображениями используются функции , -\/x, x2, x3. Для таких кусочно-элементарных отображений было выделено [4] подмножество рациональных точек, орбиты которых остаются рациональными, благодаря чему доказана их вычислительная универсальность. Будем рассматривать непрерывные кусочно-аффинные отображения / : S1 ^ S1 степени 2 окружности S1 = R/Z. Все такие отображения топологически сопряжены с y = E2(x) = 2x (mod 1) и являются частными случаями кусочно-аффинных отображений с двумя интервалами. Для них доказывается алгоритмическая разрешимость проблемы достижимости, и, следовательно, такие системы не являются вычислительно универсальными. Утверждение практически тривиальное, но тем не менее важное по следующим причинам. Во-первых, проблема достижимости в кусочно-аффинных отображениях с двумя интервалами в общем случае является открытой проблемой [5]. Во-вторых, отображение E2 является классическим примером хаотической системы, в которой для почти всех точек x G S1 их орбиты демонстрируют хаотическое поведение. Однако ни одна точка из этих «почти всех» не представима на компьютере, поскольку они являются иррациональными числами, и наоборот, для всех известных в программировании типов данных система E2 ведёт себя регулярно. Математическая теорема о хаотичности системы E2 с точки зрения дискретной (компьютерной) математики является бессодержательной. И даже если под числом понимать алгоритм, потенциально его порождающий, то теорема о хаотичности E2 должна принять вид, раскрывающий тот факт, что сложность поведения системы заключается или скрыта не в самом отображении, а в сложности начальной точки x. Вместе с тем, как следует из доказательства ниже, любое другое топологически сопряжённое с E2 кусочно-аффинное отображение с рациональными коэффициентами показывает хаотическое поведение не только орбит иррациональных чисел, но и некоторого подмножества рациональных чисел. Рациональные числа представимы на компьютере, поэтому такие отображения уже интересны в контексте криптографического преобразования информации. Пусть X = R/Z П Q, f : X ^ X - непрерывное кусочно-аффинное отображение o,m n m n n , f (x) = - x при и 2= m степени 2, т.е. такое, что X = Xi U X2, Xi n ( m \ X x E X1, f (x) = -n- (x - m ) при x E X2, m, n E N. Обозначим через O (x) = n - m n = {fn (x) : n E N} орбиту точки x. Проблема достижимости из точки точки звучит так: существует ли алгоритм, определяющий по произвольным точкам xo, x1 E X принадлежность x1 E O(x0). Теорема 1. Проблема достижимости в непрерывных кусочно-аффинных отображениях f окружности в себя степени 2 алгоритмически разрешима. Доказательство. Числа m, n, n - m взаимно простые. Через |x|p обозначим p-адическую норму x. Если простое s E P не делит m и n - m, то f (x)|s ^ max{|x|s, 0}. n n Если p E P делит m, а q E P делит n - m, то - x > |x|p, - x = |x|q. Пусть |x|p > m p m q n m n m n и | x| q > -(x - m) Л n ' > |x|q, | x| p и, следова- > , тогда q nm -(x--) n m n p q тельно, |fi+1 (x)|p + |fi+1(x)|q > |fi(x)|p +1fг(x)|q, т.е. для проверки y E O(x) достаточно вычислить начальный отрезок орбиты длины i, такой, что |f l(x)|p +1fг(x) |q > |y|p + |y|q. m m \ > - и | x| q > p - не выполняется n n q nm p Пусть условие | x |fг(x)|q ^ |y|q для всех i, то последовательность O(x) зацикленная, причём с вычислимого места, поскольку существует лишь конечное множество чисел 0 ^ x ^ 1, таких, что |x|s ^ max {0, |y|r : r E P}, s E P. ■ Следствие 1. Если |x| m m, > - и | x| q > p - n n , то O(x) не зацикливается и рацио нальное x ведет себя в f как некоторое действительное число в E2.

Скачать электронную версию публикации