## Smooth Number

An Integer is -smooth if it has no Prime Factors . The probability that a random Positive Integer is -smooth is , where is the number of -smooth numbers . 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 -smooth numbers must be found (where is the Prime Counting Function), the number of random numbers which must be examined is about . But because it takes about steps to determine if a number is -smooth using Trial Division, the expected number of steps needed to find a subset of numbers whose product is a square is (Pomerance 1996). Canfield et al. (1983) showed that this function is minimized when

and that the minimum value is about

In the Continued Fraction Factorization Algorithm, can be taken as , but in Fermat's Factorization Method, it is . 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.