[3] Smooth numbers are especially important in cryptography, which relies on factorization of integers.
A positive integer is called B-smooth if none of its prime factors are greater than B.
This definition includes numbers that lack some of the smaller prime factors; for example, both 10 and 12 are 5-smooth, even though they miss out the prime factors 3 and 5, respectively.
All 5-smooth numbers are of the form 2a × 3b × 5c, where a, b and c are non-negative integers.
Here, note that B itself is not required to appear among the factors of a B-smooth number.
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 the fast Fourier transform (FFT) algorithms (such as the Cooley–Tukey FFT algorithm), which operates 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.
5-smooth or regular numbers play a special role in Babylonian mathematics.
[8] They are also important in music theory (see Limit (music)),[9] and the problem of generating these numbers efficiently has been used as a test problem for functional programming.
[11] While most applications center around cryptanalysis (e.g. the fastest known integer factorization algorithms, for example: the general number field sieve), the VSH hash function is another example of a constructive use of smoothness to obtain a provably secure design.
denote the number of y-smooth integers less than or equal to x (the de Bruijn function).
If the smoothness bound B is fixed and small, there is a good estimate for
denotes the number of primes less than or equal to
-smooth part of a random integer less than or equal to
[12] Further, m is called n-powersmooth (or n-ultrafriable) if all prime powers
dividing m satisfy: For example, 720 (24 × 32 × 51) is 5-smooth but not 5-powersmooth (because there are several prime powers greater than 5, e.g.
It is 16-powersmooth since its greatest prime factor power is 24 = 16.
Such applications are often said to work with "smooth numbers," with no n specified; this means the numbers involved must be n-powersmooth, for some unspecified small number n. As n increases, the performance of the algorithm or method in question degrades rapidly.
For example, the Pohlig–Hellman algorithm for computing discrete logarithms has a running time of O(n1/2)—for groups of n-smooth order.
Note the set A does not have to be a set of prime factors, but it is typically a proper subset of the primes as seen in the factor base of Dixon's factorization method and the quadratic sieve.
Likewise, it is what the general number field sieve uses to build its notion of smoothness, under the homomorphism
[13] The On-Line Encyclopedia of Integer Sequences (OEIS) lists B-smooth numbers for small Bs: