Computational Complexity and its Relationship to Number Theory

这项研究的主要焦点是计算问题的数论方面。近年来，人们对这一领域的兴趣死灰复燃。解决了古老的问题(例如素性测试)，催生了新的子学科(例如公钥密码学)，出现了深度数学工具(例如阿贝尔变种、类域理论)。一个特别令人感兴趣的领域是新的“数字字段筛选”。这组由许多研究人员开发的算法是过去25年来整数因式分解最显著的进步。这项工作继续研究对该方法的改进和推广，特别是对函数域设置的改进和推广。新的“函数域筛法”用于有限域上离散对数的计算，有望取代现有的适当形式的有限域的算法。第二个感兴趣的领域是最近的结果在公钥密码学中的应用。美国政府最近提出了国家数字签名标准(DSS)。该方案的安全性依赖于离散对数的计算难度。DSS是有争议的，这项研究调查了几种方法的潜力，包括数字域筛选和函数域筛选，以打破所提出的系统或引入“陷阱门”。另一个研究领域涉及开发新的数学工具。最后，探讨了生物系统与计算之间的关系。这种关系的一个方面与计算机病毒有关。

The primary focus of this research is the number theoretic aspects of computational problems. In recent years there has been a resurgence of interest in this area. Ancient problems have been solved (e.g. primality testing), new subdisciplines have been spawned (e.g. public-key cryptography) and deep mathematical tools have emerged (e.g. Abelian varieties, class field theory). One area of particular interest is the new ``number field sieve`. This collection of algorithms, developed by many researchers, is the most significant advance in integer factoring in the last quarter century. This work continues to investigate improvements and generalizations of this method, in particular, to the function field setting. The new ``function field sieve` is used for the calculations of discrete logarithms over finite fields and shows promise for supplanting existing algorithms for finite fields of appropriate form. A second area of interest is the application of recent results to public-key cryptography. The United States Government has recently proposed a national ``Digital Signature Standard` (DSS). The proposed scheme relies for its security on the difficulty of computing discrete logarithms. The DSS is controversial and this research investigates the potential of several methods, including the number field sieve and the function field sieve, for breaking the proposed system or for introducing ``trapdoors`. Another area of investigation involves the development of new mathematical tools. Finally, the relationships between biological systems and computation is explored. One aspect of this relationship concerns computer viruses.