Smooth number

Uses your system voice; voice and rate in settings.

Snapshot

≈ 7 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 = 7 2 and 15750 = 2 × 3 2 × 5 3 × 7 are both 7-smooth, while 11 and 702 = 2 × 3 3 × 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.

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 = 7 2 and 15750 = 2 × 3 2 × 5 3 × 7 are both 7-smooth, while 11 and 702 = 2 × 3 3 × 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 2 2 × 3 4 × 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 2 a × 3 b × 5 c , 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 .

Distribution

Let \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 \Psi(x,B) : \Psi(x,B) \sim \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p}. where \pi(B) denotes the number of primes less than or equal to B . Otherwise, define the parameter u as u = log x / log y: that is, x = y u . Then, \Psi(x,y) = x\cdot \rho(u) + O\left(\frac{x}{\log y}\right) where \rho(u) is the Dickman function. For any k, almost all natural numbers will not be k-smooth. If n=n_1 n_2 where n_1 is B -smooth and n_2 is not (or is equal to 1), then n_1 is called the B -smooth part of n . The relative size of the x^{1/u} -smooth part of a random integer less than or equal to x is known to decay much more slowly than \rho(u) .

Powersmooth numbers

Further, m is called n-powersmooth (or n-ultrafriable) if all prime powers p^{\nu} dividing m satisfy: p^{\nu} \leq n.\, For example, 720 (2 4 × 3 2 × 5 1 ) is 5-smooth but not 5-powersmooth (because there are several prime powers greater than 5, e.g. 3^2 = 9 \nleq 5 and 2^4 = 16 \nleq 5 ). It is 16-powersmooth since its greatest prime factor power is 2 4 = 16. The number is also 17-powersmooth, 18-powersmooth, etc. Unlike n-smooth numbers, for any positive integer n there are only finitely many n-powersmooth numbers.

In fact, the n-powersmooth numbers are exactly the positive divisors of “the least common multiple of 1, 2, 3, …, n” , e.g. the 9-powersmooth numbers (also the 10-powersmooth numbers) are exactly the positive divisors of 2520. n-smooth and n-powersmooth numbers have applications in number theory, such as in Pocklington n − 1 primality test and Morrison n + 1 primality test and ECPP and Pollard's p − 1 algorithm and Williams's p + 1 algorithm and ECM.

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(n 1/2 )—for groups of n-smooth order.

Smooth over a set A

Moreover, m is said to be smooth over a set A if there exists a factorization of m where the factors are powers of elements in A. For example, since 12 = 4 × 3, 12 is smooth over the sets A 1 = {4, 3}, A 2 = {2, 3}, and \mathbb{Z} , however it would not be smooth over the set A 3 = {3, 5}, as 12 contains the factor 4 = 2 2 , and neither 4 nor 2 are in A 3 . 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 \varphi:\mathbb{Z}[\theta]\to\mathbb{Z}/n\mathbb{Z} .

See also

Highly composite number Rough number Round number Størmer's theorem Unusual number

Notes and references

Bibliography

G. Tenenbaum, Introduction to analytic and probabilistic number theory, (AMS, 2015) A. Granville, Smooth numbers: Computational number theory and beyond, Proc. of MSRI workshop, 2008

External links

The On-Line Encyclopedia of Integer Sequences (OEIS) lists B-smooth numbers for small Bs: 2-smooth numbers: A000079 (2 i ) 3-smooth numbers: A003586 (2 i 3 j ) 5-smooth numbers: A051037 (2 i 3 j 5 k ) 7-smooth numbers: A002473 (2 i 3 j 5 k 7 l ) 11-smooth numbers: A051038 (etc...) 13-smooth numbers: A080197 17-smooth numbers: A080681 19-smooth numbers: A080682 23-smooth numbers: A080683

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374971635 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001374971635 · captured 1789433987.0 · version history

Cite this page as: encyclopegia.org, “Smooth number”, snapshot enwiki-001374971635. https://encyclopegia.org/a/smooth-number

Sources cited in this revision

7 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.