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

现代密码学使几个数论问题成为人们关注的焦点，其中最著名的是整数分解和离散对数问题。随着公钥加密技术应用范围的扩大，这些问题的重要性也随之增加。算法自组装是一个新兴的研究领域，其中有趣的数论和代数联系，虽然一开始是意想不到的，最近被发现。有人认为，自组装最终将用于电路制造、纳米机器人、DNA计算和非晶计算。根据其实际重要性，自组装在过去几年中得到了越来越多的理论关注。本文主要研究算法数论和算法自组装中的复杂性理论问题。目标是在算法数论、密码学和算法自组装中发展有效的代数和几何计算方法。本研究的主要焦点是各种群上的离散对数问题，包括有限域的乘法群和与椭圆曲线相关的群。提出了一种新的方法，探讨了数域和椭圆曲线上的全局对偶和局部对偶。主要目标是获得解决这些基本问题的计算复杂性的结果，并阐明基于离散对数的密码系统（包括椭圆曲线密码系统）的基本安全性。对基于曲线的密码学重要的建设性问题也将进行研究。本研究还解决了几个关于可逆自组装的基本问题，包括自组装系统的表征和平衡的确定，实现目标平衡行为的不同类型分子单元的初始浓度的确定，以及收敛到平衡的速度。虽然这些问题似乎自然需要分析工具来研究，但它们也有一个有趣的代数视角。我们的主要目标是获得能够推进自组装的数学和算法理论的结果，这对于建立该领域实验工作的指导原则是非常需要的。

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.