8 Jun 2010 @ 05:40, by John Grieve
Number #/ Music/ Pythagorean
Smooth number
From Wikipedia, the free encyclopediaJump to:navigation, search
In number theory, a smooth number is an integer which factors completely into small prime numbers; the term seems coined by Leonard Adleman.[1] Smooth numbers are especially important in cryptography relying on factorization.
Contents [hide]
1 Definition
2 Applications
3 Distribution
4 Powersmooth numbers
5 See also
6 Notes
7 References
8 External links
[edit] Definition
A positive integer is called B-smooth if none of its prime factors are greater than B. For example, 1,620 has prime factorization 22 × 34 × 5; therefore 1,620 is 5-smooth because none of its prime factors are greater than 5. 5-smooth numbers are also called regular numbers or Hamming numbers; 7-smooth numbers are sometimes called highly composite, although this conflicts with another meaning of that term.
Note that B does not have to be a prime factor. If the largest prime factor of a number is p then the number is B-smooth for any B ≥ p. Usually B is given as a prime, but composite numbers work 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.
[edit] 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 numbers play a special role in Babylonian mathematics.[2] They are also important in music theory,[3] and the problem of generating these numbers efficiently has been used as a test problem for functional programming.[4]
[edit] Distribution
Let denote the de Bruijn function, the number of y-smooth integers less than or equal to x.
If the smoothness bound B is fixed and small, there is a good estimate for :
Otherwise, define the parameter u as u = log x / log y: that is, x = yu. Then we have
where is the Dickman–de Bruijn function.
[edit] Powersmooth numbers
Further, m is called B-powersmooth if all prime powers dividing m satisfy:
For example, 243251 is 16-powersmooth since its greatest prime factor power is 24 = 16. The number is also 17-powersmooth, 18-powersmooth, 19-powersmooth, etc.
B-smooth and B-powersmooth numbers have applications in number theory, such as in Pollard's p − 1 algorithm. Such applications are often said to work with "smooth numbers," with no B specified; this means the numbers involved must be B-smooth 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(B1/2) for groups of B-smooth order.
[edit] See also
Rough number
Størmer's theorem
[edit] Notes
1.^ M. E. Hellman, J. M. Reyneri, "Fast computation of discrete logarithms in GF (q)", in Advances in Cryptology: Proceedings of CRYPTO '82 (eds. D. Chaum, R. Rivest, A. Sherman), New York: Plenum Press, 1983, p. 3–13, online quote at Google Scholar: "Adleman refers to integers which factor completely into small primes as “smooth” numbers."
2.^ 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, MR0191779 .
3.^ Longuet-Higgins, H. C. (1962), "Letter to a musical friend", Music Review (August): 244–248 .
4.^ Dijkstra, Edsger W. (1981), Hamming's exercise in SASL, Report EWD792. Originally a privately-circulated handwitten note, [link] .
[edit] References
G. Tenenbaum, Introduction to analytic and probabilistic number theory, (CUP, 1995) ISBN 0-521-41261-7
A. Granville, Smooth numbers: Computational number theory and beyond, Proc. of MSRI workshop, 2004
[edit] External links
Weisstein, Eric W., "Smooth Number" from MathWorld.
The On-Line Encyclopedia of Integer Sequences (OEIS) lists B-smooth numbers for small B's:
2-smooth numbers: A000079 (2i)
3-smooth numbers: A003586 (2i3j)
5-smooth numbers: A051037 (2i3j5k)
7-smooth numbers: A002473 (2i3j5k7l)
11-smooth numbers: A051038 (etc...)
13-smooth numbers: A080197
17-smooth numbers: A080681
19-smooth numbers: A080682
23-smooth numbers: A080683
[show]v • d • eDivisibility-based sets of integers
Overview Integer factorization · Divisor · Unitary divisor · Divisor function · Prime factor · Fundamental theorem of arithmetic
Forms of factorization Prime number · Composite number · Semiprime number · Pronic number · Sphenic number · Square-free number · Powerful number · Perfect power · Achilles number · Smooth number · Regular number · Rough number · Unusual number
Constrained divisor sums Perfect number · Almost perfect number · Quasiperfect number · Multiply perfect number · Hyperperfect number · Superperfect number · Unitary perfect number · Semiperfect number · Primitive semiperfect number · Practical number
Numbers with many divisors Abundant number · Primitive abundant number · Highly abundant number · Superabundant number · Colossally abundant number · Highly composite number · Superior highly composite number · Weird number
Numbers related
to aliquot sequences Untouchable number · Amicable number · Sociable number
Other Deficient number · Friendly number · Solitary number · Sublime number · Harmonic divisor number · Frugal number · Equidigital number · Extravagant number
Retrieved from "http://en.wikipedia.org/wiki/Smooth_number"
Categories: Analytic number theory | Integer sequencesPersonal tools
New featuresLog in / create accountNamespaces
ArticleDiscussionVariantsViews
ReadEditView historyActions
Search
SearchNavigation
Main pageContentsFeatured contentCurrent eventsRandom articleInteraction
About WikipediaCommunity portalRecent changesContact WikipediaDonate to WikipediaHelpToolbox
What links hereRelated changesUpload fileSpecial pagesPermanent linkCite this page
Print/export
Create a bookDownload as PDFPrintable version
Languages
ČeskyDeutschFrançaisNederlandsPolskiThis
|
|
