Smooth Number

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

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

• Chaitin's Number
• Chaitin's Omega
• Champernowne Constant
• Change of Variables Theorem
• Chaos
• Chaos Game
• Character (Group)
• Characteristic Class
• Characteristic (Elliptic Integral)
• Characteristic Equation
• Characteristic (Euler)
• Characteristic Factor
• Characteristic (Field)
• Characteristic Function
• Squareful
• Square Gyrobicupola
• Square Integrable
• Square Knot
• Square Matrix
• Square Number
• Square Orthobicupola
• Square Packing
• Square Polyomino
• Square Pyramid
• Square Pyramidal Number