Computational Complexity and its Relationship to Number Theory

本研究的主要焦点是计算问题的数论方面。近年来，人们对这一领域的兴趣重新燃起。古老的问题已经得到解决（例如，素数测试），新的分支学科已经产生（例如，公钥密码学），深度数学工具已经出现（例如，阿贝尔变种，类场论）。一个特别有趣的领域是新的“数字字段筛”。由许多研究人员开发的这套算法集合，是过去四分之一世纪中整数分解最重要的进展。这项工作将继续研究这种方法的改进和推广，特别是在函数字段设置方面。新的“函数场筛”用于计算有限域上的离散对数，并有望取代现有的适当形式的有限域算法。第二个感兴趣的领域是将最近的结果应用于公钥加密。美国政府最近提出了一项国家“数字签名标准”（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.