?
Модификация и оптимизация ρ–метода факторизации Джона Полларда с помощью рекурсивного метода подсчёта факторизации чисел
Т. 1: Перспективные технологии в средствах передачи информации.
-, 2019.
Смирнов И. А., Разумов П. В., Сафарьян О. А., Черкесова Л. В.
Черкесова Л. В., Сафарьян О. А., Смирнов И. А., Молодой исследователь Дона 2018 Т. 3 (12) С. 111–121
The paper presents the project implementation of ρ-factor Pollard factorization in C ++, which works faster than the standard algorithm by 27%, which can significantly facilitate the work in deciphering and cryptanalysis of various ciphers such as RSA ...
Added: May 9, 2023
Faliszewski P., Karpov A., Obraztsova S., Autonomous Agents and Multi-Agent Systems 2022 Vol. 36 Article 18
We analyze the complexity of several NP-hard election-related problems under the assumptions that the voters have group-separable preferences. We show that under this assumption our problems typically remain NP-hard, but we provide more efficient algorithms if additionally the clone decomposition tree is of moderate height. We also show a polynomial-time algorithm for sampling group-separable elections uniformly at ...
Added: March 14, 2022
Sergei Valentinovich Fedorenko, IEEE Access 2021 Vol. 9 P. 38673–38686
A novel method for finding roots of polynomials over finite fields has been proposed.
This method is based on the cyclotomic discrete Fourier transform algorithm.
The improvement is achieved by using the normalized cyclic convolutions,
which have a small complexity and allow matrix decomposition,
as well as methods of adapting the truncated normalized cyclic convolutions calculation.
For small values of ...
Added: April 15, 2021
Ivanov F., Krouk E., Kabatiansky G. A. et al., Springer, 2020.
Unlike most papers devoted to improvements of code-based cryptosystem, where original Goppa codes are substituted by some other codes, we suggest a new method of strengthening which is code-independent. We show (up to some limit) that the security of the new code-based cryptosystem is much closer to the hardness of maximum likelihood decoding than in the ...
Added: September 17, 2020
Shitov Y., SIAM Review 2017 Vol. 59 No. 4 P. 794–800
Using elementary linear algebra, we develop a technique that leads to solutions of two widely known problems on nonnegative matrices. First, we give a short proof of the result by Vavasis stating that the nonnegative rank of a matrix is NP-hard to compute. This proof is essentially contained in the paper by Jiang and Ravikumar, ...
Added: November 9, 2017
Matveenko V., , in: Supplementary Proceedings of the Sixth International Conference on Analysis of Images, Social Networks and Texts (AIST-SUP 2017), Moscow, Russia, July 27-29, 2017Vol. 1975.: Aachen: CEUR-WS.org, 2017. Ch. 31 P. 293–300.
Commonly in network analysis a graph (network) is represented by its adjacency matrix, and the latter may have an enormous order. We show that in many situations (generalizing the case of regular graph) a much smaller matrix (referred as type adjacency matrix) may be used instead. We introduce concepts of the types of nodes and ...
Added: November 7, 2017
Shitov Y., SIAM Journal on Optimization 2017 Vol. 27 No. 3 P. 1898–1909
Let $A$ be an $m\times n$ matrix with nonnegative real entries. The PSD rank of $A$ is the smallest integer $k$ for which there exist $k\times k$ real PSD matrices $B_1,\ldots,B_m$, $C_1,\ldots,C_n$ satisfying $A(i|j)=\operatorname{tr}(B_iC_j)$ for all $i,j$. This paper determines the computational complexity status of the PSD rank. Namely, we show that the problem of ...
Added: October 24, 2017
Gribanov D., Malyshev D., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19–31
Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...
Added: October 20, 2016
Zakharov V., Cybernetics and Systems Analysis 2010 № 4 С. 39–48
This paper shows how two-tape automata can be employed to design efficient equivalence checking procedures for sequential programs. The semantics of sequential programs is defined in terms of dynamic logic structures. If a dynamic frame is acyclic (i.e., all program statements are irreversible), it can be specified by means of a two-tape deterministic automaton. Then ...
Added: September 30, 2015
Zakharov V., Новикова Т. А., Труды Института системного программирования РАН 2012 Т. 23 С. 455–476
Унифицировать два алгебраических выражения и означает отыскать такую подстановку термов вместо переменных этих выражений, чтобы оба терма и имели одинаковое значение. Задачу унификации можно распространить и на программы. Унифицировать две программы и означает отыскать такие цепочки присваиваний и ...
Added: September 30, 2015
Zakharov V., Новикова Т. А., Труды Института системного программирования РАН 2012 Т. 22 С. 435–455
Strong (logic&term) equivalence of programs is the weakest decidable equivalence relation which approximates the functional equivalence of programs. In this paper we develop a new variant of the algorithm for checking strong equivalence of programs. A distinguished feature of our algorithm is that it relies completely on the algebra of finite substitutions which includes the ...
Added: September 30, 2015
Zakharov V., Новикова Т. А., Труды Института системного программирования РАН 2014 Т. 26 № 2 С. 245–268
It is generally accepted that to unify a pair of substitutions θ_1 and θ_2 means to find out a pair of substitutions η' and η'' such that the compositions θ_1 η' and θ_2 η'' are the same. Actually, unification is the problem of solving linear equations of the form θ_1 X=θ_2 Y in the semigroup ...
Added: September 30, 2015
Zakharov V.A., Lecture Notes in Computer Science 2015 Vol. 9270 P. 208–221
Finite state transducers over semigroups can be regarded as a formal model of sequential reactive programs. In this paper we introduce a uniform tech- nique for checking e ectively functionality, k-valuedness, equivalence and inclusion for this model of computation in the case when a semigroup these transducers op- erate over is embeddable in a decidable group. ...
Added: September 30, 2015
Zakharov V., Труды Института системного программирования РАН 2015 Т. 27 № 2 С. 221–250
Finite state transducers extend the finite state automata to model functions on strings or lists. They may be used also as simple models of sequential reactive programs. These programs operate in the interaction with the environment permanently receiving data (requests) from it. At receiving a piece of data such program performs a sequence of actions. ...
Added: September 30, 2015
Shitov Y., St Petersburg Mathematical Journal 2015 Vol. 26 P. 341–350
In the paper, the concept of a semimodule is discussed, which is rather ill-behaved in tropical mathematics. The semimodules S in R^n having topological dimension two are studied, and it is shown that any such S has a finite weak dimension not exceeding n. For a fixed k, a polynomial time algorithm is constructed that ...
Added: August 12, 2015
Savateev Y., Annals of Pure and Applied Logic 2012 Vol. 163 P. 775–788
In this paper we prove that the derivability problems for product-free Lambek calculus and product-free Lambek calculus allowing empty premises are NP-complete. Also we introduce a new derivability characterization for these calculi. ...
Added: October 20, 2014
Savateev Y., Известия РАН. Серия математическая 2011 Т. 75 № 3 С. 189–222
We use proof-nets to study the algorithmic complexity of the derivability problem for some fragments of the Lambek calculus. We prove the NP-completeness of this problem for the unidirectional fragment and the product-free fragment, and also for versions of these fragments that admit empty antecedents. ...
Added: October 20, 2014