Search

Рассматривается задача построения биективных отображений B/l : (F2) n ^ (F2) n, B/, L(x) = (f (x),f (8(x)),...,f (8 n-i(x))), x G FT, набор координатных функций которых задаётся преобразованием 8 = 5l регистра сдвига большой длины n с функцией обратной связи L и нелинейной функцией выхода f от небольшого числа k аргументов (k ^ n). При этом биективность отображения B/ l равносильна ортогональности системы его координатных функций. В работе развивается метод, который сводит исходную задачу проверки биектив-ности отображения B/ l при больших значениях длины регистра n к проверке его биективности применительно к регистрам сдвига ограниченной длины n ^ no, что позволяет эффективно использовать для её решения вычислительную технику. На основе данного метода в работе построены новые бесконечные классы биективных отображений для случая нелинейной функции f, зависящей от k ^ 6 переменных. Ранее аналогичные результаты были известны для случая, когда функция f зависит от k = 3 переменных. Полученные результаты могут быть полезны при построении и обосновании статистических свойств датчиков случайных чисел на основе фильтрующих генераторов. При этом особый практический интерес представляет выбор пар (f, L), при которых одновременно обеспечивается биективность отображения B/,l и максимальность периода отображения 8l., The paper deals with the methods for constructing bijective mappings B/, L whose coordinate functions are defined by a great length shift register with a feedback function L(x 1, x 2,..., x n) and with an output (filtering) nonlinear function f (x 1, x 2,..., x k) depending on a small number k of its arguments (k ^ n). It is known that the orthogonality of the coordinate functions is equivalent to the bijectiveness of the mapping B/, L. A method developed in the paper reduces the problem of bijectiveness of B/, L for any n to the case of bounded n 0. The method allows to build new infinite classes of bijective mappings B/, L for nonlinear functions f depending on four, five or six variables. Earlier, similar results were known for a function f depending on three arguments. The results can be useful for constructing and proving statistical properties of random sequences generated on the basis of filter generators.

Работа посвящена вопросам численного построения композиционных моделей липшиц-ограниченных сюрьективных функций одного аргумента. Композиционные модели являются частным случаем функциональной аппроксимации, получаемым путём композиции функций из заданного множества. Доказывается NP-трудность задачи построения оптимальной композиционной модели при заданном множестве функций, используемых для построения модели, и определённой приближаемой функции. Рассматриваются различные алгоритмы нахождения приближённых композиционных моделей, часть из которых имеет полиномиальную сложность; оцениваются возможности применения данных подходов., The paper is devoted to the analysis of computational complexity of the synthesis of composite models for Lipschitz-bounded surjective functions of single variable. Composite models are some function approximation methods based on approximating via composition of functions taken from a given set. In this paper, it is proved that the problem of building strictly optimal composite model for a target functions via a given set of functions is NP-complete. Methods that are capable to build a near-optimal composition model are discussed. Some of these methods can be realized as algorithms with the polynomial computational complexity but they have a limited application.

Из результатов предыдущих работ, посвященных классу совершенно уравновешенных булевых функций (булевых функций без запрета), можно сделать вывод, что в данном классе особый интерес представляет подкласс функций без барьера. Ранее было доказано, что он не является пустым, тем не менее никаких оценок его мощности, отличных от тривиальных, предложено не было. В настоящей работе рассматриваются методы построения совершенно уравновешенных булевых функций без барьера, основанные на специального вида операции композиции булевых функций и на важных свойствах данной операции. Как следствие применения одного из методов получена нижняя оценка числа совершенно уравновешенных функций без барьера n переменных: 22n-3 -n+2., From the results of the previous papers dedicated to the set of perfectly balanced Boolean functions, one can conclude that the subset of Boolean functions without barriers is of prior interest in this set. Such a subset was considered previously, and the nonemptiness of it was proven, but no nontrivial estimations of the cardinality of this subset were found. In the current paper, some methods for constructing perfectly balanced Boolean functions without barriers are considered. They are based on the composition of Boolean functions of a special form and on certain important properties of such composition.

Теория дискретных автоматов на полурешетках является одним из значительных достижений научной школы прикладной дискретной математики (ПДМ) Томского государственного университета (ТГУ), представляя собой сравнительно новое научное направление на стыке математической кибернетики и общей алгебры, в рамках которого впервые удалось формализовать такие понятия, относящиеся к дискретным управляющим системам, как динамическое поведение, физическая реализуемость, адекватная модель и ее точность, и решить задачи логического проектирования таких систем в постановке, отражающей динамику поведения системы, возможность ее физической реализации на современной электронной базе и адекватность моделирования с любой наперед заданной точностью. Статья написана к 50-летию школы ПДМ ТГУ и является рефератом одноимённой монографии автора, вышедшей в Издательстве ТГУ в 1993 г. и ныне практически не доступной. В ней отражены почти все основные результаты теории дискретных автоматов на полурешётках, полученные к тому времени., The theory of discrete automata on semilattices is one of the important achivements of the Tomsk State University scientific School on applied discrete mathematics. It is a comparatively young branch of the science connecting mathematical cybernetics and abstract algeabras. Inside this branch, we have firstly succeeded in formal defining such notions related to the discrete control systems as the dynamic behaviour, the hardware realizability, the adequate model and its accuracy, and also in solving the problems of logical synthesizing such systems with a given dynamic behaviour and with the possibility of hardware realization at the transistor level and of modelling their dynamic behaviour adequately with any given accuracy. The paper is presented on behalf of 50 years jubilee of the School. It is an extended abstract of the same name monograph by the author issued at TSU in 1993 and now being out of access. All the main results obtained in the theory of discrete automata up to that time are presented in the paper.

Работа является продолжением серии статей, посвященных обращению дискретных функций из класса, имеющего пересечения с различными областями кибернетики. В данный класс, в частности, попадают функции, используемые в современных криптосистемах в качестве шифрующих преобразований. В настоящей работе обсуждаются некоторые характерные моменты, касающиеся решения задач обращения рассматриваемых функций на многопроцессорных вычислительных системах., This paper is a continuation of a series of papers devoted to problems of reversing of discrete functions belonging to class that has intersections with different areas of mathematical cybernetics. In particular the functions used in modern cryptosystems as ciphering transformations belong to the given class. In the paper some distinctive moments concerning the solving of considered functions reversing problems on multiprocessing computing systems are discussed

