Smooth number

In number theory, a smooth (or friable) number is an integer which factors completely into small prime numbers. The term seems to have been coined by Leonard Adleman.^[1] Smooth numbers are especially important in cryptography relying on factorization. The 2-smooth numbers are just the powers of 2.

Definition

A positive integer is called B-smooth if none of its prime factors is greater than B. For example, 1,620 has prime factorization 2² × 3⁴ × 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, despite the fact that they miss out prime factors 3 and 5 respectively. 5-smooth numbers are also called regular numbers or Hamming numbers; 7-smooth numbers are also called humble, and sometimes called highly composite,^[2] although this conflicts with another meaning of highly composite numbers.

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.

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.^[3] They are also important in music theory,^[4] (see Limit (music)) and the problem of generating these numbers efficiently has been used as a test problem for functional programming.^[5]

Smooth numbers have a number of applications to cryptography.^[6] Although most applications involve cryptanalysis (e.g. the fastest known integer factorization algorithms), the VSH hash function is one example of a constructive use of smoothness to obtain a provably secure design.

Distribution

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

\Psi(x,B) \sim \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p}.

where $\scriptstyle{\pi(B)}$ denotes the number of primes less than or equal to $\scriptstyle B$ .

Otherwise, define the parameter u as u = log x / log y: that is, x = y^u. Then,

\Psi(x,y) = x\cdot \rho(u) + O\left(\frac{x}{\log y}\right)

where $\scriptstyle\rho(u)$ is the Dickman function.

Powersmooth numbers

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

p^{\nu} \leq B.\,

For example, 720 (2⁴3²5¹) is 5-smooth but is not 5-powersmooth (because there are several prime powers greater than 5, e.g., $3^2=9 \nleq 5$ or $2^3 > 5$ ). It is 16-powersmooth since its greatest prime factor power is 2⁴ = 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 − 1 algorithm. 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 logarithms has a running time of O(B^1/2) for groups of B-smooth order.

Notes

↑ 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."
↑ "Sloane's A002473 : 7-smooth numbers", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
↑ 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, MR 0191779 .
↑ Longuet-Higgins, H. C. (1962), "Letter to a musical friend", Music Review (August): 244–248 .
↑ Dijkstra, Edsger W. (1981), Hamming's exercise in SASL (PDF), Report EWD792. Originally a privately circulated handwitten note .
↑ David Naccache, Igor Shparlinski, "Divisibility, Smoothness and Cryptographic Applications", http://eprint.iacr.org/2008/437.pdf

References

G. Tenenbaum, Introduction to analytic and probabilistic number theory, (AMS, 2015) ISBN 978-0821898543
A. Granville, Smooth numbers: Computational number theory and beyond, Proc. of MSRI workshop, 2008

External links

Weisstein, Eric W., "Smooth Number", MathWorld.

The On-Line Encyclopedia of Integer Sequences (OEIS) lists B-smooth numbers for small Bs:

2-smooth numbers: A000079 (2ⁱ)
3-smooth numbers: A003586 (2ⁱ3^j)
5-smooth numbers: A051037 (2ⁱ3^j5^k)
7-smooth numbers: A002473 (2ⁱ3^j5^k7^l)
11-smooth numbers: A051038 (etc...)
13-smooth numbers: A080197
17-smooth numbers: A080681
19-smooth numbers: A080682
23-smooth numbers: A080683

Divisibility-based sets of integers

Overview	Integer factorization Divisor Unitary divisor Divisor function Prime factor Fundamental theorem of arithmetic Arithmetic number

Factorization forms	Prime Composite Semiprime Pronic Sphenic Square-free Powerful Perfect power Achilles Smooth Regular Rough Unusual

Constrained divisor sums	Perfect Almost perfect Quasiperfect Multiply perfect Hemiperfect Hyperperfect Superperfect Unitary perfect Semiperfect Practical Erdős–Nicolas

With many divisors	Abundant Primitive abundant Highly abundant Superabundant Colossally abundant Highly composite Superior highly composite Weird

Aliquot sequence-related	Untouchable Amicable Sociable Betrothed

Other sets	Deficient Friendly Solitary Sublime Harmonic divisor Frugal Equidigital Extravagant

Classes of natural numbers

Powers and
related numbers

Of the form
a × 2^b ± 1

Other polynomial
numbers

Recursively defined
numbers

Possessing a
specific set
of other numbers

Expressible via
specific sums

Generated
via a sieve

Lucky

Code related

Meertens

Figurate numbers

2-dimensional

centered	Centered triangular Centered square Centered pentagonal Centered hexagonal Centered heptagonal Centered octagonal Centered nonagonal Centered decagonal Star

non-centered	Triangular Square Square triangular Pentagonal Hexagonal Heptagonal Octagonal Nonagonal Decagonal Dodecagonal

3-dimensional

centered	Centered tetrahedral Centered cube Centered octahedral Centered dodecahedral Centered icosahedral

non-centered	Tetrahedral Octahedral Dodecahedral Icosahedral Stella octangula

pyramidal	Square pyramidal Pentagonal pyramidal Hexagonal pyramidal Heptagonal pyramidal

4-dimensional

centered	Centered pentachoric Squared triangular

non-centered	Pentatope

Pseudoprimes

Combinatorial
numbers

Arithmetic functions

By properties of σ(n)	Abundant Almost perfect Arithmetic Colossally abundant Descartes Hemiperfect Highly abundant Highly composite Hyperperfect Multiply perfect Perfect Practical number Primitive abundant Quasiperfect Refactorable Sublime Superabundant Superior highly composite Superperfect

By properties of Ω(n)	Almost prime Semiprime

By properties of φ(n)	Highly cototient Highly totient Noncototient Nontotient Perfect totient Sparsely totient

By properties of s(n)	Amicable Betrothed Deficient Semiperfect

Dividing a quotient

Other prime factor
or divisor related
numbers

Recreational
mathematics

Base-dependent
numbers

This article is issued from Wikipedia - version of the Thursday, November 26, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.