The Ivan and Betty Niven Distinguished Lectures

University of British Columbia

March 21 - 23, 2005

The UBC Department of Mathematics is proud to present a series of lectures on Number Theory presented by Carl Pomerance of Dartmouth College.

These lecture series were made possible through a generous bequest received from Ivan and Betty Niven.

In honor of their generous support, the Department of Mathematics has established a permanent endowment fund, "The Ivan and Betty Niven Distinguished Lectures Fund", the income from which will fund a series of annual lectures on a broad array of topics in Mathematics.

Lecture #1 (Joint IAM-Mathematics Colloquium)

Monday, March 21, 3:00-4:00, MATX 1100

A New Primal Screen

How fast can one determine if a given number is prime or composite? This question, which was first posed explicitly by Gauss in 1801, has been the subject of much attention in the computer age. In 2002, Agrawal, Kayal and Saxena announced a new and surprisingly simple deterministic algorithm that runs in polynomial time (within a fixed power of the number of digits of the number in question). We will discuss this algorithm as well as more recent developments.

Reception and Refreshements, 4:00--6:00, MATX 1115

Lecture #2 (Student Lecture)

Tuesday, March 22, 12:30-2:00, MATH 100

Unsolved prime-number problems

From the twin-prime conjecture to Goldbach's conjecture and the Riemann Hypothesis, there are plenty of unsolved problems related to prime numbers. In this talk we will discuss these and more, including recent progress.

Lecture #3 (Number Theory Seminar)

Wednesday, March 23, 3:00-4:00, WMAX 110

Periods of pseudorandom number generators

This talk will consider two common pseudorandom number generators based in number theory. The first, due to D.H. Lehmer, is the linear congruential generator, where the (n+1)-st iterate x(n+1) is ax(n)+b (mod m) (where a,b,m and an initial seed x(0) are given). This generator is commonly used in numerical analysis for Monte Carlo simulations. The other is the power generator x(n+1)=x(n)^a (mod m) where a,m and x(0) are given. This generator has cryptographic applications. Among other results we have that for any nontrivial choice of parameters a,b,x(0), the linear congruential generator has period m/exp((1+o(1))loglog m logloglog m) for almost all m , while the power generator has period m/exp((1+o(1))(loglog m)^2 logloglog m) for almost all m. These results, which are conditional on the Generalized Riemann Hypothesis, are joint with Par Kurlberg, Shuguang Li, and Greg Martin.