Topics in combinatorial and algorithmic number theory

pomerancedms -0703850奖摘要：本文讨论了计算数论和组合数论中的几个问题，以及算术函数理论及其在椭圆曲线列中的应用。在第一类中，PI将与Hendrik Lenstra合作改进AKS素数检验，并将其应用于有限域的构造，他将与Lenstra和Jonathan Pila合作研究涉及2属超椭圆曲线雅可比矩阵的严格快速分解算法。在组合数论方面，PI将继续他最近与Michael Filaseta， Kevin Ford， Sergei Konyagin和Gang Yu合作处理Paul Erdos的覆盖同余问题。PI将研究的算术函数有：乘群模整数的阶数（欧拉函数）和这个群的最大循环子群的阶数（卡迈克尔函数），包括这个子群在满群中的索引。该指标应用于Ulmer对正特征函数场上椭圆曲线的秩的研究和Arnold的一些问题。PI将与Igor Shparlinski合作前一项申请，与Michel Balazard合作后一项申请。通过卡迈克尔函数，PI打算与弗洛里安·卢卡一起大力改进有关其范围的已知结果。人们可能会认为，关于整数的基本问题，比如决定什么时候一个数是素数，把另一个数分解，或者当一个特定的数被用作除数时，余数的乘法结构，到现在应该已经很好地理解了。但事实并非如此，对于其中一个问题，即因式分解，它显然通常很困难，这是支撑商业和通信的加密系统安全性的基础。该提案的主要建议活动涉及这些基本问题，主要是从理论方面。此外，PI还提出研究余数的乘法结构在某些椭圆曲线秩的研究中的一些应用。椭圆曲线由二元三次方程产生；研究这样一个方程的解，它的变量来自给定的代数域，如有理数和类似的域。它们为数论学家提供了丰富的结构来源。这些曲线也被用于密码系统和计算数论中，但是PI在这里的重点是对解集的某些代数不变量作为一个变化曲线参数的统计研究。最后，PI将研究组合数论中的一些问题，包括已故Paul Erdos的著名的覆盖同余问题。这里的问题是，是否存在一个有限的大整数集，每个大整数都有一个余数，使得每个整数除以给定的大数时，在给定的预设列表中至少留下一个相应的余数。“大”的当前记录是25，不知道是否可以对任意大的数字执行此操作。

Abstract for the award DMS-0703850of PomeranceThis proposal deals with several problems in computational and combinatorial number theory, and the theory of arithmetic functions with applications to ranks of elliptic curves. In the first category, the PI will work with Hendrik Lenstra on improving the AKS primality test, with applications to the construction of finite fields, and he will work with Lenstra and Jonathan Pila on a rigorously fast factorization algorithm involving jacobian varieties of hyperelliptic curves of genus 2. In combinatorial number theory, the PI will continue his recent work with Michael Filaseta, Kevin Ford, Sergei Konyagin, and Gang Yu dealing with the covering congruences problem of Paul Erdos.Among the arithmetic functions that the PI will study are the order of the multiplicative group modulo an integer (Euler's function) and the order of the largest cyclic subgroup of this group (Carmichael's function), including the index of this subgroup in the full group. This index has applications to the work of Ulmer on the ranks of elliptic curves over function fields of positive characteristic and some questions of Arnold. The PI will be working jointly with Igor Shparlinski on the former applications and with Michel Balazard on the latter. With the Carmichael function, the PI intends with Florian Luca to strongly improve the known results concerning its range.One would think that basic questions concerning the integers, such as deciding when one is prime, factoring another, or the multiplicative structure of the remainders when a particular number is used as a divisor, would be well-understood by now. But they are not, and for one of these problems, namely factoring, the fact that it is apparently difficult in general is the basis for the security of cryptographic systems that underpin commerce and communication. The principal proposed activities of this proposal concern these fundamental problems, mostly from the theoretical side. In addition, the PI proposes to study some applications of the multiplicative structure of remainders to the study of the ranks of certain elliptic curves. Elliptic curves arise from cubic equations in two variables; one studies the solutions to such an equation with the variables coming from a given algebraic domain such as the rational numbers and similar domains. They have provided a rich source of structure for number theorists. These curves too have been used in cryptographic systems and in computational number theory, but the PI's focus here is a statistical study of certain algebraic invariants of the solution sets as one varies curve parameters. Finally, the PI will study some problems in combinatorial number theory, including the famous covering congruences problem of the late Paul Erdos. Here one asks if there can be a finite set of large integers and a single remainder for each such that every integer when divided by the given large numbers leaves at least one corresponding remainder in the given pre-set list. The current record for "large" is 25, and it is not known if one can do this with arbitrarily large numbers.