Robin Pemantle
Computer Science Department
University of Pennsylvania
" An upper bound on the time for quadratic sieving "
Abstract
Central to many factoring algorithms in use today is the following random process: generate random numbers in the interval [1,N] until some subset has a product which is a square (and there is a computable witness to this). Naive probabilistic models for the distribution of prime factors suggest that this stopping time has a very sharp threshold. Based on more sophisticated probabilistic models, we find a rigorous upper bound that is within a factor of 4/3 of a proven lower bound, and conjecture that our upper bound is in fact asymptotically sharp. This is joint work with Andrew Granville, Ernie Croot and Prasad Tetali.
Tuesday, November 25, 2008
3:00 - 4:15
Wu & Chen
101 Levine Hall