Представлены клеточно-автоматные стохастические модели рекомбинации электронов и дырок в неоднородном полупроводнике в двумерном и трёхмерном случаях. Исследована кинетика процесса рекомбинации электронов и дырок в режимах чистой диффузии, диффузии с туннелированием и диффузии частиц при наличии рекомбинационных центров. Изучен характер электронно-дырочных пространственных корреляций, полученных с помощью клеточно-автоматной модели, и связанного с этим формирования сегрегации в 2Dи ЭБ-полупроводниках. Путём численного моделирования вычислены и исследованы основные характеристики процесса рекомбинации: плотности частиц и интенсивность фотолюминесценции. Кроме того, проанализирована зависимость времени выполнения параллельных программ, реализующих клеточно-автоматные модели рекомбинации в двумерном и трёхмерном случаях, от значений таких модельных параметров, как начальная плотность электронно-дырочных пар и размер моделируемой области., Stochastic models of electron-hole recombination in 2D and 3D inhomogeneous semiconductors based on a discrete cellular automata approach are presented in the paper. These models are derived from a Monte Carlo algorithm based on spatially inhomoge-neous nonlinear Smoluchowski equations with the random initial distribution density used to simulate the annihilation of spatially separate electrons and holes in a disordered semiconductor characterized by the heterogeneous properties of the material. Recombination kinetics in different regimes such as a pure diffusion, diffusion in vicinity of tunneling and diffusion in the presence of recombination centers are investigated by a cellular automata simulation. Statistical characteristics of the recombination process (particle concentrations and the radiative intensity) obtained by the cellular automaton models are compared with the theoretically known asymptotics derived for a pure diffusion case. The results obtained for a two-dimensional domain correspond to the theoretical asymptotics, whereas in three-dimensional case, they differ from the exact asymptotics. It is found out by simulations that a spatial electron and hole separation (segregation) occurs under certain conditions on the diffusion and tunneling rates. The electron-hole spatial segregation in 2D and 3D semiconductors is analyzed by using the probability density of the electron-hole separation. In addition, the execution time of the codes implementing the cellular automaton model of the recombination in 2D and 3D semiconductors is studied in dependence on the number of simulated electron-hole pairs and the size of the semiconductor domain. It is shown that the execution time for semiconductors of dimension d is proportional to a polynomial of order d.

Приведена конструкция одного из Т-неприводимых расширений для ориентированных сверхстройных деревьев., A digraph H = (W, в) is called a T-irreducible extension of a digraph G = (V, a), if | W| = | V| + 1, there is a vertex w e W such that H w = G, G is embedded into every subgraph H u for u = w, and no arc can be deleted from в without disturbing these properties. T-irreducible graph extensions are widely applied to synthesizing fault tolerant computing networks. In the paper, it is shown that, for any directed starlike tree G = (V, a) consisting of some directed chains Pi = (v0, Vj,i,..., Vi,ni), i = 1,..., k, beginning in the root (vo) of the tree, and having no other shared vertices, the digraph H = (V U {w},e), where a С в, (v0,w) e в, (w,vi,ni-1) e в for all i, 0 ^ i ^ k 1, ni > 2 ^ ((w, Vi,ni-2) e в, 0 < i < k 1, (w, Vi,ni-1) e в, 0 < i < k 1), n > 3 ^ ^ ((w, vi,j), (vi,j, w) e в, 0 ^ i ^ k 1,1 ^ j ^ ni 3), is a T-irreducible extension of G.

