Aspects of Algorithmic Number Theory

对于CCF-0635355，算法数论的几个方面PI：Eric Bach这个项目是关于解决数论中的问题的算法的设计和分析，以及这些算法背后的数学基础。数论算法是国家基础设施的基础，因为它们不断地用于公钥加密、为防止传输错误而对消息进行编码，以及伪随机数生成。它们也构成了任何计算机代数系统的最内层。此外，计算复杂性理论中的许多基本问题都与数论有关。研究集中在五个具体领域：a)与因式分解和可分解对象的均匀生成有关的算术函数；b)最优性测试，包括Carmichael数的推广；c)有限域上多项式的因式分解算法；d)离散对数的算法；e)算术性质的组合计算。这项研究的更广泛影响包括帮助培训下一代面向计算的研究人员，为安全可靠的通信贡献更好的系统，以及加强当地计算基础设施和地方、国家和国际智力合作。

Abstract for CCF-0635355, Aspects of Algorithmic Number TheoryPI: Eric BachThis project deals with the design and analysis of algorithms for solving problems in number theory, and the mathematics that underlies these algorithms. Number-theoretic algorithms are basic to the nation's infrastructure, as they are used continually for public key encryption, encoding of messages to resist transmission errors, and pseudo-random number generation. They also form the innermost layer of any computer algebra system. In addition, many fundamental questions in computational complexity theory are linked to number theory.The research focuses on five specific areas: a) Arithmetic functions related to factoring and the uniform generation of decomposable objects; b) Optimality testing, including generalizations of Carmichael numbers; c) Algorithms for factoring polynomials over finite fields; d) Algorithms for discrete logarithms;e) Combinatorial computations of an arithmetic nature. Broader impacts of the research include helping to train the next generation of computationally oriented researchers, contributing to better systems for secure and reliable communication, and enhancing local computational infrastructure and local, national, and international intellectual collaboration.