Hugh Williams, University of Manitoba, Winnipeg, Canada
History and application of numerical sieving devices
A machine is called a number sieve if it is a device which finds solutions to systems of single variable linear congruences with varying moduli. The mecanism detects these solutions by simply searching through all of the integers up to a certain preselected bound. While this approach may sound very naive, in fact it is possible to make these devices execute at a very rapid rate. Furthermore, for solving certain problems the use of these machines is the fastest method known. The purpose of this talk is to give a brief history of these devices and then to show how they have been used to obtain information on a variety of problems arising in the theory of numbers. In particular, we discuss the integer factoring problem, the primality testing problem, the search for pseudosquares, and the search for quadratic polynomials which have a high density of prime values.