В развитие матрично-графового подхода к исследованию перемешивающих свойств итеративных преобразований С.Н. Кяжиным, В.М. Фомичевым были введены понятия локальной примитивности и локального экспонента орграфа, обобщающие известные понятия примитивности и экспонента и позволяющие расширить область приложений, и получены универсальный критерий i х j-прими-тивности и универсальная оценка i х j-экспонента орграфа. Однако применение данных результатов не всегда удобно, так как затруднено общностью математической модели. В данной работе для различных классов орграфов, определяемых взаимным расположением компонент сильной связности и их строением, получены условия i х j-примитивности и оценки (в ряде случаев точные значения) i х j-экспонента, улучшающие универсальную оценку. Условия локальной примитивности и величина оценок локальных экспонентов определяются свойствами множества длин путей из i в j в перемешивающем орграфе, а также длинами контуров, содержащихся в компонентах сильной связности, через которые проходят данные пути. Полученные результаты значительно упрощают для исследователя распознавание локальной примитивности и получение оценок локальных экспонентов конкретных перемешивающих орграфов преобразований, возникающих, в том числе, в криптографических приложениях., For vertices i and j in a digraph Г, the last is called i х j-primitive if for some 7 e N and any integer t ^ 7, there is a path of length t from i to j in Г. The least such 7 is called i х j-exponent of Г and is noted as i х j-expT. Because of mathematical model generality, it is not always easy to use the universal criterion of digraph i х j-primitiveness and the universal estimation of digraph i х j-exponent obtained by S. N. Kyazhin and V. M. Fomichev. In the paper, some criteria of digraph i x j-primitiveness and an estimations of digraph i x j-exponent in two special cases are given. For vertices i and j being achievable from each other, that is, belonging to a strongly connected component U, the graph Г is i x j-primitive if and only if U is primitive. If Г is i x j-primitive, then i x j-expT < u(r 1) + G(C) + p(i, U7(C)) + 0(t/(C), j) r E (1s + (s 2)As) + 1, where u is the number of vertices in U; C is a primitive s=1 system of k directed cycles in U of lengths 11,..., ; U((C) is the set of vertices of digraph U(C) = (J C which contains r connected components, r ^ k; As is the sum с ес of lengths of directed cycles in the s-th connected component in U((C), s = 1,..., r; G(C) = g(11,..., Zfc) is Frobenius number; p(i, J) is the least distance between i and a subset J of vertices; 0(J, j) is the least distance between J and j. For i not being achievable from j, the graph Г is i x j-primitive if and only if for some d G N and subset P of the set of paths from i to j, the set spc P is d-full, and for some a G Z, spc W(i, j) 5 spc P + Z(a, d), where spc W(i, j) is the set of path lengths from i to j; spc P is the set of path lengths in P; d-full set is the complete residue system modulo d; Z(a, d) = {z G Z : z = a + kd, k G N}; spc P + Z(a, d) = {ж + y : (ж, y) G G spcP x Z(a, d)}. If Г is i x j-primitive, then i x j-expT ^ £d(spcP) + a + d, where £d(spcP) is the minimal number in N such that, for all a G {{d(spcP),{d(spcP) + 1,..., £d(spc P) + d 1}, there is b G spc P that b ^ a and b is congruent to a modulo d. By means of the result the derivation of i x j-primitiveness conditions and i x j -exponent estimations for various classes of digraphs is reduced to the estimation of appropriate numbers a and d. The results simplify local primitiveness recognition for concrete mixing digraphs of cryptographic transformations.

Ввиду высокой сложности современных сетей и стохастического характера происходящих в них процессов, основным инструментом анализа инфокоммуникационных систем является имитационное моделирование. При анализе функционирования беспроводных технологий (беспроводных сенсорных сетей, ad hoc-сетей, когнитивного радио и др.) в качестве математической модели топологии сети часто используются случайные геометрические графы, в частности UDG-графы. Следовательно, вопрос о разработке эффективного генератора таких графов является актуальным. Описан метод генерации псевдослучайных геометрических графов с наперёд заданными свойствами. Предложенный генератор превосходит существующие аналоги как по производительности, так и по качеству сгенерированных топологий., Due to the high complexity of modern networks as well as the stochastic nature of network processes, the simulation becomes the main tool for communication systems analysis. In simulation studies of wireless technologies (wireless sensor networks, ad hoc-networks, cognitive radio, Internet of Things etc.), the random geometric graph (RGG) is the most commonly used mathematical model of network topology. This graph is constructed by randomly placing N vertices in some metric space (according to a specified probability distribution), where each pair of vertices is connected by an edge iff the distance between them is smaller than a predetermined value (radius). Network simulation technique typically uses the rectangular region and the uniform distribution for vertices coordinates. Thus, the research and development of efficient RGG generators is an important problem. The paper describes a method for the fast generation of pseudo-random geometric graphs with the prescribed properties: 1) the vertices are uniformly distributed in the network region; 2) the region is fully covered by circles of a given radius centered at the vertices of the graph; 3) the graph is connected. To increase the generator performance, we construct an auxiliary grid covering the region. To guarantee the full coverage and graph connectivity, every cell of the grid contains at least one vertex. The corresponding cell size depends on the given transmission radius in a wireless network. The core idea of the proposed algorithm is to apply the procedure of edges construction only for nodes in adjacent cells. It allows to avoid unnecessary calculations. In the first stage of the algorithm, one vertex is randomly placed in each cell. To define the vertex coordinates, one of the standard generators of pseudo-random values for uniform distribution is used here and below. In the second part of the algorithm, the remaining vertices are randomly distributed over the region. The edges construction procedure based on adjacent cells is applied as well. The algorithm can be easily adapted for non-squared region. Experiments show that the proposed method, when compared to the traditional algorithm, drastically reduces the generation time (up to 10 times). The proposed generator is better than the existing analogues both in performance and reality of generated topologies.

Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В данной работе изучается генерическая сложность проблемы общезначимости (тождественной истинности) булевых формул. Доказывается, что эта проблема неразрешима за полиномиальное время на любом полиномиальном строго генерическом множестве формул при условии её трудноразрешимости в худшем случае., Generic-case approach to algorithmic problems was suggested by Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. In this paper, we consider generic complexity of the validity problem for Boolean formulas and prove that this problem is generically hard if it is hard in the worst case.

Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. Изучается генерическая сложность классической проблемы дискретного логарифма в полях GF(p), где p простое. Доказывается, что её естественная подпробле-ма генерически трудноразрешима (то есть трудна для почти всех входов) при условии, что проблема дискретного логарифма трудноразрешима в классическом смысле., Generic-case approach to algorithmic problems was suggested by Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies behaviour of an algorithm on typical (almost all) inputs and ignores the rest of inputs. Many classical undecidable or hard algorithmic problems become feasible in the generic case. But there are gener-ically hard problems. In this paper, we consider generic complexity of the classical discrete logarithm problem. We fit this problem in the frameworks of generic complexity and prove that its natural subproblem is generically hard provided that the discrete logarithm problem is hard in the worst case.

Предложено задание подстановок алгоритмов блочного шифрования Магма и 2-ГОСТ через линейные комбинации алгебраических пороговых функций (АПФ). Для этого приведены полученные автором результаты представимости геометрических типов булевых функций от четырёх переменных через АПФ., The paper deals with the implementation of substitutions in Magma and 2-GOST block cipher algorithms by algebraic threshold functions (ATF). For this purpose, the representations of all the geometric types of Boolean functions in 4 variables by ATF are given.

Изучаются матроиды конечного ранга и конечномерные комбинаторные геометрии. Предложено определение матроида в терминах поверхностей различного ранга, удовлетворяющих заданным аксиомам инцидентности. Доказана эквивалентность этого определения определению матроида в терминах независимых множеств. В случае обыкновенного матроида его характеризация представляет собой эквивалентное определение комбинаторной геометрии., In the paper, the matroids of finite rank and finite-dimensional combinatorial geometries are studied. A definition of a matroid in terms of different rank surfaces satisfying some incidence axioms is proposed. This definition is equivalent to the definition of a matroid in terms of independent sets. In case of a simple matroid its characterization can be viewed as an equivalent definition of a combinatorial geometry.

In order to protect both data confidentiality and legality, a concept of a watermarking cipher (also called a w-cipher) is defined. The main idea of this cjncept is as follows: the transformation of a plaintext x by the composition of encryption and decryption operations using some encryption and decryption keys yields a proper text x/ containing a unique watermark w. The encryption and decryption keys in the w-cipher are connected with each other and with the given watermark w in some way. In contrast with the ciphers usually studied in cryptography, the encryption function in a w-cipher is not compulsorily invertible. Thus in fact w-ciphers are not ciphers in the known sense of the word, but the ciphers are w-ciphers of a certain partial type, and all terms, notions and notations related to ciphers are quite applicable to w-ciphers. It is shown how data watermarking can be performed by applying a w-cipher in such a way that the concealment of a watermark into a plaintext is accomplished by this w-cipher either in the encryption or in the decryption processes. Some examples of w-ciphers constructed on the basis of symmetric stream ciphers are presented in the paper.

Исследуется сложность реализации булевых функций и систем булевых функций схемами в базисе, состоящем из элементов двух сортов. Элементами первого сорта являются произвольные монотонные функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго сорта, каждой такой функции приписан положительный вес. Для случая, когда отрицание является единственным элементом второго сорта, А. А. Марковым в 1957 г. показано, что минимальное число немонотонных элементов, достаточное для реализации функции f, равно \log 2(d(f) + 1)], где d(f) максимальное число переключений значений функции f с 1 на 0 (максимум берётся по всем возрастающим цепям наборов значений переменных). В работе установлено, что в общем случае сложность реализации булевой функции f равна P\log2(d(f ) + 1)] 0(1), где р минимальный вес немонотонных элементов базиса. Получено также аналогичное обобщение классического результата А. А. Маркова о сложности реализации систем булевых функций., Complexity of Boolean functions and Boolean function systems realization in a base consisting of all monotone functions and a finite number of non-monotone functions is researched. The weight of any monotone function in the base is supposed to be 0, the weight of non-monotone function in it is positive. A. A. Markov studied special case of this base, where the non-monotone part consisted of the negation function. He showed that the minimum number of negation elements which are needed to realize an arbitrary function / equals |"log2(d(f) + 1)]. Here d(f) is the maximum number of value changes from 1 to 0 over all increasing chains of arguments tuples. The aim of this paper is to prove that the complexity of a Boolean function / realization equals Pl~log2(d(f) + 1)] O(1), where p is the minimum weight of non-monotone elements in the base. Similar generalization of the classical Markov's result concerning the realization of Boolean function systems is obtained too.

