Smooth number

In number theory, a smooth (or friable) number is an integer which factors completely into small prime numbers. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography relying on factorization. The 2-smooth numbers are just the powers of 2.

A positive integer is called B-smooth if none of its prime factors is greater than B. For example, 1,620 has prime factorization 2² × 3⁴ × 5; therefore 1,620 is 5-smooth because none of its prime factors are greater than 5. This definition includes numbers that lack some of the smaller prime factors; for example, both 10 and 12 are 5-smooth, despite the fact that they miss out prime factors 3 and 5 respectively. 5-smooth numbers are also called regular numbers or Hamming numbers; 7-smooth numbers are also called humble, and sometimes called highly composite, although this conflicts with another meaning of highly composite numbers.

Note that B does not have to be a prime factor. If the largest prime factor of a number is p then the number is B-smooth for any B ≥ p. Usually B is given as a prime, but composite numbers work as well. A number is B-smooth if and only if it is p-smooth, where p is the largest prime less than or equal to B.

An important practical application of smooth numbers is for fast Fourier transform (FFT) algorithms such as the Cooley–Tukey FFT algorithm that operate by recursively breaking down a problem of a given size n into problems the size of its factors. By using B-smooth numbers, one ensures that the base cases of this recursion are small primes, for which efficient algorithms exist. (Large prime sizes require less-efficient algorithms such as Bluestein's FFT algorithm.)

...
Wikipedia