Computational Number Theory

这个项目调查了数论问题计算复杂性的几个方面。首先，是研究看似棘手的问题，如因式分解、决定二次残差和离散对数。我们的目标是找到更快的算法，无论是渐近的还是针对“前沿”问题大小的。其次，PI将探索有效解决数论问题需要多少随机性的问题。为此，将开发通过算法利用随机性的措施。接下来的目标是建立三个问题，i)素性测试，ii)模素数的平方根的计算，以及iii)寻找模素数的二次非剩余，具有“低”随机性需求的有效算法。最后，这个项目将探索证明关于整数N的陈述的复杂性(例如：“N恰好有2个素因数”)，除了目标陈述为真这一事实外，没有透露任何关于N的信息。

This project investigates several aspects of the computational complexity of number theoretic problems. First, is the study of apparently intractable problems such as factoring, deciding quadratic residuosity, and the discrete logarithm. The goal is to find faster algorithms, both asymptotically and for "frontier" problem sizes. Second, the PI will explore the questions of how much randomness is necessary for the effective solution of number theoretic problems. Towards this end, measures of randomness utilization by algorithms will be developed. A subsequent goal is to establish that three problems i) primality testing ii) computation of square roots modulo a prime number, and iii) finding a quadratic nonresidue modulo a prime number, have effective algorithms with "low" randomness needs. Finally, this project will explore the complexity of proving statements about an integer N (e.g. "N has exactly 2 prime factors"), without revealing any information about N other than the fact that the target statement is true.