Problems in Algorithmic and Combinatorial Number Theory

摘要：算术和组合数论中的问题卡尔·波美朗斯DMS-0401422也许算术中最基本的问题是区分素数和复合数，并将复合数分解成它们的素因数。最近，阿格拉瓦尔、卡亚尔和萨克塞纳在质数识别问题上取得了惊人的进展，这导致了这一领域的复兴。首席调查员建议寻找AKS测试的可证明变体，以达到其启发式复杂性，并使用解析数论中有效的可计算工具来做到这一点。此外，首席调查员还建议研究某些常用伪随机数生成器的正常周期长度和正常周期数。更多的理论问题包括多项式序列中素数之间的间隙，涉及原根的方程，以及乘法函数的除数。这位首席调查员计划在他最近在达特茅斯学院教授的一门研究生课程的基础上写一本关于素性测试的专著。考虑到拟议研究的更广泛影响，密码学和信息安全领域严重依赖算法数论，而后者的基本进展对前者非常感兴趣。事实上，天生保守的信息安全领域或许更希望算法数论不再有任何根本性的进步。它们仍然可能在这么晚的时候发生，这可能会导致安全领域重新思考并扩大其主题的基础。伪随机数发生器的研究在密码学和数值分析中有着广泛的应用。令人惊讶的是，我们不知道某些基本和常用发电机的典型周期长度或典型周期数，这是本提案讨论的一个问题。将被考虑的理论主题涉及与素数有关的某些基本和自然问题，其中一些问题很可能导致实际应用。例如，原根也与密码学领域密切相关，深入了解它们之间可能存在的关系具有根本的意义。

Abstract: Problems in Algorithmic and Combinatorial Number TheoryCarl Pomerance DMS-0401422Perhaps the most fundamental problem in arithmetic is that of distinguishing prime numbers from composite numbers, and factoring composites into their prime factors. Recent stunning progress by Agrawal, Kayal, and Saxena on the prime recognition problem has led to a rejuvenation of the field. The Principal Investigator proposes to find provable variants of the AKS test that achieve its heuristic complexity, and do so with effectively computable tools in analytic number theory. In addition, the Principal Investigator proposes to study normal cycle lengths and the normal number of cycles of certain commonly used pseudorandom number generators. More theoretical problems include gaps between primes in a polynomial sequence, equations involving primitive roots, and the number of divisors of a multiplicative function. The Principal Investigator has plans to write a monograph on primality testing based on a graduate-level course he recently taught at Dartmouth College.Concerning broader impacts of the proposed research, the fields of cryptology and information security depend heavily on algorithmic number theory, and fundamental advances in the latter field are of intense interest in the former. In fact, the naturally conservative field of information security would perhaps prefer that there not be any more fundamental advances in algorithmic number theory. That they still can occur at this late date may cause the security field to rethink and broaden the underpinnings of their subject. The study of pseudorandom number generators has many applications to cryptology and numerical analysis. Surprisingly, we don't know the typical cycle length or the typical number of cycles for certain basic and commonly-used generators, a topic addressed by this proposal. The theoretical topics that will be considered deal with certain basic and natural questions connected with prime numbers, and some of these problems may well lead to practical applications. For example, primitive roots are also closely connected to the field of cryptology, and a deeper understanding of the possible relationships among them is of fundamental interest.