Исследуются неэндоморфные совершенные по Шеннону (абсолютно стойкие к атаке по шифртексту) шифры в случае, когда мощность множества шифрве-личин равна двум. В терминах линейной алгебры на основе теоремы Биркго-фа о классификации дважды стохастических матриц описано множество (полиэдр) матриц вероятностей ключей неэндоморфных совершенных шифров с двумя шифрвеличинами. Построено множество возможных значений априорных вероятностей шифробозначений данных шифров., This paper deals with non-endomorphic perfect (according to Shannon) ciphers, which are absolutely immune against the ciphertext-only attacks in the case when plaintext alphabet consists of two elements. Matrices of probabilities of cipher keys are described in terms of linear algebra on the basis of Birkhoff's theorem (about the classification of doubly stochastic matrices). The set of possible values of a priori probabilities for elements in ciphertext alphabet of a perfect cipher is constructed.

Описывается двухслойный тоталистический клеточный автомат, позволяющий генерировать компьютерное представление пористых сред со сложной неоднородной морфологией. Двухслойный клеточный автомат представляет собой композицию двух клеточных автоматов: тоталистического (первого слоя) и асинхронного (второго слоя). Наличие второго слоя даёт возможность формировать сложные неоднородные структуры, похожие на наблюдаемые в природе. Для анализа формируемых структур в процессе моделирования вычисляются численные характеристики: пористость, перколяция, процент единичных (заполненных) клеток, на основании которых может быть выбран пористый материал с нужной морфологией., In the paper, two-layer totalistic cellular automaton allowing to generate porous materials computer representation is presented. Two-layer cellular automaton is constructed as a parallel composition of a totalistic cellular automaton and an asynchronous cellular automaton. The second layer gives an opportunity to form complex inhomogeneous structures similar to a patterns emerging in natural phenomena. The investigation aims to create a method for porous media morphology synthesis according to a given set of properties such as porosity, percolation, density, etc. Two-layer totalistic cellular automaton allows to obtain a set of patterns representing different porous media morphology. In addition, a porous medium characteristics such as percolation degree, porosity, the number of connected components are calculated and can be used for the analysis and selection of materials with necessary morphology.

Пусть R = GR(q n,p n) кольцо Галуа мощности q n и характеристики p n, где q = p m, и Gf,R граф биективного преобразования кольца R, задаваемого полиномом f (x) G R[x]. Если n > 1 или q = p, то граф Gf,R не может быть циклом. Максимальная длина цикла в таком графе не превосходит q(q-1)p n-2. Полиномы, для которых граф Gf,R содержит цикл указанной длины, назовём полиномами с максимальной длиной цикла. Для таких полиномов предложен алгоритм проверки, лежит ли заданный элемент кольца на каком-либо цикле длины q(q 1)p n-2 графа Gf,R. Алгоритм требует выполнения порядка dq операций умножения и порядка dq операций сложения в кольце R, d = degf(x), d < |R|. Предложен также алгоритм построения системы представителей различных циклов графа Gf,R, имеющих длину q(q 1)p n-2. Алгоритм построения представителей всех циклов длины q(q 1)p n-2 требует выполнения порядка d(q 1)q n-1 операций умножения и порядка d(q 1)q n-1 операций сложения в кольце R. Алгоритм построения представителей M различных циклов длины q(q 1)p n-2 требует выполнения порядка d(q 1)q k-1 операций умножения и порядка d(q 1)q k-1 операций сложения в кольце R, где k = [log q/ p M] + 1., For a polynomial mapping over the Galois ring R = GR(q n,p n) with the cardinality q n and characteristic p n, the maximal length of a cycle equals q(q 1)p n-2. In this paper, we present an algorithm for constructing the system of representatives of all maximal length cycles and an algorithm for constructing an element in a cycle of maximal length for a polynomial substitution f G R[x]. The complexity of the first algorithm equals d(q 1)q n-1 multiplication operations and d(q 1)q n-1 addition operations in R, the complexity of the second algorithm equals dq multiplication operations and dq addition operations in R where d = deg(f).

