Editing Smooth number (section)

==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>