Smooth number

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.[1] Smooth numbers are especially important in cryptography relying on factorization.

Definition[edit]

A positive integer is called B-smooth if none of its prime factors is 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, 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[1], although this conflicts with another meaning of that term.

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

Applications[edit]

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

5-smooth or regular numbers play a special role in Babylonian mathematics.[2] They are also important in music theory,[3] (see Limit (music)) and the problem of generating these numbers efficiently has been used as a test problem for functional programming.[4]

Smooth numbers have a number of applications to cryptography.[5] Although most applications involve cryptanalysis (e.g. the fastest known integer factorization algorithms), the VSH hash function is one example of a constructive use of smoothness to obtain a provably secure design.

Distribution[edit]

Let \scriptstyle \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 \scriptstyle\Psi(x,B):

 \Psi(x,B) \sim  \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p}.

where \scriptstyle{\pi(B)} denotes the number of primes less than or equal to \scriptstyle B.

Otherwise, define the parameter u as u = log x / log y: that is, x = yu. Then,

 \Psi(x,y) = x\cdot \rho(u) + O\left(\frac{x}{\log y}\right)

where \scriptstyle\rho(u) is the Dickman function.

Powersmooth numbers[edit]

Further, m is called B-powersmooth (or B-ultrafriable) if all prime powers \scriptstyle p^{\nu} dividing m satisfy:

p^{\nu} \leq B.\,

For example, 243251 is 5-smooth but is not 5-powersmooth (because there are several prime powers greater than 5, e.g., 3^2=9 \nleq 5 or 2^3 > 5). It is 16-powersmooth since its greatest prime factor power is 24 = 16. The number is also 17-powersmooth, 18-powersmooth, etc.

B-smooth and B-powersmooth numbers have applications in number theory, such as in 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-powersmooth 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(B1/2) for groups of B-smooth order.

See also[edit]

Notes[edit]

  1. ^ M. E. Hellman, J. M. Reyneri, "Fast computation of discrete logarithms in GF (q)", in Advances in Cryptology: Proceedings of CRYPTO '82 (eds. D. Chaum, R. Rivest, A. Sherman), New York: Plenum Press, 1983, p. 3–13, online quote at Google Scholar: "Adleman refers to integers which factor completely into small primes as “smooth” numbers."
  2. ^ Aaboe, Asger (1965), "Some Seleucid mathematical tables (extended reciprocals and squares of regular numbers)", Journal of Cuneiform Studies 19 (3): 79–86, doi:10.2307/1359089, MR 0191779 .
  3. ^ Longuet-Higgins, H. C. (1962), "Letter to a musical friend", Music Review (August): 244–248 .
  4. ^ Dijkstra, Edsger W. (1981), Hamming's exercise in SASL, Report EWD792. Originally a privately circulated handwitten note .
  5. ^ David Naccache, Igor Shparlinski, "Divisibility, Smoothness and Cryptographic Applications", http://eprint.iacr.org/2008/437.pdf

References[edit]

External links[edit]

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