Topics in combinatorial and algorithmic number theory

本文讨论了计算和组合数论中的几个问题，以及算术函数理论及其在椭圆曲线秩中的应用。在第一类中，PI将与Hendrik Lenstra合作改进AKS素性检验，并应用于有限域的构造，他将与Lenstra和Jonathan Pila合作严格快速的因式分解算法，涉及亏格2的超椭圆曲线的雅可比变种。在组合数论中，PI将继续他最近与Michael Filaseta、Kevin Ford、Sergei Kanyagin和Gang Yu处理Paul Erdo的覆盖同余问题的工作。PI将研究的算术函数是模为整数的乘法群的顺序(欧拉函数)和该群的最大循环子群的顺序(Carmichael函数)，将该子组的索引包括在全组中。该指标在Ulmer关于正特征函数域上椭圆曲线的秩上的工作和Arnold的一些问题上都有应用。PI将与伊戈尔·什帕林斯基共同处理前者的应用程序，并与米歇尔·巴拉扎德共同处理后者。利用Carmichael函数，PI打算和Florian Luca一起大力改进关于它的值域的已知结果。人们会认为关于整数的基本问题，例如判断一个是素数，分解另一个，或者当一个特定的数被用作除数时，余数的乘法结构，到现在应该已经很好地理解了。但事实并非如此，对于其中一个问题，即保理，它显然总体上很困难，这一事实是支撑商业和通信的密码系统安全的基础。这项建议的主要拟议活动主要涉及这些基本问题，主要是从理论方面。此外，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.