Multiplex congruence network of natural numbers

Congruence theory has many applications in physical, social, biological and technological systems. Congruence arithmetic has been a fundamental tool for data security and computer algebra. However, much less attention was devoted to the topological features of congruence relations among natural numbers. Here, we explore the congruence relations in the setting of a multiplex network and unveil some unique and outstanding properties of the multiplex congruence network. Analytical results show that every layer therein is a sparse and heterogeneous subnetwork with a scale-free topology. Counterintuitively, every layer has an extremely strong controllability in spite of its scale-free structure that is usually difficult to control. Another amazing feature is that the controllability is robust against targeted attacks to critical nodes but vulnerable to random failures, which also differs from ordinary scale-free networks. The multi-chain structure with a small number of chain roots arising from each layer accounts for the strong controllability and the abnormal feature. The multiplex congruence network offers a graphical solution to the simultaneous congruences problem, which may have implication in cryptography based on simultaneous congruences. Our work also gains insight into the design of networks integrating advantages of both heterogeneous and homogeneous networks without inheriting their limitations.

Related papers:

title: An Introduction to the Theory of Numbers
abstract: This is the fifth edition of a work (first published in 1938) which has become the standard introduction to the subject. The book has grown out of lectures delivered by the authors at Oxford, Cambridge, Aberdeen, and other universities. It is neither a systematic treatise on the theory of numbers nor a 'popular' book for non-mathematical readers. It contains short accounts of the elements of many different sides of the theory, not usually combined in a single volume; and, although it is written for mathematicians, the range of mathematical knowledge presupposed is not greater than that of an intelligent first-year student. In this edition, the main changes are in the notes at the end of each chapter. Sir Edward Wright seeks to provide up-to-date references for the reader who wishes to pursue a particular topic further and to present, both in the notes and in the text, a reasonably accurate account of the present state of knowledge.

title: From Number Theory to Physics
abstract: 1. An Introduction to Zeta Functions.- 2. Introduction to Compact Riemann Surfaces, Jacobians, and Abelian Varieties.- 3. Elliptic Curves.- 4. Introduction to Modular Forms.- 5. Decorated Elliptic Curves: Modular Aspects.- 6. Galois Theory, Algebraic Number Theory, and Zeta Functions.- 7. Galois Theory for Coverings and Riemann Surfaces.- 8. Differential Galois Theory.- 9. p-adic Numbers and Ultrametricity.- 10. Introduction to Lattice Geometry.- 11. A Short Introduction to Quasicrystallography.- 12. Gap Labelling Theorems for Schrodinger Operators.- 13.  Irrationally Winding.- 14. An Introduction to Small Divisors Problems.

title: Chinese remainder theorem: applications in computing, coding, cryptography
abstract: Chinese remainder algorithm in modular computations in algorithmics in bridging computations in coding theory in cryptography tutorial in information theory tutorial in algebra list of mathematical symbols.

title: Number Theory for Computing
abstract: From the Publisher: 
There are many surprising connections between the theory of numbers, which is one of the oldest branches of mathematics, and computing and information theory. Number theory has important applications in computer organization and security, coding and cryptography, random number generation, hash functions, and graphics. Conversely, number theorists use computers in factoring large integers, determining primes, testing conjectures, and solving other problems. This book takes the reader from elementary number theory, via algorithmic number theory, to applied number theory in computer science. It introduces basic concepts, results, and methods, and discusses their applications in the design of hardware and software, cryptography, and security. It is aimed at undergraduates in computing and information technology, but will also be valuable to mathematics students interested in applications. In this 2nd edition full proofs of many theorems are added and some corrections are made.

