Smooth number

From Wikipedia, the free encyclopedia

In number theory, a positive integer m is called B-smooth if all prime factors $p i$ of m are such that

$p_i \leq B$ .

For example, 2²³3⁵⁶5⁴ is 5-smooth since none of its prime factors are greater than 5.

Obviously, a number n is B-smooth if and only if it is p-smooth, where p is the largest prime less than B.

7-smooth numbers are sometimes called highly composite (although this conflicts with another meaning of that term: see highly composite number).

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.)

1 Powersmooth numbers
2 Distribution
3 External links
4 References

[edit] Powersmooth numbers

Further, m is called B-powersmooth if all prime powers $p_i^{n_i}$ dividing m satisfy:

$p_i^{n_i} \leq B$ .

For example, 2⁴3²5¹ is 16-powersmooth since its greatest prime factor power is 2⁴ = 16. The number is also 17-powersmooth, 18-powersmooth, 19-powersmooth, etc.

B-smooth and B-powersmooth numbers have applications in number theory, such as Pollard's p-1 algorithm. Such applications are often said to work with "smooth numbers," with no B specified; this means the numbers involved must be B-smooth for some unspecified small number B; as B 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(B^1/2) for groups of B-smooth order.