Given a number x and a bound b, determine whether x is b-smooth, that is, all prime factors of x are less than or equal to b. What is a good algorithm for this problem?
Variations:
Define "almost b-smooth" to mean at most one of the prime factors is greater than b. Determine whether a given number is almost b-smooth.
Find the first few numbers after a given minimum that are (almost) b-smooth.
One can probabilistically solve these problems with the Elliptic Curve Method of factorization, going up to a B1 and number of iterations appropriate for the bound b. (Similarly Pollard rho, done before ECM.) What bounds and iterations are sufficient (for what probability of failure) for a given bound b? Are there better ways?
Not sure what these might be useful for.
No comments :
Post a Comment