title: Number theory in science and communication - with applications in cryptography, physics, digital information, computing, and self-similarity, 4th Edition
abstract: "Number Theory in Science and Communication" is a well-known introduction for non-mathematicians to this fascinating and useful branch of applied mathematics . It stresses intuitive understanding rather than abstract theory and highlights important concepts such as continued fractions, the golden ratio, quadratic residues and Chinese remainders, trapdoor functions, pseudo primes and primitive elements. Their applications to problems in the real world are one of the main themes of the book. This revised fifth edition is augmented by recent advances in coding theory, permutations and derangements and a chapter in quantum cryptography. From reviews of earlier editions "I continue to find [Schroeders] Number Theory a goldmine of valuable information. It is a marvelous book, in touch with the most recent applications of number theory and written with great clarity and humor. Philip Morrison ( "A light-hearted and readable volume with a wide range of applications to which the author has been a productive contributor useful mathematics outside the formalities of theorem and proof." Martin Gardner

title: Cryptographic hash functions
abstract: Hash functions were introduced in cryptology in the late seventies as a tool to protect the authenticity of information. Soon it became clear that they were a very useful building block to solve other security problems in telecommunication and computer networks. This paper sketches the history of the concept, discusses the applications of hash functions, and presents the approaches that have been followed to construct hash functions. In addition, it tries to provide the information which is necessary to choose a practical hash function. An overview of practical constructions and their performance is given and some attacks are discussed. Special attention is paid to standards dealing with hash functions.

title: How to Break MD5 and Other Hash Functions
abstract: MD5 is one of the most widely used cryptographic hash functions nowadays. It was designed in 1992 as an improvement of MD4, and its security was widely studied since then by several authors. The best known result so far was a semi free-start collision, in which the initial value of the hash function is replaced by a non-standard value, which is the result of the attack. In this paper we present a new powerful attack on MD5 which allows us to find collisions efficiently. We used this attack to find collisions of MD5 in about 15 minutes up to an hour computation time. The attack is a differential attack, which unlike most differential attacks, does not use the exclusive-or as a measure of difference, but instead uses modular integer subtraction as the measure. We call this kind of differential a modular differential. An application of this attack to MD4 can find a collision in less than a fraction of a second. This attack is also applicable to other hash functions, such as RIPEMD and HAVAL.

title: Exact controllability of multiplex networks
abstract: We develop a general framework to analyze the controllability of multiplex networks using multiple-relation networks and multiple-layer networks with interlayer couplings as two classes of prototypical systems. In the former, networks associated with different physical variables share the same set of nodes and in the latter, diffusion processes take place. We find that, for a multiplerelation network, a layer exists that dominantly determines the controllability of the whole network and, for a multiple-layer network, a small fraction of the interconnections can enhance the controllability remarkably. Our theory is generally applicable to other types of multiplex networks as well, leading to significant insights into the control of complex network systems with diverse structures and interacting patterns.

title: Families and clustering in a natural numbers network.
abstract: We develop a network in which the natural numbers are the vertices. The decomposition of natural numbers by prime numbers is used to establish the connections. We perform data collapse and show that the degree distribution of these networks scales linearly with the number of vertices. We explore the families of vertices in connection with prime numbers decomposition. We compare the average distance of the network and the clustering coefficient with the distance and clustering coefficient of the corresponding random graph. In case we set connections among vertices each time the numbers share a common prime number the network has properties similar to a random graph. If the criterion for establishing links becomes more selective, only prime numbers greater than p(l) are used to establish links, where the network has high clustering coefficient.

title: Number theoretic example of scale-free topology inducing self-organized criticality.
abstract: In this Letter we present a general mechanism by which simple dynamics running on networks become self-organized critical for scale-free topologies. We illustrate this mechanism with a simple arithmetic model of division between integers, the division model. This is the simplest self-organized critical model advanced so far, and in this sense it may help to elucidate the mechanism of self-organization to criticality. Its simplicity allows analytical tractability, characterizing several scaling relations. Furthermore, its mathematical nature brings about interesting connections between statistical physics and number theoretical concepts. We show how this model can be understood as a self-organized stochastic process embedded on a network, where the onset of criticality is induced by the topology.

title: Natural Number Network and Prime Number Theorem
abstract: A divisibility-based natural number network is introduced. Some interesting results are found. For example, determining divisibility-based natural number network and stochastic coping model network have the same degree distribution; the average degree of divisibility-based natural number network and the conjecture of prime number theorem are closely related. These results show that prime numbers are randomness and sparseness in natural numbers.

