Algorithms in Number Theory

本课题研究数论问题的计算复杂性，这是一个既有理论意义又有实际意义的问题。 在实践方面，数论中的计算问题出现在随机数生成、密码学和计算机代数系统的设计中。 在理论方面，许多关于各种计算资源的相对能力的经典问题对数论至关重要。 例如，如果随机化对于多项式时间计算是不必要的，那么就有一个快速的确定性测试。这项工作福尔斯四类：a）设计改进的模型分析数论算法，B）改进统计测试的启发式模型数论算法，c）应用分析和代数数论计算数论，和d）将有效的算法纳入教学的初等密码学。

This project will study the computational complexity of number-theoretic problems, which is relevant to both the theory and practive of computing. On the practical side, computational problems in number theory arise in the design of systems for random number generation, cryptography, and computer algebra. On the theoretical side, many of the classic questions about the relative power of various computational resources are crucial to number theory. For example, if randomization is not necessary for polynomial-time computation, then there is a fast deterministic test for primality. This work falls into four categories:a) designing improved models for the analysis of number-theoretic algorithms,b) improving statistical tests of heuristic models for number-theoretic algorithms,c) applying analytic and algebraic number theory to computations in number theory, andd) incorporating efficient algorithms into the teaching of elementary cryptography.