The Computational Complexity of Problems Related to Number Theory

本研究的主要焦点是数论相关问题的计算复杂性。目标是为这些问题开发有效的算法，研究它们之间的复杂性理论关系，并将所得结果应用于公钥密码系统的设计和分析。近年来，研究人员开始探索将数域和阿贝尔变的几何和算术理论作为研究数论问题计算复杂性的基本工具。最近，首席研究员（与L. M. Adleman合作）使用这些工具证明了原数检验是随机多项式时间。这是第一次在没有任何假设的情况下证明这个问题是可处理的（在随机计算的意义上）。在这个结果中，广泛地应用了阿贝尔变分理论。在这项工作中发展的理论机制和算法技术是相当通用的。该项目探索了这些技术的进一步应用，特别是当它们应用于素数测试、整数分解、有限域上的确定性多项式分解和该领域的其他基本问题时。此外，本项目还研究了并行网络模型和虚拟内存模型下的计算复杂度，并研究了广义满足问题的近似算法。该项目解决了涉及整数的重要计算任务，特别是素数测试和因数分解。如果成功，新技术将能够计算更大的整数，这将对密码学产生一些实际影响。

The primary focus of this research is the computational complexity of problems related to number theory. The goal is to develop efficient algorithms for these problems, to investigate complexity theoretic relations among them, and to apply the results obtained to the design and analysis of public key cryptographic systems. In the last few years, researchers have begun to explore the use of the geometric and arithmetic theory of number fields and Abelian varieties as fundamental tools in the study of the computational complexity of number theoretic problems. Very recently, the principal investigator (jointly with L. M. Adleman) used such tools to show that primality testing is in random polynomial time. This is the first time the problem was proved to be tractable (in the sense of randomized computation) without any hypothesis. In this result, extensive use is made of the theory of Abelian varieties. The theoretic machinery and algorithmic techniques developed in this work are quite general. The project explores further applications of these techniques particularly as they apply to primality testing, integer factoring, deterministic polynomial factorization over finite fields, and other fundamental problems in this area. In addition, the project investigates computational complexity under the parallel network model and the virtual-memory model, and in addition studies approximation algorithms for the generalized satiafiability problem. The project addresses important computational tasks involving integers, in particular primality testing and factorization. If successful, the new techniques will enable computation with much larger integers which will have several practical ramifications particularly to cryptography.