The Computational Complexity of Problems Related to Number Theory

数论相关问题的计算复杂性

• 批准号: 8701541
• 负责人: Ming-Deh Huang
• 金额: $ 5.12万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-07-01 至 1989-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8701541&HistoricalAwards=false
• 关键词: Computational; Complexity; Problems; Related; Number

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.

这项研究的主要焦点是计算的复杂性， 与数论有关的问题。 目标是开发高效的 这些问题的算法，研究复杂性理论 它们之间的关系，并将所得结果应用于设计 和公钥密码系统的分析。 在过去的几年里，研究人员已经开始探索使用 数域与阿贝尔簇的几何与算术理论 作为研究计算复杂性的基本工具， 数论问题 最近，首席研究员 （与L。M. Adleman）使用这样的工具来证明素性 测试在随机多项式时间内进行。 这是第一次 问题被证明是易于处理的（在随机化的意义上 计算）没有任何假设。 在这个结果中， Abel Variations的理论。 理论机器和 在这项工作中开发的算法技术是相当通用的。 的 该项目探讨了这些技术的进一步应用，特别是 因为它们适用于素性测试、整数分解、确定性 有限域上的多项式因式分解，以及其他基本的 这方面的问题。 此外，该项目还研究了在 并行网络模型和虚拟内存模型， 加法研究了广义 可满足性问题 该项目解决了涉及整数的重要计算任务， 特别是素性测试和因子分解。 如果成功， 新技术将使计算更大的整数， 将有几个实际的分支，特别是对密码学。