Найдены периоды разрядных последовательностей, полученных из r-ичного разложения знаков линейной рекуррентной последовательности максимального периода над конечным простым полем для произвольного натурального r ^ 3., In the paper, for any integer r ^ 3, the periods of digit-position sequences obtained from r-ary representation of elements in a linear recurrent sequence of the maximal period over prime field are computed.

Работа продолжает исследование функциональной структуры булевых функций, задаваемых действительными линейными неравенствами. Рассматриваются булевы функции, определяемые одним нелинейным неравенством второй степени. Многочлены второй степени среди всех нелинейных многочленов обладают наименьшим размером задания, т. е. свойством, существенным в ряде прикладных задач. Доказаны три критерия функциональной разделимости для булевых квадратичных пороговых функций. Второй критерий не требует анализа табличного задания функции и формулируется в терминах пороговой структуры., Threshold functions provide a simple but fundamental model for many questions investigated in image recognition, artificial neural networks and many other areas. In this paper, the results in Boolean threshold function decomposition are advanced to Boolean functions represented by one quadratic inequality. Quadratic polynomials are the most compact non-linear polynomials and this property sometimes is quite important. We prove three criteria for non-trivial decomposition of quadratic Boolean threshold functions. One of them can be applied without analysis of truth table and only uses the threshold structure parameters.

Получена нижняя оценка показателя нелинейности подстановок поля F2", ограничения которых на смежные классы группы F^n по её подгруппе H, |H| = l, 1 · r = 2 n 1, являются отображениями вида x ^ Ajx, Aj e Fgn, j = 0,...,r 1. В случаях r = 3, 5 найден спектр значений показателя нелинейности подстановок данного вида., In this paper, we give a lower bound on the nonlinearity of permutations on a field F 2n with restrictions to cosets of H in F2n, H < Fgn, IH| = l, l · r = 2 n 1, being the maps x ^ Ajx, Aj e F2n, j = 0,..., r 1. Nonlinearity spectra of this permutations are found in the cases r = 3, 5.

Сдвиг научного интереса от физических явлений, подчиняющихся законам термодинамики, к нелинейным диссипативным процессам, содержащим химические и биологические превращения, привёл к аналогичному повороту в математическом моделировании: от решения дифференциальных уравнений к прямому дискретному стохастическому моделированию. Математическим фундаментом дискретного моделирования является асинхронный клеточный автомат стохастический аналог клеточного автомата фон Неймана. Систематической методологии построения асинхронного клеточного автомата, моделирующего процессы, состоящие из многих действий, совместно преобразующих общее дискретное пространство, пока не существует. Нет ответа на вопрос, насколько и чем различаются результаты моделирования при разных способах организации (режимах) взаимодействий локальных операторов, составляющих сложный процесс. В работе делается попытка ответить на этот вопрос путём проведения серии вычислительных экспериментов по моделированию трёх типовых реакционно-диффузионных процессов при разных асинхронных режимах и сравнительного анализа их эволюций. Результат состоит в том, что качественный характер процессов не зависит от способа композиции, а количественные различия могут быть скорректированы., The shift of scientific interest from physical phenomena obeying laws of thermodynamics towards nonlinear dissipative processes containing chemical and biological transformations stimulates a similar turn in mathematical modeling: from differential equation solution to direct and stochastic simulation. A foundation for discrete simulation is the asynchronous cellular automaton a stochastic analogue of von-Neumann''s cellular automaton. For the time being, there is no systematic methodology for constructing asynchronous cellular automata simulating processes composed of many actions transforming a common discrete space. It is not known, how different are simulation results obtained by different ways of composing simple operations for organizing a complex computational process. In the paper, an attempt is made to answer this question by means of performing a series of simulation of three typical reaction-diffusion processes with different asynchronous modes of functioning, and comparative analysis of their evolutions and invariants. The obtained result shows that qualitative character of the process under simulation does not depend on the composition mode, and quantitative differences may be corrected.

Минимальные рёберные расширения графов можно рассматривать как модель оптимальной рёберной отказоустойчивой реализации некоторой системы. Работа посвящена верхней оценке количества дополнительных рёбер минимальных рёберных 1-расширений для графов специального вида сверхстройных деревьев. Приводятся две схемы построения рёберного 1-расширения для сверхстройного дерева произвольного вида и соответствующий алгоритм на основе этих схем., Minimal edge extension of graphs can be regarded as a model of optimal edge fault tolerant implementation of a system. This paper is about an upper bound for the number of additional edges in minimal 1-edge extensions for graphs of a special class starlike trees. Two schemes for constructing 1-edge extensions for any kind starlike trees and an algorithm based on these schemes are proposed.

Исследуются задачи дискретной оптимизации с логическими ограничениями на основе моделей целочисленного линейного программирования и метода регулярных разбиений. Получена верхняя оценка мощности произвольного L-комплекса многогранника задачи 2-выполнимости, использование которой позволяет более эффективно решать некоторые прикладные задачи проектирования сложных изделий с помощью рассматриваемых подходов., In the paper, we analize discrete optimization problems with logical constraints based on integer linear programming models and L-partition approach. We obtain an upper bound for the power of any L-complex of the 2-SAT polytope. The use of this evaluation allows to solve some applied problems of designing complex products by these approaches much more efficiently.

Работа посвящена разработке математического метода проведения соревнований Capture the Flag, основанных на решении заданий при угрозе DDoS-атак на сервер организаторов. Предлагается распределённый протокол проведения соревнований, который перекладывает часть функций организаторов на участников. Участники соревнования конкурируют друг с другом и не хотят помогать командам-соперникам, поэтому к защищённости протокола предъявляются высокие требования. Получен протокол, удовлетворяющий поставленным требованиям, рассмотрены атаки, исследована устойчивость протокола к ним, предложены модификации. Описаны возможные направления дальнейших исследований в данной области., The paper is devoted to mathematical method of holding task-based CTF contests under threat of DDoS attack against organizers'' servers. For the purpose, a decentralized protocol is proposed where a part of organizer role is distributed among participants. There are some important security requirements to the protocol due to the competitive nature of CTF contests. The result protocol meets these requirements. Its stability against considered attacks is researched. Directions of further research are described.