title: Complex architecture of primes and natural numbers.
abstract: Natural numbers can be divided in two nonoverlapping infinite sets, primes and composites, with composites factorizing into primes. Despite their apparent simplicity, the elucidation of the architecture of natural numbers with primes as building blocks remains elusive. Here, we propose a new approach to decoding the architecture of natural numbers based on complex networks and stochastic processes theory. We introduce a parameter-free non-Markovian dynamical model that naturally generates random primes and their relation with composite numbers with remarkable accuracy. Our model satisfies the prime number theorem as an emerging property and a refined version of Cramér's conjecture about the statistics of gaps between consecutive primes that seems closer to reality than the original Cramér's version. Regarding composites, the model helps us to derive the prime factors counting function, giving the probability of distinct prime factors for any integer. Probabilistic models like ours can help to get deeper insights about primes and the complex architecture of natural numbers.

title: Divisibility patterns of natural numbers on a complex network
abstract: Investigation of divisibility properties of natural numbers is one of the most important themes in the theory of numbers. Various tools have been developed over the centuries to discover and study the various patterns in the sequence of natural numbers in the context of divisibility. In the present paper, we study the divisibility of natural numbers using the framework of a growing complex network. In particular, using tools from the field of statistical inference, we show that the network is scale-free but has a non-stationary degree distribution. Along with this, we report a new kind of similarity pattern for the local clustering, which we call “stretching similarity”, in this network. We also show that the various characteristics like average degree, global clustering coefficient and assortativity coefficient of the network vary smoothly with the size of the network. Using analytical arguments we estimate the asymptotic behavior of global clustering and average degree which is validated using numerical analysis.

title: Navigation in a small world
abstract: The small-world phenomenon — the principle that most of us are linked by short chains of acquaintances — was first investigated as a question in sociology and is a feature of a range of networks arising in nature and technology. Experimental study of the phenomenon revealed that it has two fundamental components: first, such short chains are ubiquitous, and second, individuals operating with purely local information are very adept at finding these chains. The first issue has been analysed, and here I investigate the second by modelling how individuals can find short chains in a large social network.

title: Optimizing controllability of complex networks by minimum structural perturbations.
abstract: To drive a large, complex, networked dynamical system toward some desired state using as few external signals as possible is a fundamental issue in the emerging field of controlling complex networks. Optimal control is referred to the situation where such a network can be fully controlled using only one driving signal. We propose a general approach to optimizing the controllability of complex networks by judiciously perturbing the network structure. The principle of our perturbation method is validated theoretically and demonstrated numerically for homogeneous and heterogeneous random networks and for different types of real networks as well. The applicability of our method is discussed in terms of the relative costs of establishing links and imposing external controllers. Besides the practical usage of our approach, its implementation elucidates, interestingly, the intricate relationship between certain structural properties of the network and its controllability.

title: Network controllability is determined by the density of low in-degree and out-degree nodes.
abstract: The problem of controllability of the dynamical state of a network is central in network theory and has wide applications ranging from network medicine to financial markets. The driver nodes of the network are the nodes that can bring the network to the desired dynamical state if an external signal is applied to them. Using the framework of structural controllability, here, we show that the density of nodes with in degree and out degree equal to one and two determines the number of driver nodes in the network. Moreover, we show that random networks with minimum in degree and out degree greater than two, are always fully controllable by an infinitesimal fraction of driver nodes, regardless of the other properties of the degree distribution. Finally, based on these results, we propose an algorithm to improve the controllability of networks.

title: Exact controllability of complex networks
abstract: Controlling complex networks is of paramount importance in science and engineering. Despite the recent development of structural controllability theory, we continue to lack a framework to control undirected complex networks, especially given link weights. Here we introduce an exact controllability paradigm based on the maximum multiplicity to identify the minimum set of driver nodes required to achieve full control of networks with arbitrary structures and link-weight distributions. The framework reproduces the structural controllability of directed networks characterized by structural matrices. We explore the controllability of a large number of real and model networks, finding that dense networks with identical weights are difficult to be controlled. An efficient and accurate tool is offered to assess the controllability of large sparse and dense networks. The exact controllability framework enables a comprehensive understanding of the impact of network properties on controllability, a fundamental problem towards our ultimate control of complex systems.

