Algebraic and Geometric Methods in Algorithmic Number Theory and Algorithmic Self-Assembly

University Of Southern California, Los Angeles CA

Investigators

Abstract

Modern cryptography has brought several number theoretic problems to the spotlight, most notably integer factoring and the discrete logarithm problem. The significance of these problems grows as the scope of application for public key cryptography is broadened. Algorithmic self-assembly is an emerging research area where interesting number theoretic and algebraic connections, though unexpected at first, have recently been discovered. It has been suggested that self-assembly will ultimately be useful for circuit fabrication, nano-robotics, DNA computation, and amorphous computing. In accordance with its practical importance, self-assembly has received increased theoretical attention over the last few years. This research addresses complexity theoretic issues in algorithmic number theory and algorithmic self-assembly. The objective is to develop efficient algebraic and geometric methods of computation in algorithmic number theory, cryptography, and algorithmic self-assembly. A primary focus of this research is the discrete logarithm problem over various groups, including the multiplicative groups of finite fields and groups associated with elliptic curves. A novel approach is taken which explores global pairings and local dualities in number fields and elliptic curves. The primary goal is to obtain results that address the computational complexity of these fundamental problems and clarify the foundational security of discrete-log based cryptosystems including elliptic curve cryptosystems. Constructive issues important to curve based cryptography will also be investigated. This research also addresses several fundamental issues concerning reversible self-assembly including, characterization and determination of equilibrium of a self-assembly system, determination of initial concentrations of different types of molecular units for achieving a targeted equilibrium behavior, and rate of convergence to equilibrium. Though these problems seem naturally require analytic tools to study, they turn out to have an interesting algebraic perspective as well. The primary goal is to obtain results that advance the mathematical and algorithmic theory of self-assembly, which is much needed for establishing guiding principles for experimental works in this area.