![]() ![]() ![]() ![]() |
![]() ![]() ![]() ![]() |
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
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.