Smooth number

Encyclopedia : S : SM : SMO : Smooth number

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

Powersmooth numbers

Further, m is called B-powersmooth if all prime powers [p_i^] dividing m satisfy:

[p_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.

External links

The On-Line Encyclopedia of Integer Sequences (OEIS) lists B-smooth numbers for small B's:

2-smooth numbers: [[OEIS:A000079|A000079]] (2ⁱ)
3-smooth numbers: [[OEIS:A003586|A003586]] (2ⁱ3^j)
5-smooth numbers: [[OEIS:A051037|A051037]] (2ⁱ3^j5^k)
7-smooth numbers: [[OEIS:A002473|A002473]] (2ⁱ3^j5^k7^l)
11-smooth numbers: [[OEIS:A051038|A51038]] (etc...)
13-smooth numbers: [[OEIS:A080197|A80197]]
17-smooth numbers: [[OEIS:A080681|A80681]]
19-smooth numbers: [[OEIS:A080682|A80682]]
23-smooth numbers: [[OEIS:A080683|A80683]]

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.