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.