Tuesday, April 14, 2020

[fwibgiza] issmooth

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 :