Algorithms to Uniformly Generate Random Factored Smooth Integers

Eric Bach, Jonathan Sorenson

Let $x\ge y>0$ be integers. A positive integer is $y$-smooth if all its prime divisors are at most $y$. Let $\Psi (x,y)$ count the number of $y$-smooth integers up to $x$. We present s…