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.