Number Theoretic, Computational and Cryptographic Aspects of a Certain Sequence of Arithmetic Progressions

Abstract

This thesis introduces a new mathematical object: collection of arithmetic progressions with elements satisfying the inverse property, \j-th terms of i-th and (i+1)-th progressions are multiplicative inverses of each other modulo (j+1)-th term of i-th progression". Such a collection is uniquely de ned for any pair (a; d) of co-prime integers. The progressions of the collection are ordered. Thus we call it a sequence rather than a collection. The results of the thesis are on the following number theoretic, computational and cryptographic aspects of the defined sequence and its generalizations. The sequence is closely connected to the classical Euclidean algorithm. Precisely, certain consecutive progressions of the sequence form \groupings". The difference between the common differences of any two consecutive progressions of a grouping is same. The number of progressions in a grouping is connected to the quotient sequence of the Euclidean algorithm on co-prime input pairs. The research community has studied extensively the behavior of the Euclidean algorithm. For the rst time in the literature, the connection (proven in the thesis) shows what the quotients of the algorithm signify. Further, the leading terms of progressions within groupings satisfy a mirror image symmetry property, called \symmetricity". The property is subject to the quotient sequence of the Euclidean algorithm and divisors of integers of the form x2 y2 falling in specific intervals. The integers a, d are the primary quantities of the defined sequence in a computational sense. Given the two, leading term and common difference of any progression of the sequence can be computed in time quadratic in the binary length of d. On the other hand, the inverse computational question of finding (a; d), given information on some terms of the sequence, is interesting. This problem turns out to be hard as it requires finding solutions to an nearly-determined system of multivariate polynomial equations. Two sub-problems arising in this context are shown to be equivalent to the problem of factoring integers. The reduction to the factoring problem, in both cases, is probabilistic. Utilizing the computational difficulty of solving the inverse problem, and the sub-problems (mentioned above), we propose a symmetric-key cryptographic scheme (SKCS), and a public key cryptographic scheme (PKCS). The PKCS is also based on the hardness of the problem of finding square-roots modulo composite integers. Our proposal uses the same algorithmic and computational primitives for effecting both the PKCS and SKCS. In addition, we use the notion of the sequence of arithmetic progressions to design an entity authentication scheme. The proof of equivalence between one of the inverse computational problems (mentioned above) and integer factoring led us to formulate and investigate an independent problem concerning the largest divisor of integer N bounded by the square-root of N. We present some algorithmic and combinatorial results. In the course of the above investigations, we are led to certain open questions of number theoretic, combinatorial and algorithmic nature. These pertain to the quotient sequence of the Euclidean algorithm, divisors of integers of the form x2 y2 p in specific intervals, and the largest divisor of integer N bounded by N.