Editing Smooth number

{{Short description|Integer having only small prime factors}}
In [[number theory]], an '''''n''-smooth''' (or '''''n''-friable''') '''number''' is an [[integer]] whose [[prime factors]] are all less than or equal to ''n''.<ref>{{Cite web|url=https://www.geeksforgeeks.org/p-smooth-numbers-p-friable-number/|title=P-Smooth Numbers or P-friable Number|date=2018-02-12|website=GeeksforGeeks|language=en-US|access-date=2019-12-12}}</ref><ref>{{Cite web|url=http://mathworld.wolfram.com/SmoothNumber.html|title=Smooth Number|last=Weisstein|first=Eric W.|website=mathworld.wolfram.com|language=en|access-date=2019-12-12}}</ref> For example, a 7-smooth number is a number in which every prime factor is at most 7. Therefore, 49 = 7<sup>2</sup> and 15750 = 2 × 3<sup>2</sup> × 5<sup>3</sup> × 7 are both 7-smooth, while 11 and 702 = 2 × 3<sup>3</sup> × 13 are not 7-smooth. The term seems to have been coined by [[Leonard Adleman]].<ref>{{cite book|first1=M. E.|last1=Hellman|author-link1=Martin Hellman|first2=J. M.|last2=Reyneri |title=Advances in Cryptology – Proceedings of Crypto 82|chapter=Fast Computation of Discrete Logarithms in ''GF'' (''q'') | year=1983|pages=3–13|doi=10.1007/978-1-4757-0602-4_1|isbn=978-1-4757-0604-8}}</ref> Smooth numbers are especially important in [[cryptography]], which relies on factorization of integers. 2-smooth numbers are simply the [[Power of two|powers of 2]], while 5-smooth numbers are also known as [[regular numbers]].

==Definition==
A [[negative and positive numbers|positive]] [[integer]] is called <var>B</var>-'''smooth''' if none of its [[prime factor]]s are greater than <var>B</var>. For example, 1,620 has prime factorization 2<sup>2</sup> × 3<sup>4</sup> × 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<sup>''a''</sup> × 3<sup>''b''</sup> × 5<sup>''c''</sup>, 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.<ref>{{cite OEIS|A003586|3-smooth numbers}}</ref>
5-smooth numbers are also called [[regular number|'''regular numbers''']] or Hamming numbers;<ref>{{Cite web|url=https://www.w3resource.com/python-exercises/challenges/1/python-challenges-1-exercise-25.php|title=Python: Get the Hamming numbers upto a given numbers also check whether a given number is an Hamming number|website=w3resource|language=en|access-date=2019-12-12}}</ref> 7-smooth numbers are also called '''humble numbers''',<ref>{{Cite web|url=https://www.eecs.qmul.ac.uk/~pbo/ACM/archive/00001.html|title=Problem H: Humble Numbers|website=www.eecs.qmul.ac.uk|access-date=2019-12-12}}</ref> and sometimes called ''highly composite'',<ref>{{Cite OEIS|A002473|name=7-smooth numbers}}</ref> although this conflicts with another meaning of [[highly composite numbers]].

Here, note that <var>B</var> itself is not required to appear among the factors of a <var>B</var>-smooth number. If the largest prime factor of a number is <var>p</var> then the number is <var>B</var>-smooth for any <var>B</var> ≥ <var>p</var>. In many scenarios <var>B</var> is [[Prime number|prime]], but [[composite number]]s are permitted as well. A number is <var>B</var>-smooth [[if and only if]] it is <var>p</var>-smooth, where <var>p</var> is the largest prime less than or equal to <var>B</var>.

== 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 number]]s play a special role in [[Babylonian mathematics]].<ref>
{{citation
 | last = Aaboe | first = Asger | author-link = Aaboe
 | title = Some Seleucid mathematical tables (extended reciprocals and squares of regular numbers)
 | journal = Journal of Cuneiform Studies
 | volume = 19
 | issue = 3
 | pages = 79–86
 | year = 1965
 | mr=0191779
 | doi = 10.2307/1359089| jstor = 1359089 | s2cid = 164195082
}}.</ref> They are also important in [[music theory]] (see [[Limit (music)]]),<ref>
{{citation
 | last = Longuet-Higgins | first = H. C.
 | year = 1962
 | title = Letter to a musical friend
 | journal = Music Review
 | issue = August
 | pages = 244–248
}}.</ref> and the problem of generating these numbers efficiently has been used as a test problem for [[functional programming]].<ref>
{{citation
 | author-link = Edsger W. Dijkstra | last = Dijkstra | first = Edsger W.
 | title = Hamming's exercise in SASL
 | year = 1981
 | url = http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF
 | id = Report EWD792. Originally a privately circulated handwritten note
}}.</ref>

Smooth numbers have a number of applications to cryptography.<ref>{{cite journal|first1=David|last1=Naccache|first2=Igor |last2=Shparlinski|title=Divisibility, Smoothness and Cryptographic Applications|url=http://eprint.iacr.org/2008/437.pdf|date=17 October 2008|website=eprint.iacr.org|arxiv=0810.2067 |access-date=26 July 2017}}f</ref> While most applications center around [[cryptanalysis]] (e.g. the fastest known [[integer factorization]] algorithms, for example: the [[general number field sieve]]), the [[Very smooth hash|VSH]] hash function is another example of a constructive use of smoothness to obtain a [[Provably secure cryptographic hash function|provably secure design]].

==Distribution==

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

:<math> \Psi(x,B) \sim  \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p}. </math>
 
where <math>\pi(B)</math> denotes [[Prime-counting function|the number of primes less than or equal to]] <math>B</math>.

Otherwise, define the parameter ''u'' as ''u''&thinsp;=&thinsp;log&thinsp;''x''&nbsp;/&nbsp;log&thinsp;''y'': that is, ''x''&thinsp;=&thinsp;''y''<sup>''u''</sup>.  Then,

:<math> \Psi(x,y) = x\cdot \rho(u) + O\left(\frac{x}{\log y}\right)</math>

where <math>\rho(u)</math> is the [[Dickman function]].

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

If <math>n=n_1 n_2</math> where <math>n_1</math> is <math>B</math>-smooth and <math>n_2</math> is not (or is equal to 1), then <math>n_1</math> is called the <math>B</math>-smooth part of <math>n</math>. The relative size of the <math>x^{1/u}</math>-smooth part of a random integer less than or equal to <math>x</math> is known to decay much more slowly than <math>\rho(u)</math>.<ref>{{cite conference
 | last1 = Kim | first1 = Taechan
 | last2 = Tibouchi | first2 = Mehdi
 | editor1-last = Tanaka | editor1-first = Keisuke
 | editor2-last = Suga | editor2-first = Yuji
 | contribution = Invalid Curve Attacks in a GLS Setting
 | doi = 10.1007/978-3-319-22425-1_3
 | pages = 41–55
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Advances in Information and Computer Security – 10th International Workshop on Security, IWSEC 2015, Nara, Japan, August 26–28, 2015, Proceedings
 | volume = 9241
 | year = 2015| isbn = 978-3-319-22424-4
 }}</ref>

==Powersmooth numbers==
<!-- This section is linked from [[Table of prime factors]] -->

Further, ''m'' is called ''n''-'''powersmooth''' (or ''n''-'''ultrafriable''') if all prime ''powers'' <math>p^{\nu}</math> dividing ''m'' satisfy:

:<math>p^{\nu} \leq n.\,</math>

For example, 720 (2<sup>4</sup> × 3<sup>2</sup> × 5<sup>1</sup>) is 5-smooth but not 5-powersmooth (because there are several prime powers greater than 5,  ''e.g.'' <math>3^2 = 9 \nleq 5</math> and <math>2^4 = 16 \nleq 5</math>). It is 16-powersmooth since its greatest prime factor power is 2<sup>4</sup>&thinsp;=&thinsp;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''” {{OEIS|A003418}}, 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 [[Pollard's p − 1 algorithm|Pollard's ''p''&thinsp;−&thinsp;1 algorithm]] and [[Lenstra elliptic-curve factorization|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. A''s ''n'' increases, the performance of the algorithm or method in question degrades rapidly. For example, the [[Pohlig–Hellman algorithm]] for computing [[discrete logarithm]]s has a running time of [[asymptotic notation|O]](''n''<sup>1/2</sup>)—for [[group (mathematics)|group]]s of ''n''-smooth [[Order (group theory)|order]].

==Smooth over a set ''A''==
Moreover, ''m'' is said to be smooth over a [[Set (mathematics)|set]] ''A'' if there exists a factorization of ''m'' where the factors are powers of elements in ''A''. For example, since 12 = 4&thinsp;×&thinsp;3, 12 is smooth over the sets ''A''<sub>1</sub> = {4,&thinsp;3}, ''A''<sub>2</sub> = {2,&thinsp;3}, and <math>\mathbb{Z}</math>, however it would not be smooth over the set ''A''<sub>3</sub> = {3,&thinsp;5}, as 12 contains the factor 4 = 2<sup>2</sup>, and neither 4 nor 2 are in ''A''<sub>3</sub>.

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]] <math>\varphi:\mathbb{Z}[\theta]\to\mathbb{Z}/n\mathbb{Z}</math>.<ref>{{cite web|url=https://personal.math.vt.edu/brown/doc/briggs_gnfs_thesis.pdf|title=An Introduction to the General Number Field Sieve|first=Matthew E.|last=Briggs|publisher=Virginia Polytechnic Institute and State University|website=math.vt.edu|date=17 April 1998|location=Blacksburg, Virginia|access-date=26 July 2017}}</ref>

==See also==
*[[Highly composite number]]
*[[Rough number]]
*[[Round number]]
*[[Størmer's theorem]]
*[[Unusual number]]

==Notes and references==
<references/>

==Bibliography==
* G. Tenenbaum, ''Introduction to analytic and probabilistic number theory'', (AMS, 2015) {{isbn|978-0821898543}}
* [[A. Granville]], [http://www.dms.umontreal.ca/~andrew/PDF/msrire.pdf ''Smooth numbers: Computational number theory and beyond''], Proc. of MSRI workshop, 2008

==External links==
* {{mathworld|urlname=SmoothNumber|title=Smooth Number}}
The [[On-Line Encyclopedia of Integer Sequences]] (OEIS)
lists ''B''-smooth numbers for small ''B''s:
* 2-smooth numbers: [[OEIS:A000079|A000079]] (2<sup>''i''</sup>)
* 3-smooth numbers: [[OEIS:A003586|A003586]] (2<sup>''i''</sup>3<sup>''j''</sup>)
* 5-smooth numbers: [[OEIS:A051037|A051037]] (2<sup>''i''</sup>3<sup>''j''</sup>5<sup>''k''</sup>)
* 7-smooth numbers: [[OEIS:A002473|A002473]] (2<sup>''i''</sup>3<sup>''j''</sup>5<sup>''k''</sup>7<sup>''l''</sup>)
* 11-smooth numbers: [[OEIS:A051038|A051038]] (etc...)
* 13-smooth numbers: [[OEIS:A080197|A080197]]
* 17-smooth numbers: [[OEIS:A080681|A080681]]
* 19-smooth numbers: [[OEIS:A080682|A080682]]
* 23-smooth numbers: [[OEIS:A080683|A080683]]

{{Divisor classes}}
{{Classes of natural numbers}}

[[Category:Analytic number theory]]
[[Category:Integer sequences]]