Рассматривается линейная нотация полный инвариант графов, который позиционируется как альтернатива для описания конечных графов. Данный инвариант строится с помощью алгоритма, близкого к алгоритму поиска канонических форм графов. Хранение линейной нотации в памяти вместо обычного графа позволяет проще решать две основные задачи: построение иллюстраций для графов и сравнение графов на изоморфизм. Для полученного описания дополнительно демонстрируется переносимость таких понятий теории графов, как раскраски и пути, непосредственно на линейные нотации., In this paper, we consider the graph linear notation a complete graph invariant, which is positioned as an alternative to description of finite graphs. This invariant is constructed using an algorithm which is close to the search algorithm for canonical forms of graphs. The storage in a memory of a graph linear notation instead of the graph itself simplifies the procedures for constructing graph illustrations and testing two graphs for isomorphism. We demonstrate how the main graph theory concepts including colouring and graph paths can be defined in terms of graph linear notations.

Рассматривается инвариант W(G) связных неориентированных графов G, равный сумме расстояний между всеми парами вершин графа G. Предлагается эффективный алгоритм расчёта матрицы расстояний и индекса Винера максимальных внешнеплоских графов с большим количеством вершин. Временная сложность алгоритма O(n 2). Алгоритм удобен как для ручного расчёта индекса Винера небольших графов, так и для расчёта индекса Винера графов, сгенерированных компьютерной программой., Wiener index W(G) of a connected undirected graph G equals the sum of distances between all pairs of vertices in G. In this paper, an effective algorithm for calculating Wiener index of maximal outerplane graphs with a big number n of vertices is offered. The time complexity of the algorithm is O(n 2). The algorithm is fit for manual calculation of Wiener index of small graphs, as well as for its calculation for computer generated graphs.

Рассматривается модель управления доступом MS SQL Server, построенная на основе СУБД ДП-модели. Для учёта особенностей управления доступом в СУБД MS SQL Server 2012 в модель добавлены роли, права доступа к учётным записям пользователей и ролям, цепочки владения, а также возможность олицетворения пользователей и активации триггеров и процедур от имени заданных учётных записей пользователей. Доказывается утверждение об эквивалентности возможности выполнения произвольного SQL-кода от имени заданной учётной записи и возможности получения к ней права олицетворения. Обосновываются необходимые и достаточные условия получения и предоставления прав доступа к сущностям при отсутствии кооперации между субъект-сессиями., In this paper, the MS SQL Server access control model, based on the DBMS DP-model, is introduced. For taking into account the access control features of Microsoft SQL Server, the model includes roles, permissions to user accounts and roles, ownership chaining, user impersonation and activating procedures and triggers on behalf of the specified user accounts. The statement of the equivalence of the possibilities to execute arbitrary SQL-code on behalf of a specified account and to obtain the right of its impersonation is proved. Some necessary and sufficient conditions for obtaining and granting access rights by entities in the absence of cooperation between sessions are proved.

Рассматривается сеть передачи данных с линейным кодированием в узлах. Предполагается, что наблюдатель подслушивает данные, передаваемые по некоторым рёбрам сети, а информация, поступающая на вход сети, защищается с помощью кодового зашумления. В рамках этой модели решается задача анализа стойкости кодового зашумления при многократном подслушивании в сети данных, соответствующих одному информационному слову. Получена формула вычисления стойкости после l перехватов для l ^ 1. Для одной сети в качестве примера рассмотрено применение полученной формулы при анализе стойкости кодового за-шумления, основанного на коде Рида Маллера R(1, 3)., A communication network with linear coding in the nodes is considered. It is assumed that an adversary can overhear data transmitted through some edges of the network and code noising is used to protect incoming information. In the paper, the security of code noising against multiple eavesdropping the network data is analysed. A formula for calculating the security against I interceptions of information words is obtained. The formula is applied to the security analysis of code noising based on Reed Muller code R(1, 3).

Строится FP//LINSPACE алгоритмический аналог вещественной W-функции Ламберта W 0(x) на отрезке [-(re) -1, (re) -1] FP//LINSPACE алгоритмических вещественных чисел, где r рациональное, r > 4/3 (в качестве r можно брать любое рациональное с таким условием). Для построения алгоритмического аналога вещественной W-функции Ламберта W 0(x) предлагается алгоритм WLE расчёта двоично-рациональных приближений данной функции на отрезке [-(re) -1, (re) -1] с полиномиальной временной и линейной емкостной сложностью на машине Тьюринга. Алгоритм WLE строится на основе разложения в ряд Тейлора данной функции, при этом показывается и используется в алгоритме линейная сходимость ряда Тейлора W-функции Ламберта W 0(x) на отрезке [-(re) -1, (re) -1]., In the paper, we construct FP//LINSPACE algorithmic analog of real Lambert W-function W 0(x) on segment [-(re) -1, (re) -1] of FP//LINSPACE algorithmic real numbers, where r is a rational number, r > 4/3 (any such rational number is suitable). To construct algorithmic analog of real Lambert W-function W 0(x), we consider algorithm WLE for the evaluation of dyadic rational approximations of the function on segment [-(re) -1, (re) -1] on Turing machine using polynomial time and linear space. Algorithm WLE is based on the Taylor series expansion of the function; it is shown that the Taylor series of real Lambert W-function W 0(x) on segment [-(re) -1, (re) -1] converges linearly. This fact is used in the algorithm.

Приведено доказательство формул для вычисления асимптотических констант вероятности несвязности планарного взвешенного графа с высоконадёжными рёбрами., In this paper, formulas for the calculation of asymptotic constants in the disconnection probability for a weighted planar graph with high reliable edges are proved.

Рассмотрена одна из двух основных составляющих сжатия видеоинформации в новом стандарте H.265/HEVC внутрикадровое кодирование. Проведена серия экспериментов, результаты которых позволяют оценить практическую эффективность используемых в HEVC решений., In this paper, the Intra Prediction part of the newest video compression standard H.265/HEVC is experimentally tested for the effectiveness of its application to video sequences of different types.

