##### Department of Mathematics,

University of California San Diego

****************************

### Probability Seminar

## Robin Pemantle

#### University of Pennsylvania

## Complexity upper bound for a sieving algorithm

##### Abstract:

\indent 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. Naive probabilistic models for the distribution of prime factors suggest that this stopping time has a sharp threshold. Based on more sophisticated probabilistic models, we find a rigorous upper bound that is within a factor of 4/pi 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.

Host: Jason Schweinsberg

### April 5, 2011

### 2:00 PM

### AP&M 7321

****************************