The Computational Complexity of Problems Related to Number Theory

点击翻译按钮获取中文摘要

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.