Приводится пример континуального семейства в-замкнутых классов функций многозначной логики, содержащих только функции, принимающие не более трёх значений, где оператор в-замыкания определён на основе кодирования функций многозначной логики в двоичной системе счисления. Доказываются некоторые свойства данного семейства классов., The paper studies в-closed classes of the multivalued logic functions, where the в-closure operator is defined on the basis of the functions encoding in the binary number system. A continual set of в-closed classes, which contain only functions taking no more than three values, is given and some of its properties are proved.

Рассматривается задача о максимально достижимом числе вершин при заданных размерности и диаметре неориентированных циркулянтных графов. В 1994 г. Ф.П. Муга доказал теорему о том, что это число является нечётным при любых размерностях и диаметрах циркулянтного графа, что подтверждается для одно-, двухи трёхмерных циркулянтов. В настоящей работе доказано, что найденное доказательство теоремы некорректно. На основании новых данных скорректирована таблица максимально достижимых порядков циркулянтов размерности четыре., For undirected circulant networks, the problem of the maximal reachable number of nodes under given dimension and diameter of a graph is considered. In 1994, F. P. Muga proved the theorem that this number is odd for any dimension and any diameter of a circulant graph. Later, R. R. Lewis has presented a counterexample of four-dimensional circulant. In the present paper, a mistake in the proof of this theorem is pointed. Based on the new results, the early presented table of the maximal reachable orders of four-dimensional circulants is corrected.

