Editing Smooth number (section)

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