View source for Smooth number

In [[number theory]], a '''smooth (or friable) number''' is an [[integer]] which [[integer factorization|factors]] completely into small [[prime number]]s. For example, a 7-smooth number is a number whose prime factors are all at most 7, so 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. The term seems to have been coined by [[Leonard Adleman]].<ref>{{cite book|first1=M. E.|last1=Hellman|authorlink1=Martin Hellman|first2=J. M.|last2=Reyneri|title=Fast computation of discrete logarithms in ''GF'' (q)|journal=Advances in Cryptology: Proceedings of CRYPTO '82 (eds. D. Chaum, R. Rivest, A. Sherman)| 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]] relying on factorization. The 2-smooth numbers are just the [[Power of two|powers of 2]], while 5-smooth numbers are known as [[regular number]]s.

==Definition==
A [[negative and positive numbers|positive]] [[integer]] is called <var>B</var>-'''smooth''' if none of its [[prime factor]]s is 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.

5-smooth numbers are also called ''[[regular number]]s'' or ''Hamming numbers''; 7-smooth numbers are also called '''''humble numbers''''', and sometimes called ''highly composite'',<ref>{{Cite OEIS|A002473|name=7-smooth numbers}}</ref> although this conflicts with another meaning of [[highly composite numbers]].

Note that <var>B</var> itself is not required to appear among the factors of a B-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>. Usually <var>B</var> is 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 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 number]]s play a special role in [[Babylonian mathematics]].<ref>{{citation
 | authorlink = Aaboe
 | last = Aaboe | first = Asger
 | 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 }}.</ref> They are also important in [[music theory]],<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> (see [[Limit (music)]]) and the problem of generating these numbers efficiently has been used as a test problem for [[functional programming]].<ref>{{citation
 | authorlink = 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|accessdate=26 July 2017}}f</ref>  Although most applications involve [[cryptanalysis]] (e.g. the fastest known [[integer factorization]] algorithms), the [[Very smooth hash|VSH]] hash function is one 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>\scriptstyle{\pi(B)}</math> denotes the number of primes less than or equal to <math>\scriptstyle B</math>.

Otherwise, define the parameter ''u'' as ''u'' = log&nbsp;''x''&nbsp;/&nbsp;log&nbsp;''y'': that is, ''x'' = ''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]].

The average size of the smooth part of a number of given size is known as <math>\zeta(u)</math> and it is known to decay much more slowly than <math>\rho(u)</math>.<ref>{{Cite book|url=https://books.google.com/?id=BatnCgAAQBAJ&pg=PA49&lpg=PA49&dq=average+smooth+part+integer#v=onepage&q=average%20smooth%20part%20integer&f=false|title=Advances in Information and Computer Security: 10th International Workshop on Security, IWSEC 2015, Nara, Japan, August 26-28, 2015, Proceedings|last=Tanaka|first=Keisuke|last2=Suga|first2=Yuji|date=20 August 2015|publisher=Springer|isbn=9783319224251|location=|pages=49–51|language=en|via=}}</ref>

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

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

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

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

For example, 720 (2<sup>4</sup>3<sup>2</sup>5<sup>1</sup>) is 5-smooth but is 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> = 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 &minus; 1 algorithm|Pollard's ''p''&nbsp;&minus;&nbsp;1 algorithm]] and [[Lenstra elliptic-curve factorization|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 logarithm]]s has a running time of [[asymptotic notation|O]](''B''<sup>1/2</sup>) for [[group (mathematics)|group]]s 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, 12=4*3, '''12''' is smooth over sets such as '''A'''<sub>1</sub>={4,3}, '''A'''<sub>2</sub>={2,3}, and <math>\mathbb{Z}</math>; however it would not be smooth over the set '''A'''<sub>3</sub>={3,5} as 12 contains the factor 4 or 2<sup>2</sup> which is not 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>\phi:\mathbb{Z}[\theta]\to\mathbb{Z}/n\mathbb{Z}</math>.<ref>{{cite web|url=https://www.math.vt.edu/people/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|accessdate=26 July 2017}}</ref>

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

==Notes==
<references/>

==References==
* 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]]