Строится алгоритм FLE быстрого вычисления логарифмической функции ln(1 + ж) вещественного аргумента на полуинтервале [2 -5,1 — 2 -5) на машине Шёнхаге с оракульной функцией и даётся верхняя оценка его временной и емкостной сложности. Алгоритм FLE строится на основе разложения в ряд Тейлора по аналогии с алгоритмом быстрого вычисления экспоненты FEE, при этом дополнительно строится модифицированный алгоритм двоичного деления ModifBinSplit для гипергеометрических рядов. Для алгоритмов ModifBinSplit и FLE показывается квазилинейность по времени и линейность по памяти при вычислении на машине Шёнхаге, то есть принадлежность классу Sch(FQLIN-TIME//LIN-SPACE). Для расчёта логарифмической функции на произвольном промежутке используется мультипликативная редукция интервала., In the present paper, an algorithm FLE is constructed for the fast evaluation of the real logarithmic function ln(1 + x) on interval [2 -5,1 — 2 -5) on Schonhage machine. An upper bound of the time and space complexity of this algorithm is given. The algorithm FLE is based on Taylor series expansion and is similar to the algorithm for the fast evaluation of the exponential function FEE. A modified binary splitting algorithm ModifBinSplit for hyper-geometric series is constructed to use in algorithm FLE. It is proved that the time and space complexity of algorithms ModifBinSplit and FLE are quasi-linear and linear respectively if they are implemented on Schonhage machine; therefore it is proved that these algorithms are in class Sch(FQLIN-TIME//LIN-SPACE). Multiple interval reduction is used to compute the logarithmic function on an arbitrary interval.

Рассматриваются вопросы реализации наиболее трудоёмких этапов алгоритма Видемана — Копперсмита поиска решений сильно разреженных систем линейных уравнений на современных ЭВМ. Исследуются вопросы эффективной реализации отдельных операций алгоритма. Отдельно рассмотрены проблемы, возникающие при реализации алгоритма на вычислителях кластерного типа., This paper concerns implementation of the main steps of block Wiede-mann's algorithm for solving systems of linear equations. Effective implementation of particular operations is provided. Specific problems of implementing the algorithm for running on clusters are studied.

В работе 1985 г. Дж. Лагариас и А. Одлыжко предложили метод решения вычислительной задачи о рюкзаке, основанный на её сведении к задаче поиска короткого вектора в решётке специального вида. Метод Лагариаса — Одлыжко позволяет решать «практически все» задачи о рюкзаках, обладающие малой плотностью. В настоящей работе метод Лагариаса — Одлыжко решения задачи о рюкзаке модифицируется применительно к случаям обобщённой задачи о рюкзаке и систем задач о рюкзаках. Система задач о рюкзаках вводится в настоящей работе как конечное множество индивидуальных задач о рюкзаках, имеющих общее решение. Определяются множества значений плотности обобщённых задач о рюкзаках и систем задач о рюкзаках, такие, что модифицированные методы позволяют решать «практически все» обобщённые задачи о рюкзаках и системы задач о рюкзаках, обладающие плотностью из этих множеств., In 1985, to solve the computational knapsack problem, J.C. Lagarias and A.M. Odlyzhko have offered a method based on the reduction of this problem to the search of one of the short vector in the lattice of a special kind. This way allows to solve "almost all" knapsack problems that have a low density. In this paper the Lagarias — Odlyzhko method is modified to be applicable for solving the generalized knapsack problem and the systems of generalized knapsack problems. The system of knapsack problems is introduced hear as the finite set of the individual knapsack problems that have a common solution. Besides, for the generalized knapsack problem and for the systems of knapsack problems, some sets of density values are defined so that the modified methods allow to solve "almost all" generalized knapsack problems and the systems of knapsacks problems with the densities from these sets.

Рассматривается задача реализации алгоритма Копперсмита, вычисляющего векторные аннулирующие многочлены для матричных последовательностей, на современных 64-разрядных ЭВМ. Рассмотрены вопросы представления данных для случая последовательностей бинарных матриц с точки зрения снижения трудоёмкости алгоритма. Предложены способы эффективного распараллеливания алгоритма для реализации на ЭВМ с многоядерными процессорами, а также для выполнения алгоритма на вычислителях кластерного типа., This paper concerns implementation of Coppersmith algorithm, which allows to calculate vector generating polynomials. Data representation for binary matrix sequences is considered. Effective parallelization for mul-ticore CPUs and clusters provided.

Рассматривается механизм внесения изменений в систему семантически осмысленного ролевого управления доступом в рамках СК-РУД модели одновременно несколькими администраторами. С использованием математического аппарата сетей Петри описываются процессы перехода системы между состояниями и обосновывается условие безопасности переходов., This paper describes the process of updating Semantic RBAC system by several administrators concurrently. Processes of system transition between states are represented by a Petri net. Secure transitions are defined, and security conditions are proved for each transition type.

Представлен материал по истории криптографии в России. До сих пор она остается мало изученной и во многом засекреченной; в то же время к ней наблюдается повышенный интерес. Кратко рассмотрен период с середины XVI века до настоящего времени. Иногда хронологический порядок изложения нарушается, внимание обращается к отдельным событиям и людям, повлиявшим на ход истории криптографии или своеобразно его отразившим., In this paper, the historical survey of the cryptography in Russia is given. The period from the middle of XVI century up to date is considered.

Доказано, что вероятность протяжки однобитовой разности через сложение и вычитание по модулю равна 1, если этот бит является старшим, и 1j2, если этот бит отличен от старшего. Проведённые эксперименты подтверждают эти результаты., In this paper, a proof is given for the fact that the probability of one-bit difference propagation through modulo addition and subtraction is equal to 1 if the bit is the most significant one, and 1/2 otherwise. This theoretical fact is verified too with the experimental data.

Рассматривается схема построения возможно односторонней функции в группе с разрешимой проблемой равенства и неразрешимой проблемой эндоморфной сводимости. Анализируются предпосылки криптографической стойкости предлагаемой схемы. В качестве приложения предлагается схема аутентификации с нулевым разглашением пользователей в системе. Отмечается, что для её криптостойкости требуется неразрешимость более сильной проблемы двукратной эндоморфной сводимости., The paper considers a schema for constructing a possibly one-way function on a group with the decidable word problem and undecidable endomorphism problem. Possible prerequisites for reliability of the proposed schema are analyzed. A corresponding authentication protocol with zero knowledge is proposed as an application. It is noted that for its security a more strong assumption on the undecidability of the two-level endomorphism problem is needed.

Предлагаются алгоритмы быстрого поиска центра, радиуса и диаметра взвешенного графа по матрице кратчайших расстояний, использующие особенности графов реальных дорожных сетей, и приводятся результаты сравнительной оценки алгоритмов с поиском характеристик простым проходом по матрице., In this paper, some algorithms are presented for the fast search of center, radius and diameter of weighted graphs on all-pairs shortest path matrix, using features of real-world road networks graphs. They are compared with algorithms searching these parameters by simple pass through elements of matrix.

Известно, что оценка максимального энергопотребления логической схемы позволяет обеспечить её надёжность. Получение этой оценки облегчается предварительным нахождением такого режима работы схемы, при котором её энергопотребление оказывается максимальным. Предлагается метод нахождения этого режима для случая, когда рассматриваемая схема реализует конечный автомат., It is known that estimation of maximal energy consumption in a logic circuit allows to secure its reliability. Getting that estimation is considerably facilitated by preliminary nding such a regime of the circuit working at which its energy consumption is maximal. A method for such nding is suggested in this paper for the case when the regarded circuit implements a nite automaton.

Приводится аналитический обзор лекций и докладов, представленных на Sibecrypt'12 — XI Всероссийской конференции «Сибирская научная школа-семинар с международным участием „Компьютерная безопасность и криптография"», состоявшейся 3-8 сентября 2012 г. в Институте динамики систем и теории управления СО РАН (г.Иркутск)., This is a survey of papers and lectures presented and delivered at 11th Siberian Workshop SIBECRYPT devoted to mathematical problems in computer security and cryptography and held on September 3rd 8th, 2012, in Irkutsk, Russia.

Приведены результаты вычислительных экспериментов по определению вероятности несвязности планарных графов с высоконадёжными рёбрами. Полученные результаты подтверждают теоретическую, не более чем кубическую, оценку сложности проводимых вычислений, основанных на рассмотрении двойственных графов и построении асимптотических соотношений. Приведены результаты сравнения используемого методы с методом Монте-Карло, которые свидетельствуют о существенном сокращении числа арифметических операций и времени счета., In this paper, an algorithm based on the concept of dual graphs is constructed for calculation of incoherence probability for planar graphs with the high reliable edges. Numerical experiments show that, in a comparison with the Monte-Carlo method, this algorithm decreases calculation complexity significantly.

Циркулянтные сети интенсивно исследуются последние 30 лет и находят широкое применение в различных областях информатики и дискретной математики. По ним два обзора было опубликовано на английском языке (Дж.-К. Бермонда, Ф. Комелласа и Д. Ф. Хсу в 1995 г. и Ф. К. Хванга в 2003 г.) и один на русском языке (О. Г. Монахова и Э.А. Монаховой, 2000 г.). Настоящий обзор дополнительно включает результаты, которые не были отражены в упомянутых источниках, а также новые результаты, полученные в области исследования неориентированных циркулянтных сетей в последние годы., Circulant graphs have been extensively investigated over the past 30 years and have the broad application to different fields of computer science and discrete mathematics. Two surveys on circulant networks have been published in English: by Bermond, Comellas and Hsu (1995) and by Hwang (2003). In Russian, a survey on circulant networks is presented in a book of Monakhov and Monakhova (2000). The present paper includes the results which have not been presented in these works, and also some new results in the area of undirected circulant networks research obtained during the last years.

Работа посвящена исследованию связностных характеристик предфрактальных графов. Получены достижимые оценки для числа точек сочленения и числа мостов предфрактального графа. Свойство самоподобия определяет получение прогнозируемых диапазонов количественных оценок для перечисленных связностных характеристик., The paper is devoted to the research of prefractal graph's connectivity characteristics. Some estimations being achievable on their boundaries are received for the number of prefractal graph's cutpoints and bridges. The estimations are obliged to the self-similarity of prefractal graphs.

Дан краткий обзор современных результатов по проблеме вычисления древовидной ширины. Представлены и исследованы некоторые нижние и верхние оценки данного числового параметра графа. Предложены алгоритмические методы улучшения этих оценок., The paper gives a brief overview of recent results on the graph treewidth problem. We investigate some of the lower and upper bounds for treewidth, and present algorithmic methods to improve these bounds.