In number theory, an n-smooth (or n-friable) number is an integer whose prime factors are all less than or equal to n. For example, a 7-smooth number is a number in which every prime factor is at most 7. Therefore, 49 = 72 and 15750 = 2 × 32 × 53 × 7 are both 7-smooth, while 11 and 702 = 2 × 33 × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography, which relies on factorization of integers. 2-smooth numbers are simply the powers of 2, while 5-smooth numbers are also known as regular numbers.
Definition A positive integer is called B-smooth if none of its prime factors are greater than B. For example, 1,620 has prime factorization 22 × 34 × 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, 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. The 3-smooth numbers have also been called "harmonic numbers", although that name has other more widely used meanings, most notably for the sum of the reciprocals of the natural numbers. 5-smooth numbers are also called regular numbers or Hamming numbers; 7-smooth numbers are also called humble numbers, and sometimes called highly composite, although this conflicts with another meaning of highly composite numbers. Here, note that B itself is not required to appear among the factors of a B-smooth number. If the largest prime factor of a number is p then the number is B-smooth for any B ≥ p. In many scenarios B is prime, but composite numbers are permitted 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.
Applications 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. (Large prime sizes require less-efficient algorithms such as Bluestein's FFT algorithm.) Numbers that are 5-smooth or regular numbers play a special role in Babylonian mathematics. They are also important in music theory (see Limit (music)), and the problem of generating these numbers efficiently has been used as a test problem for functional programming. Smooth numbers have a number of applications to cryptography. 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. In music, a p-limit tuning is the set of music intervals that are ratios of two p-smooth numbers.
Distribution Let Ψ ( x , y ) {\displaystyle \Psi (x,y)} 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 Ψ ( x , B ) {\displaystyle \Psi (x,B)} :
Ψ ( x , B ) ∼ 1 π ( B ) ! ∏ p ≤ B log x log p . {\displaystyle \Psi (x,B)\sim {\frac {1}{\pi (B)!}}\prod _{p\leq B}{\frac {\log x}{\log p}}.}
where π ( B ) {\displaystyle \pi (B)} denotes the number of primes less than or equal to B {\displaystyle B} . Otherwise, define the parameter u as u = log x / log y: that is, x = yu. Then,
Ψ ( x , y ) = x ⋅ ρ ( u ) + O ( x log y ) {\displaystyle \Psi (x,y)=x\cdot \rho (u)+O\left({\frac {x}{\log y}}\right)}
where ρ ( u ) {\displaystyle \rho (u)} is the Dickman function. For any k, almost all natural numbers will not be k-smooth. If n = n 1 n 2 {\displaystyle n=n_{1}n_{2}} where n 1 {\displaystyle n_{1}} is B {\displaystyle B} -smooth and n 2 {\displaystyle n_{2}} is not (or is equal to 1), then n 1 {\displaystyle n_{1}} is called the B {\displaystyle B} -smooth part of n {\displaystyle n} . The relative size of the x 1 / u {\displaystyle x^{1/u}} -smooth part of a random integer less than or equal to x {\displaystyle x} is known to decay much more slowly than ρ ( u ) {\displaystyle \rho (u)} .
… excerpt ends here. Continue reading the full article.
