Smooth Number

An Integer is $k$-smooth if it has no Prime Factors $>k$. The probability that a random Positive Integer $\leq n$ is $k$-smooth is $\psi(n,k)/n$, where $\psi(n,k)$ is the number of $k$-smooth numbers $\leq n$. This fact is important in application of Kraitchik's extension of Fermat's Factorization Method because it is related to the number of random numbers which must be examined to find a suitable subset whose product is a square.

Since about $\pi(k)$ $k$-smooth numbers must be found (where $\pi(k)$ is the Prime Counting Function), the number of random numbers which must be examined is about $\pi(k)n/\psi(n,k)$. But because it takes about $\pi(k)$ steps to determine if a number is $k$-smooth using Trial Division, the expected number of steps needed to find a subset of numbers whose product is a square is $\sim [\pi(k)]^2n/\psi(n,k)$ (Pomerance 1996). Canfield et al. (1983) showed that this function is minimized when

$$k\sim \mathop{\rm exp}\nolimits ({\textstyle{1\over 2}}\sqrt{\ln n\ln\ln n}\,)$$

and that the minimum value is about

$$\mathop{\rm exp}\nolimits (2\sqrt{\ln n\ln\ln n}\,).$$

In the Continued Fraction Factorization Algorithm, $n$ can be taken as $2\sqrt{n}$, but in Fermat's Factorization Method, it is $n^{1/2+\epsilon}$. $k$ is an estimate for the largest Prime in the Factor Base (Pomerance 1996).

References

Canfield, E. R.; Erdös, P.; and Pomerance, C. ``On a Problem of Oppenheim Concerning `Factorisation Numerorum.''' J. Number Th. 17, 1-28, 1983.

Pomerance, C. ``On the Role of Smooth Numbers in Number Theoretic Algorithms.'' In Proc. Internat. Congr. Math., Zürich, Switzerland, 1994, Vol. 1 (Ed. S. D. Chatterji). Basel: Birkhäuser, pp. 411-422, 1995.

Pomerance, C. ``A Tale of Two Sieves.'' Not. Amer. Math. Soc. 43, 1473-1485, 1996.