TIME: 1:30-2:20 pm,  November 28, 2006

PLACE: CSE 403

TITLE: The square dependence problem and factoring

SPEAKER: Prasad Tetali
         Georgia Tech
 

ABSTRACT:

In several integer factoring algorithms, one produces a sequence of
integers (created in a pseudo-random way), and wishes to determine a
subsequence whose product is a square.  A good model for how this
sequence is generated is the following process introduced by Pomerance
in his 1994 ICM lecture: Select integers $a_1,a_2,\dots,$ at random
from the interval $[1,x]$, until some subsequence has product equal to
a square. Estimating the expected stopping time of this process turns
out to be valuable in developing heuristic (and rigorous) running time
estimates for integer factoring algorithms.

Here we determine this expected stopping time up to a constant factor,
which improves previous estimates due to Pomerance (1994) and
Schroeppel (1985), who showed that this stopping time is
$J_0(x)^{1-o(1)}$, for an appropriate function $J_0(x)$.  Our
significant improvement places the stopping time in $[0.4407 J_0(x),
0.5615 J_0(x)]$, asymptotically almost surely. Our proof uses the
first and second moment methods from probabilistic combinatorics,
involves Husimi graphs and analytical estimates on smooth numbers.

This is joint work with E. Croot (Georgia Tech) and A. Granville
(University of Montreal).  The talk is expected to be fairly
nontechnical, and accessible to a general audience.