Problems in Algorithmic and Combinatorial Number Theory

Dartmouth College, Hanover NH

Investigators

Abstract

Abstract: Problems in Algorithmic and Combinatorial Number Theory Carl Pomerance DMS-0401422 Perhaps 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.