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.