Power Digraphs in Number Theory

Abstract

The modular exponentiation is considered to be one of the renowned problems in number theory and is of paramount importance in the field of cryptography. Now a days many security systems are based on powerful cryptographic algorithms. Most of them are designed by using the exponentiation x k ≡ y (mod n) as in RSA, Diffie- Hellman key exchange, Pseudo-random number generators etc. For the last two decades, this problem is being studied by associating the power digraphs with modular exponentiation. For the fixed values of n and k, a power digraph G(n, k) is formed by taking Z n as the set of vertices and the directed edges (x, y) from x to y if x k ≡ y (mod n) for the vertices x and y. These digraphs make a novel connection between three disciplines of discrete mathematics namely number theory, graph theory and cryptography. The objective of this dissertation is to generalize the results on symmetry, heights, isolated fixed points, the number of components of a power digraph and the primality of Fermat numbers. To obtain the desired goal, a power digraph is decomposed into the direct product of smaller power digraphs by using the Chinese Remainder Theorem. The method of elimination is adopted to discard those values of n and k which do not provide desired results. During the entire course of research, the Carmichael lambda-function λ(n) is used for developing the relations between the properties of a power digraph and the parameters n, k. For any prime divisor p of n, the concept of equivalence classes has been used to discuss the symmetry of order p of G(n, k). The general rules to determine the heights are formulated by comparing the prime factorizations of k, λ(n) and the orders of vertices. Some necessary and sufficient conditions for the existence of symmetric power digraphs G(n, k), where n = p α q 1 q 2 · · · q m such that p, q i are distinct primes and α > 1, of order p are established. Explicit formulae for the determination of the heights of the vertices and components of a power digraph in terms of n, k, λ(n) and the orders of vertices are formulated. An expression for the number of vertices at a specific height is established. The power digraphs in which each vertex of indegree 0 of a certain subdigraph is at height q ≥ 1 are characterized. The necessary and sufficient conditions on n and k for a digraph to have at least one isolated fixed point are obtained. The work ends with the complete classification of the power digraphs with exactly two components.