Georgia Institute of Technology College of Sciences

In many integer factoring algorithms, one produces a sequence of integers (created in a pseudo-random way), and wishes to rapidly determine a subsequence whose product is a square (which we call a `square product'). In his lecture at the 1994 International Congress of Mathematicians, Pomerance observed that the following problem encapsulates all of the key issues: Select integers a1, a2, ..., at random from the interval [1,x], until some (non-empty) subsequence has product equal to a square. Find good esimates for the expected stopping time of this process. A good solution to this problem should help one to determine the optimal choice of parameters for one's factoring algorithm, and therefore this is a central question. In this talk I will discuss the history of this problem, and its somewhat recent solution due to myself, Andrew Granville, Robin Pemantle, and Prasad Tetali.