title: Controllability of complex networks
abstract: The ultimate proof of our understanding of natural or technological systems is reflected in our ability to control them. Although control theory offers mathematical tools for steering engineered and natural systems towards a desired state, a framework to control complex self-organized systems is lacking. Here we develop analytical tools to study the controllability of an arbitrary complex directed network, identifying the set of driver nodes with time-dependent control that can guide the system’s entire dynamics. We apply these tools to several real networks, finding that the number of driver nodes is determined mainly by the network’s degree distribution. We show that sparse inhomogeneous networks, which emerge in many real complex systems, are the most difficult to control, but that dense and homogeneous networks can be controlled using a few driver nodes. Counterintuitively, we find that in both model and real systems the driver nodes tend to avoid the high-degree nodes.

title: Robustness analysis of network controllability
abstract: Structural controllability, which is an interesting property of complex networks, attracts many researchers from various fields. The maximum matching algorithm was recently applied to explore the minimum number of driver nodes, where control signals are injected, for controlling the whole network. Here we study the controllability of directed Erdos–Renyi and scale-free networks under attacks and cascading failures. Results show that degree-based attacks are more efficient than random attacks on network structural controllability. Cascade failures also do great harm to network controllability even if they are triggered by a local node failure.

title: Control Centrality and Hierarchical Structure in Complex Networks
abstract: We introduce the concept of control centrality to quantify the ability of a single node to control a directed weighted network. We calculate the distribution of control centrality for several real networks and find that it is mainly determined by the network’s degree distribution. We show that in a directed network without loops the control centrality of a node is uniquely determined by its layer index or topological position in the underlying hierarchical structure of the network. Inspired by the deep relation between control centrality and hierarchical structure in a general directed network, we design an efficient attack strategy against the controllability of malicious networks.

title: Universal behavior of load distribution in scale-free networks.
abstract: We study a problem of data packet transport in scale-free networks whose degree distribution follows a power law with the exponent gamma. Load, or "betweenness centrality," of a vertex is the accumulated total number of data packets passing through that vertex when every pair of vertices sends and receives a data packet along the shortest path connecting the pair. It is found that the load distribution follows a power law with the exponent delta approximately 2.2(1), insensitive to different values of gamma in the range, 2 < gamma < or = 3, and different mean degrees, which is valid for both undirected and directed cases. Thus, we conjecture that the load exponent is a universal quantity to characterize scale-free networks.

title: Fundamental structural constraint of random scale-free networks.
abstract: We study the structural constraint of random scale-free networks that determines possible combinations of the degree exponent γ and the upper cutoff k(c) in the thermodynamic limit. We employ the framework of graphicality transitions proposed by Del Genio and co-workers , while making it more rigorous and applicable to general values of k(c). Using the graphicality criterion, we show that the upper cutoff must be lower than k(c)∼N(1/γ) for γ<2, whereas any upper cutoff is allowed for γ>2. This result is also numerically verified by both the random and deterministic sampling of degree sequences.

title: Handbook of Applied Cryptography
abstract: From the Publisher: 
A valuable reference for the novice as well as for the expert who needs a wider scope of coverage within the area of cryptography, this book provides easy and rapid access of information and includes more than 200 algorithms and protocols; more than 200 tables and figures; more than 1,000 numbered definitions, facts, examples, notes, and remarks; and over 1,250 significant references, including brief comments on each paper.

title: Network growth by copying.
abstract: We introduce a growing network model in which a new node attaches to a randomly selected node, as well as to all ancestors of the target node. This mechanism produces a sparse, ultrasmall network where the average node degree grows logarithmically with network size while the network diameter equals 2. We determine basic geometrical network properties, such as the size dependence of the number of links and the in- and out-degree distributions. We also compare our predictions with real networks where the node degree also grows slowly with time--the Internet and the citation network of all Physical Review papers.