Smooth number

In number theory, a n-smooth (or n-friable) number is an integer whose prime factors are all less or equal to n.[1][2][3] For example, a 7-smooth number is a number whose prime factors are all at most 7, so 49 = 7² and 15750 = 2 × 3² × 5³ × 7 are both 7-smooth, while 11 and 702 = 2 × 3³ × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman.[4] Smooth numbers are especially important in cryptography, which relies on factorization of integers. The 2-smooth numbers are just the powers of 2, while 5-smooth numbers are known as regular numbers.

Definition

A positive integer is called B-smooth if none of its prime factors is greater than B. For example, 1,620 has prime factorization 2² × 3⁴ × 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.

5-smooth numbers are also called regular numbers or Hamming numbers;[5] 7-smooth numbers are also called humble numbers,[6] and sometimes called highly composite,[7] 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.)

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

Smooth numbers have a number of applications to cryptography.[11] While most applications center around cryptanalysis (e.g. the fastest known integer factorization algorithms, for example: General number field sieve algorithm), the VSH hash function is another example of a constructive use of smoothness to obtain a provably secure design.

Distribution

Let ${\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 ${\displaystyle \Psi (x,B)}$:

${\displaystyle \Psi (x,B)\sim {\frac {1}{\pi (B)!}}\prod _{p\leq B}{\frac {\log x}{\log p}}.}$

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

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

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

where ${\displaystyle \rho (u)}$ is the Dickman function.

The average size of the smooth part of a number of given size is known as ${\displaystyle \zeta (u)}$, and it is known to decay much more slowly than ${\displaystyle \rho (u)}$.[12]

For any k, almost all natural numbers will not be k-smooth.

Powersmooth numbers

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

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

For example, 720 (2⁴ × 3² × 5¹) is 5-smooth but not 5-powersmooth (because there are several prime powers greater than 5, e.g. ${\displaystyle 3^{2}=9\nleq 5}$ and ${\displaystyle 2^{4}=16\nleq 5}$). It is 16-powersmooth since its greatest prime factor power is 2⁴ = 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 and ECM. 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(B^1/2)—for groups of B-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₁ = {4, 3}, A₂ = {2, 3}, and ${\displaystyle \mathbb {Z} }$, however it would not be smooth over the set A₃ = {3, 5}, as 12 contains the factor 4 = 2², which is not in A₃.

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 ${\displaystyle \phi$ :\mathbb {Z} [\theta ]\to \mathbb {Z} /n\mathbb {Z} } .[13]

See also

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

Notes and references

1. "The Definitive Glossary of Higher Mathematical Jargon — Smooth". Math Vault. 2019-08-01. Retrieved 2019-12-12.
2. "P-Smooth Numbers or P-friable Number". GeeksforGeeks. 2018-02-12. Retrieved 2019-12-12.
3. Weisstein, Eric W. "Smooth Number". mathworld.wolfram.com. Retrieved 2019-12-12.
4. Hellman, M. E.; Reyneri, J. M. (1983). Fast computation of discrete logarithms in GF (q). Advances in Cryptology: Proceedings of CRYPTO '82 (Eds. D. Chaum, R. Rivest, A. Sherman). pp. 3–13. doi:10.1007/978-1-4757-0602-4_1. ISBN 978-1-4757-0604-8.
5. "Python: Get the Hamming numbers upto a given numbers also check whether a given number is an Hamming number". w3resource. Retrieved 2019-12-12.
6. "Problem H: Humble Numbers". www.eecs.qmul.ac.uk. Retrieved 2019-12-12.
7. Sloane, N. J. A. (ed.). "Sequence A002473 (7-smooth numbers)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
8. 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, JSTOR 1359089, MR 0191779, S2CID 164195082.
9. Longuet-Higgins, H. C. (1962), "Letter to a musical friend", Music Review (August): 244–248.
10. Dijkstra, Edsger W. (1981), Hamming's exercise in SASL (PDF), Report EWD792. Originally a privately circulated handwritten note.
11. Naccache, David; Shparlinski, Igor (17 October 2008). "Divisibility, Smoothness and Cryptographic Applications" (PDF). eprint.iacr.org. Retrieved 26 July 2017.f
12. Tanaka, Keisuke; Suga, Yuji (20 August 2015). Advances in Information and Computer Security: 10th International Workshop on Security, IWSEC 2015, Nara, Japan, August 26-28, 2015, Proceedings. Springer. pp. 49–51. ISBN 9783319224251.
13. Briggs, Matthew E. (17 April 1998). "An Introduction to the General Number Field Sieve" (PDF). math.vt.edu. Blacksburg, Virginia: Virginia Polytechnic Institute and State University. Retrieved 26 July 2017.

Bibliography

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

External links

• Weisstein, Eric W. "Smooth Number". MathWorld.

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

• 2-smooth numbers: A000079 (2ⁱ)
• 3-smooth numbers: A003586 (2ⁱ3^j)
• 5-smooth numbers: A051037 (2ⁱ3^j5^k)
• 7-smooth numbers: A002473 (2ⁱ3^j5^k7^l)
• 11-smooth numbers: A051038 (etc...)
• 13-smooth numbers: A080197
• 17-smooth numbers: A080681
• 19-smooth numbers: A080682
• 23-smooth numbers: A080683