AF:Small:Algorithmic Number Theory

本课题致力于数论中算法的设计和分析。它主要集中在三个子领域：与整数的素因式分解有关的问题，域和环等有限代数对象上迭代映射的行为，以及利用组合学和解析数论的思想来加深我们对多项式分解的认识。本课题所研究的问题是计算数论中最重要的问题之一，并为计算复杂性理论和新兴的量子计算理论提供了关键的例子。解决这些问题的算法对于安全可靠的电子通信、计算机代数和伪随机数生成也非常有用。该项目取得的成果将有可能对上述所有领域产生影响。它们还将加强理论计算机科学和纯数学之间的联系。这是因为数论算法的行为与解析数论、代数几何、概率论和动力系统中的重要问题密切相关。该项目的一个关键组成部分是研究生支持。这种援助的形式是由国际数学研究所监督的研究助学金，这将有助于维持数学科学中经过算法训练的研究人员的渠道。该项目还将有助于将研究和教学结合起来，帮助他开发和宣传关于应用数论、通信技术和量子计算等主题的跨学科课程和研讨会。

This project addresses the design and analysis of algorithms in number theory. It focuses on three subareas in detail: problems related to the prime factorization of integers, the behavior of iterated maps on finite algebraic objects such as fields and rings, and the exploitation of ideas from combinatorics and analytic number theory to further our knowledge about polynomial factoring.The problems studied in this project are among the most important in computational number theory, and provide key examples for computational complexity theory and the emerging theory of quantum computing. Algorithms to solve these problems are also extremely useful for secure and reliable electronic communication, for computer algebra, and for pseudo-random number generation. Results obtained in the project will have the potential to impact all of the above areas. They will also enhance the connections between theoretical computer science and pure mathematics. This is because the behavior of number-theoretic algorithms is intimately connected to significant questions in analytic number theory, algebraic geometry, probability theory, and dynamical systems.A key component of the project is graduate student support. Such aid, in the form of research assistantships supervised by the PI, will help maintain the pipeline of algorithmically trained researchers in the mathematical sciences. The project will also help integrate research and teaching, by helping him to develop and publicize interdisciplinary courses and seminars on topics such as applied number theory, communication technology, and quantum computation.