Re: Quadratic Sieve & Smooth Numbers

From: Scott Contini (contini_at_matmail.com)
Date: 08/11/04 

Date: 10 Aug 2004 23:32:43 -0700

"Russell Harper" <rharper1661@rogers.com> wrote in message news:<JW9Sc.1619732$Ar.1075042@twister01.bloor.is.net.cable.rogers.com>...
> In http://mathworld.wolfram.com/SmoothNumber.html, it gives the number of
> random numbers which must be examined to find one which is k-smooth as
> pi(k)n/psi(n, k). Does anyone know an easy approximation to pi(k)n/psi(n,
> k)?
>
> More specifically, considering a Quadratic Sieve, there is an ideal factor
> base of k primes, what is the probability that an integer ~ n^(1/2) is
> k-smooth?
>
> Thank you,
>
> Russell

The probabilitity that integers up to x are y-smooth is u^(-u + o(1))
where u = ln x / ln y , assuming y > (ln x)^(1 + epsilon) .

You should get Pomerance and Crandall's Prime Numbers book.

Scott