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.