Computational Complexity and its Relationship to Number Theory

这项研究的主要重点是计算问题的数论方面。 近年来，人们对这一领域的兴趣重新抬头。 古老的问题已经得到解决（例如素数测试），新的分支学科已经产生（例如公钥密码学），并且出现了深刻的数学工具（例如阿贝尔变种，类域理论）。 一个特别令人感兴趣的领域是新的“数域筛”。 这一系列算法由许多研究人员开发，是上个世纪整数分解中最重要的进展。 这项工作继续调查改进和推广这种方法，特别是，功能字段设置。 新的"函数域筛“用于计算有限域上的离散元，并有望取代现有的适当形式的有限域算法。 感兴趣的第二个领域是最近的结果应用到公钥密码学。 美国政府最近提出了一项国家“数字签名标准"。 该方案的安全性依赖于离散时间序列的计算难度。 决策支持系统是有争议的，本研究探讨了几种方法，包括数字字段筛选和功能字段筛选，打破拟议的系统或引入"陷阱“的潜力。 另一个研究领域涉及新的数学工具的开发。 最后，生物系统和计算之间的关系是 探讨了这种关系的一个方面涉及计算机病毒。

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.