Hubbry Logo
search
logo
Smooth number avatar
Smooth number
Smooth number
current hub
S

Smooth number

logo
Community Hub0 Subscribers
Read side by side
Smooth number
View on Wikipedia
from Wikipedia

In number theory, an n-smooth (or n-friable) number is an integer whose prime factors are all less than or equal to n.[1][2] For example, a 7-smooth number is a number in which every prime factor is at most 7. Therefore, 49 = 72 and 15750 = 2 × 32 × 53 × 7 are both 7-smooth, while 11 and 702 = 2 × 33 × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman.[3] Smooth numbers are especially important in cryptography, which relies on factorization of integers. 2-smooth numbers are simply the powers of 2, while 5-smooth numbers are also known as regular numbers.

Definition

[edit]

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. 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 2a × 3b × 5c, where a, b and c are non-negative integers.

The 3-smooth numbers have also been called "harmonic numbers",[4] although that name has other more widely used meanings, most notably for the sum of the reciprocals of the natural numbers. 5-smooth numbers are also called regular numbers or Hamming numbers;[5] 7-smooth numbers are also called humble numbers,[6] and sometimes called highly composite,[7] although this conflicts with another meaning of highly composite numbers.

Here, note that B itself is not required to appear among the factors of a B-smooth number. If the largest prime factor of a number is p then the number is B-smooth for any B ≥ p. In many scenarios B is prime, but composite numbers are permitted 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

[edit]

An important practical application of smooth numbers is the fast Fourier transform (FFT) algorithms (such as the Cooley–Tukey FFT algorithm), which operates 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.[8] They are also important in music theory (see Limit (music)),[9] and the problem of generating these numbers efficiently has been used as a test problem for functional programming.[10]

Smooth numbers have a number of applications to cryptography.[11] While most applications center around cryptanalysis (e.g. the fastest known integer factorization algorithms, for example: the general number field sieve), the VSH hash function is another example of a constructive use of smoothness to obtain a provably secure design.

Distribution

[edit]

Let 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 :

where denotes the number of primes less than or equal to .

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

where is the Dickman function.

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

If where is -smooth and is not (or is equal to 1), then is called the -smooth part of . The relative size of the -smooth part of a random integer less than or equal to is known to decay much more slowly than .[12]

Powersmooth numbers

[edit]

Further, m is called n-powersmooth (or n-ultrafriable) if all prime powers dividing m satisfy:

For example, 720 (24 × 32 × 51) is 5-smooth but not 5-powersmooth (because there are several prime powers greater than 5, e.g. and ). It is 16-powersmooth since its greatest prime factor power is 24 = 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” (sequence A003418 in the OEIS), 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 and 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. As n 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(n1/2)—for groups of n-smooth order.

Smooth over a set A

[edit]

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, since 12 = 4 × 3, 12 is smooth over the sets A1 = {4, 3}, A2 = {2, 3}, and , however it would not be smooth over the set A3 = {3, 5}, as 12 contains the factor 4 = 22, and neither 4 nor 2 are in A3.

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 .[13]

See also

[edit]

Notes and references

[edit]

Bibliography

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Smooth number

View on Grokipedia
from Grokipedia
In number theory, a smooth number (or friable number) is a positive integer whose prime factors are all less than or equal to a given bound $ y $, meaning it is $ y $-smooth if its largest prime factor is at most $ y $.[1][2] For example, the number 14824161510814728 is 7-smooth because its only prime factors are 2 and 3.[2] The distribution of smooth numbers up to $ x $, denoted $ \Psi(x, y) $, is asymptotically approximated by $ x \rho(u) $, where $ u = \log x / \log y $ and $ \rho $ is the Dickman-de Bruijn function, which satisfies a delay differential equation and provides the probability that a random integer near $ x $ is $ y $-smooth.[3] This function originates from early 20th-century work by Karl Dickman and later refinements by Nicolaas Govert de Bruijn, with error terms improving over time to cover wider ranges of $ u $.[3] Smooth numbers play a pivotal role in computational number theory, particularly in factorization algorithms such as the quadratic sieve and the number field sieve, where identifying smooth values among residues modulo a composite enables efficient computation of relations for factoring large integers.[4][3] They also underpin primality testing methods, like the Adleman-Pomerance-Rumely test, which relies on primes $ p $ where $ p-1 $ is smooth to verify primality deterministically.[3] Beyond factoring, smooth numbers appear in applications to Waring's problem for representing numbers as sums of powers, Egyptian fraction expansions, and solving S-unit equations in algebraic number fields.[3] The term "smooth number" was coined by Ronald Rivest in the context of cryptographic algorithms, reflecting the idea of numbers without "rough" large prime factors that complicate computations.[5] Consecutive smooth numbers are rare but notable, such as 11859210 and 11859211, which are both 19-smooth.[1]

Fundamentals

Definition

In number theory, a positive integer nn is said to be BB-smooth (or yy-smooth, where y=By = B) if all of its prime factors are less than or equal to BB; equivalently, the largest prime factor of nn, denoted P(n)P(n), satisfies P(n)≤BP(n) \leq B.[1][3] The function P(n)P(n) is formally defined as P(n)=max⁡{p∣p is prime and p divides n}P(n) = \max \{ p \mid p \text{ is prime and } p \text{ divides } n \}, with the convention that P(1)=0P(1) = 0 or undefined, though 1 is considered vacuously BB-smooth for any B≥1B \geq 1 since it has no prime factors.[1] This class includes all primes p≤Bp \leq B and all finite products of such primes (with repetition allowed).[3] The term BB-smooth number is also known as a BB-friable number, where "friable" derives from the French for "crumbly," reflecting the idea of numbers composed of small prime "building blocks."[1][3] In contrast, a BB-rough number is one whose smallest prime factor is at least BB.[1] Basic examples illustrate the concept: the number 1 is BB-smooth for any BB; 30 = 2×3×52 \times 3 \times 5 is 5-smooth (since P(30)=5≤5P(30) = 5 \leq 5) but not 3-smooth (since P(30)=5>3P(30) = 5 > 3); and 12 = 22×32^2 \times 3 is 3-smooth.[1][3] The following table lists the first few positive BB-smooth numbers for small values of BB:
BBFirst few BB-smooth numbers
21, 2, 4, 8, 16, 32, ...
31, 2, 3, 4, 6, 8, 9, 12, 16, 18, ...
51, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, ...

History and Etymology

The term "smooth number" was coined by Ron Rivest in the 1970s to denote an integer whose prime factors are all relatively small, drawing an analogy to a smooth surface devoid of large "lumps" or bumps that would correspond to sizable prime factors.[5] Rivest himself confirmed this origin, stating that the term evoked the opposite of "lumpy" in reference to the absence of large primes.[5] While Leonard Adleman contributed to the underlying concepts in early cryptographic contexts and is sometimes credited alongside Rivest, the latter is affirmed as the originator of the specific terminology, despite Adleman's initial reservations about it.[5] The notion arose within computational number theory amid the rapid development of integer factorization algorithms during the 1970s, a period marked by growing interest in efficient methods for breaking composite numbers.[6] This timing aligned closely with the invention of the RSA cryptosystem in 1977 by Rivest, Adi Shamir, and Adleman, which heightened the need for analyzing numbers amenable to factoring via small primes.[6] The earliest documented uses of the term appear in the literature of the early 1980s, including a 1983 paper on discrete logarithms by Martin Hellman and John Reyneri, which explicitly attributes "smooth numbers" to Adleman in the context of algorithms requiring fully factored small-prime products. Although the precise terminology post-dates earlier mathematical investigations, the underlying idea of integers lacking large prime factors featured informally in sieve methods and distribution studies before the 1970s.[6] A key milestone was Karl Dickman's 1930 analysis of the frequency of such numbers, where he derived asymptotic proportions for integers up to xx with prime factors bounded by x1/ux^{1/u} for fixed u≥1u \geq 1, introducing the function now bearing his name.[6] The term gained widespread prominence in the 1980s through its central role in advanced factoring techniques like the quadratic sieve, with modern usage further entrenched in cryptographic benchmarks such as the RSA Factoring Challenge launched in the 1990s.[6] Since 2000, the terminology has seen no major evolution, maintaining its relevance in the analysis of number-theoretic algorithms.[6]

Properties

Distribution

The counting function Ψ(x,y)\Psi(x, y) for smooth numbers, introduced in studies of prime factorization distributions, denotes the number of yy-smooth positive integers less than or equal to xx. This includes 1 and all products of primes at most yy whose value does not exceed xx.[6][7] Ψ(x,y)\Psi(x, y) is non-decreasing in both xx and yy, as increasing the upper limit or the smoothness bound can only include additional or the same numbers in the count. For y≥2y \geq 2, Ψ(x,y)≥1\Psi(x, y) \geq 1, since 1 is always yy-smooth, and the function grows rapidly as yy increases, incorporating more prime factors into allowable products. However, for fixed yy, as x→∞x \to \infty, almost all integers up to xx are not yy-smooth, meaning Ψ(x,y)/x→0\Psi(x, y)/x \to 0.[6][7] For fixed yy, when y≤log⁡xlog⁡log⁡xy \leq \sqrt{\log x \log \log x}, Ψ(x,y)\Psi(x, y) admits an explicit combinatorial expression: Ψ(x,y)=1π(y)!∏p≤ylog⁡xlog⁡p(1+O(y2log⁡xlog⁡y))\Psi(x, y) = \frac{1}{\pi(y)!} \prod_{p \leq y} \frac{\log x}{\log p} \left(1 + O\left(\frac{y^2 \log x}{\log y}\right)\right), reflecting the approximate volume of the simplex defined by the exponents in the prime factorization. Exact values of Ψ(x,y)\Psi(x, y) are computed using sieve methods, which systematically eliminate non-smooth candidates by marking multiples of primes larger than yy.[6] Smooth numbers can be generated computationally via adapted sieving algorithms, for instance, producing all yy-smooth numbers up to moderate bounds like x=106x = 10^6 and y=100y = 100 in feasible time on standard hardware. Specific sequences of yy-smooth numbers for fixed small yy are cataloged in the On-Line Encyclopedia of Integer Sequences, such as A002473 for 7-smooth numbers (products of powers of 2, 3, 5, and 7).[7] A notable heuristic regime occurs when y=log⁡xy = \log x, where Ψ(x,log⁡x)=xlog⁡4log⁡log⁡x(1+o(1))\Psi(x, \log x) = x \frac{\log 4}{\log \log x} (1 + o(1)), indicating roughly x/log⁡log⁡xx / \log \log x such numbers; an elementary upper bound Ψ(x,log⁡x)≤xW0/log⁡log⁡x\Psi(x, \log x) \leq x W_0 / \log \log x for some constant W0W_0 follows directly from counting constraints on prime exponents. This contrasts with the prime-counting function π(x)≈x/log⁡x\pi(x) \approx x / \log x, highlighting that log-xx-smooth numbers are sparser than primes despite allowing composite forms.[8]

Asymptotic Estimates

The asymptotic density of smooth numbers is captured by the Dickman function ρ(u)\rho(u), defined to satisfy ρ(u)=1\rho(u) = 1 for 0≤u≤10 \leq u \leq 1 and the delay differential equation uρ′(u)+ρ(u−1)=0u \rho'(u) + \rho(u-1) = 0 for u>1u > 1.[9] This function admits integral representations that facilitate numerical computation, such as the form derived from its integral equation ρ(u)=1u∫u−1uρ(t) dt\rho(u) = \frac{1}{u} \int_{u-1}^{u} \rho(t) \, dt for integer intervals, extended continuously.[9] Explicit values include ρ(1)=1\rho(1) = 1 and ρ(2)=1−log⁡2≈0.3069\rho(2) = 1 - \log 2 \approx 0.3069.[9] The count Ψ(x,y)\Psi(x, y) of yy-smooth numbers up to xx satisfies Ψ(x,y)∼xρ(u)\Psi(x, y) \sim x \rho(u) as x→∞x \to \infty, where u=log⁡x/log⁡yu = \log x / \log y, establishing that the probability a random integer n≤xn \leq x is yy-smooth is asymptotically ρ(u)\rho(u).[10] For y=(log⁡x)2y = (\log x)^2, this probability is ∼x−1/2\sim x^{-1/2}.[6] De Bruijn refined this leading term, showing that for fixed uu, Ψ(x,y)=xρ(u)(1+O(1/log⁡y))\Psi(x, y) = x \rho(u) (1 + O(1 / \log y)), with uniform estimates extending to larger uu up to O(log⁡y/log⁡log⁡y)O(\log y / \log \log y).[10] These improvements provide relative errors of O(log⁡(1+u)/log⁡y)O(\log(1+u) / \log y) valid for y≥exp⁡((log⁡x)5/8+ε)y \geq \exp((\log x)^{5/8 + \varepsilon}) and x≥2x \geq 2.[10] Advanced asymptotics employ saddle-point methods to handle regimes where y=x1/uy = x^{1/u} and uu grows with xx, yielding Ψ(x,y)=xρ(u)(1+O(1/u+1/log⁡y))\Psi(x, y) = x \rho(u) (1 + O(1/u + 1/\log y)) with error terms bounded by O(xρ(u)/log⁡y)O(x \rho(u) / \log y).[10] These techniques, originating in the Perron formula integration of the partial zeta function over smooth numbers, enable precise approximations across broader ranges.[10] Recent research by Tao explores max-entropy properties of smooth numbers, interpreting ρ(u)\rho(u) through probabilistic models where the distribution of prime factors maximizes entropy subject to constraints on the largest prime and logarithmic magnitude.[11] In this framework, yy-smooth numbers up to x=yux = y^u arise from selecting primes p≤yp \leq y with probabilities cp/pc_p / p that optimize entropy, yielding ρ(u)≈exp⁡(−uξ(u)+∫0ξ(u)(es−1)/s ds)\rho(u) \approx \exp(-u \xi(u) + \int_0^{\xi(u)} (e^s - 1)/s \, ds) where ξ(u)\xi(u) solves ξ=log⁡u+log⁡ξ−1+o(1)\xi = \log u + \log \xi - 1 + o(1).[11] This heuristic links smoothness to maximal randomness under prime factorization constraints, reinforcing the Dickman asymptotic.[11]

Variants

Powersmooth Numbers

In number theory, a positive integer n≤xn \leq x is defined as uu-powersmooth if it is yy-smooth with y=x1/uy = x^{1/u}, where u≥1u \geq 1 is a real parameter measuring the degree of smoothness; larger uu implies a smaller yy, requiring all prime factors of nn to be bounded by a tighter threshold, thus making nn "smoother."[3] The collection of such uu-powersmooth numbers up to xx forms a finite set for any fixed uu and xx.[3] As x→∞x \to \infty with fixed uu, the proportion of uu-powersmooth numbers up to xx approaches ρ(u)\rho(u), where ρ\rho is the Dickman–de Bruijn function satisfying ρ(u)=1\rho(u) = 1 for 0<u≤10 < u \leq 1 and the delay differential equation uρ′(u)+ρ(u−1)=0u \rho'(u) + \rho(u-1) = 0 for u>1u > 1.[3] This positive limiting density ρ(u)\rho(u) (e.g., ρ(2)≈0.307\rho(2) \approx 0.307) distinguishes uu-powersmooth numbers from those that are smooth over a fixed yy, whose density tends to 0 as x→∞x \to \infty.[3] The Buchstab function ω(u)\omega(u), defined by ω(u)=1/u\omega(u) = 1/u for 1≤u≤21 \leq u \leq 2 and the equation (uω(u))′=ω(u−1)(u \omega(u))' = \omega(u-1) for u>2u > 2, provides a refinement to the asymptotic estimate involving ρ(u)\rho(u) in certain ranges of uu.[12] Specifically, for u=1u=1, y=xy = x, so every integer n≤xn \leq x is 1-powersmooth.[3] For illustration, consider x=100x = 100 and u=2u = 2, yielding y≈10y \approx 10; the 2-powersmooth numbers up to 100 are then the 10-smooth numbers in this range, such as 1, 2, 3, 4 (= 222^2), 5, 6, 7, 8 (= 232^3), 9 (= 323^2), 10, and continuing to products like 36 (= 22⋅322^2 \cdot 3^2) and 90 (= 2⋅32⋅52 \cdot 3^2 \cdot 5), provided the largest prime factor does not exceed 10.[3] Note that in some contexts, particularly factorization algorithms, "B-power smooth" refers to numbers whose prime power factors pep^e each satisfy pe≤Bp^e \leq B, equivalent to the divisors of lcm⁡(1,2,…,B)\operatorname{lcm}(1, 2, \dots, B), as in OEIS A003418. For example, for B=9B=9, lcm⁡(1\operatorname{lcm}(1 to 9)=25209) = 2520, and its divisors are the 9-power smooth numbers in this sense (with bounded exponents).[13][14] Powersmooth numbers play a key role in factorization algorithms. In Pollard's p−1p-1 method, the algorithm succeeds in factoring a composite NN if there exists a prime factor pp of NN such that p−1p-1 is BB-power smooth for some bound BB (meaning all prime powers in p−1p-1 are ≤B\leq B), allowing computation of gcd⁡(alcm(1,2,…,B)−1,N)\gcd(a^{ \mathrm{lcm}(1,2,\dots,B) } - 1, N) to reveal pp, where aa is a base coprime to pp.[14] Similarly, the elliptic curve method (ECM) targets prime factors pp of NN where the order of an elliptic curve group over Fp\mathbb{F}_p is smooth (with small prime factors), enabling efficient detection via smooth-order assumptions in the group structure.[3]

Set-Smooth Numbers

A set-smooth number generalizes the concept of smooth numbers by allowing factorization over an arbitrary finite set AA of positive integers. A positive integer nn is AA-smooth if it lies in the multiplicative semigroup generated by AA, meaning n=∏a∈Aaean = \prod_{a \in A} a^{e_a} where the exponents eae_a are non-negative integers, finitely many of which are positive (with the empty product defined as 1). This definition extends the standard notion of smoothness beyond prime factors to products of powers from the set AA itself.[3] When AA is the set of all prime numbers less than or equal to some bound BB, the AA-smooth numbers coincide exactly with the classical BB-smooth numbers, whose prime factors are all at most BB. In this prime-based case, the generalization aligns with foundational work in computational number theory, where such sets serve as factor bases in sieving algorithms. However, the framework permits composite elements in AA, introducing potential constraints on the exponents of underlying primes. For instance, over A={3,4}A = \{3, 4\}, the number 12 is {3,4}\{3, 4\}-smooth because 12=31×4112 = 3^1 \times 4^1, but 6 is not, as it requires an odd exponent for the prime 2, which cannot be achieved solely through powers of 3 and 4 (since 4=224 = 2^2 yields only even exponents for 2). Similarly, over A={2,3,4}A = \{2, 3, 4\}, the AA-smooth numbers include 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, and 36, among others; here, the inclusion of the composite 4 does not restrict the set beyond the prime-based {2,3}\{2, 3\}-smooth numbers, but illustrates how redundant composites can be incorporated without altering the generated semigroup. This contrasts with prime-based smoothness by allowing non-prime generators, which may impose or relax exponent conditions depending on the prime factorizations within AA.[3] The counting function ΨA(x)\Psi_A(x), which enumerates the number of AA-smooth numbers up to xx, serves as an analog to the classical Ψ(x,y)\Psi(x, y) for yy-smooth numbers. For finite AA consisting of primes, asymptotic estimates for ΨA(x)\Psi_A(x) follow from properties of the Dickman-de Bruijn function, scaled by the structure of AA. These counts are central to investigations of additive and multiplicative decompositions in sets with restricted factors. In non-standard bases such as Gaussian integers, similar notions arise for ideal factorization, though the focus here remains on positive integers. Set-smooth numbers find use in generalized sieving methods, where factor bases extend beyond small primes to structured sets for efficient relation collection in integer factorization algorithms.[3][15]

Applications

Computational Number Theory

Smooth numbers play a central role in computational number theory, particularly in algorithms for integer factorization that rely on identifying numbers with small prime factors. The classical sieve of Eratosthenes, originally designed to find primes up to a limit, can be modified to identify y-smooth numbers by iteratively marking multiples of primes up to y and retaining those without larger factors.[16] For larger ranges, segmented sieves extend this approach, dividing the interval [1, x] into manageable blocks to efficiently compute or enumerate y-smooth numbers, enabling the evaluation of the counting function Ψ(x, y).[17] In factorization algorithms, smooth numbers are essential for generating relations that lead to non-trivial factors. Dixon's method, introduced in 1979, selects random integers k near the square root of the composite N to be factored, computes Q(k) = k² - N, and checks if Q(k) is smooth over a small factor base of primes; collecting enough such smooth relations allows solving a linear system to find a congruence of squares modulo N.[4] This approach inspired the quadratic sieve, which improves efficiency by sieving values of a quadratic polynomial near √N to identify smooth relations more systematically, balancing the factor base size with the smoothness probability.[18] Similarly, the number field sieve, a more advanced method, generates relations involving smooth ideals in a number field whose norm is close to N, exploiting smoothness in both rational and algebraic integers to achieve subexponential runtime.[19] The efficiency of these methods hinges on the expected number of trials needed to find a y-smooth number in [1, x], which is approximately x / Ψ(x, y) ≈ 1 / ρ(u), where u = log x / log y and ρ is the Dickman-de Bruijn function.[4] In the random square method of Dixon, the probability that a candidate Q of size roughly √N is y-smooth follows the heuristic ρ(u) ∼ u^{-u} for large u = (log N)/(2 log y).[20] Other algorithms leverage smoothness indirectly or in specialized ways: Pollard's rho method detects small prime factors through cycle detection in a pseudorandom sequence, benefiting from scenarios where differences yield smooth multiples.[21] Lenstra's elliptic curve method (ECM) factors N by selecting random elliptic curves modulo N and computing multiples of a point until the group order modulo a prime factor p is detected as smooth, allowing efficient scalar multiplication before the computation fails modulo p.[22] Smooth numbers also underpin primality testing, such as the Adleman–Pomerance–Rumely (APR) test, which uses primes p where p-1 is smooth to construct a sequence of primes and verify primality deterministically via properties of cyclotomic fields and smooth order subgroups.[3] Advancements in the 1980s, particularly in sieving techniques for generating smooth numbers, significantly accelerated the continued fraction factoring algorithm (CFRAC), enabling routine factorization of numbers with up to 50 digits by optimizing the collection of smooth residues from continued fraction convergents.[23]

Cryptography

Smooth numbers play a critical role in cryptographic attacks on integer factorization, particularly those targeting the security of the RSA cryptosystem, which relies on the difficulty of factoring large composite moduli. In the quadratic sieve (QS) algorithm, smooth numbers are generated as values of a quadratic polynomial that factor completely over a factor base of small primes, allowing the construction of relations that lead to a square congruence modulo the target number and ultimately its factorization. Similarly, the number field sieve (NFS), the most efficient general-purpose factoring algorithm, depends on finding smooth relations where both the rational norm a−bma - b m and the algebraic norm in the number field are yy-smooth, with the smoothness bound yy approximately exp⁡((log⁡x)1/3)\exp((\log x)^{1/3}), enabling the sieving of candidates to build a dependency matrix for extracting factors. These methods exploit the abundance of smooth numbers to undermine RSA by factoring semiprimes up to hundreds of digits in size.[18][24] The Very Smooth Hash (VSH) is a provably collision-resistant hash function constructed directly from the presumed hardness of finding very smooth numbers. It maps an input message to a smooth integer nn whose prime factors are restricted to a fixed set of small primes, using modular exponentiation in a group of order NN, where collisions would require solving a non-smoothness assumption akin to the difficulty in discrete logarithm problems but tied to smoothness. VSH requires only one modular multiplication per Ω(S)\Omega(S) message bits for an SS-bit output, making it efficient for applications like trapdoor hash functions in digital signatures.[25] In practice, the elliptic curve method (ECM) leverages smooth numbers for factoring RSA challenge numbers, particularly when auxiliary composites arise during sieving; its success rate hinges on the powersmoothness of the elliptic curve group orders, as smoother orders allow larger scalar multiples within bounded smoothness limits to detect factors via gcd computations. For RSA key generation, moduli are chosen to avoid smooth p−1p-1 or q−1q-1 factors, as these enable efficient attacks like Pollard's p−1p-1 method, which computes high powers modulo NN using smooth exponents and detects factors through gcd with NN. During the 1990s, several RSA challenges, including the 129-digit RSA-129 factored in 1994, were solved using smooth number sieving in QS and early NFS implementations. Although post-quantum cryptography shifts away from factoring-based systems like RSA due to quantum threats, smooth numbers remain essential for classical cryptanalysis and assessing legacy system security.[26][27][23]

Other Fields

In signal processing, the Cooley-Tukey algorithm for the fast Fourier transform (FFT) relies on smooth transform lengths $ n $ to enable efficient recursive decomposition into smaller DFTs via radix factors, optimizing the computation of twiddle factors and achieving $ O(n \log n) $ complexity for highly composite $ n $.[28] Specifically, FFT implementations such as FFTW perform best with $ n $ of the form $ 2^k \cdot 3^m \cdot 5^p $, which are 15-smooth numbers, as these allow specialized codelets for small prime factors that minimize arithmetic operations.[29] In music theory, ancient Babylonian tuning systems approximated musical intervals using rational ratios with small denominators, favoring 5-smooth numbers to achieve consonant intervals within their sexagesimal framework.[30] For instance, the harmonic series in just intonation prioritizes 7-smooth harmonics (prime factors at most 7) for consonance, as higher partials with larger primes introduce dissonance through inharmonic beating.[31] Historical Babylonian tablets employed 60-smooth fractions in the sexagesimal system (base 60 = $ 2^2 \cdot 3 \cdot 5 $) for precise representations, facilitating calculations in astronomy and geometry.[32] In statistics, a 2025 result by Terence Tao connects smooth numbers to maximum-entropy distributions over prime factorizations, yielding heuristic models for their density that align with probabilistic estimates from number theory.[11] In ancient Babylonian mathematics, smooth rational approximations were applied to square roots, as evidenced by tablet YBC 7289, which computes 2≈1;24,51,10\sqrt{2} \approx 1;24,51,10 (a 60-smooth fraction equivalent to $ 577/408 $) using iterative methods.[33] Smooth numbers also appear in Waring's problem, where representing numbers as sums of k-th powers benefits from smooth bases to minimize the number of terms required. In Egyptian fraction expansions, greedy algorithms prefer smooth denominators to express rationals as sums of distinct unit fractions efficiently. Additionally, solving S-unit equations in algebraic number fields relies on the finiteness of solutions involving smooth S-units, with effective bounds derived from logarithmic heights and smooth factorizations.[3]

References

  1. Smooth Number -- from Wolfram MathWorld
  2. smooth number - PlanetMath
  3. [PDF] Smooth numbers: computational number theory and beyond
  4. [PDF] On the role of smooth numbers in number theoretic algorithms
  5. Why are smooth numbers called "smooth"? - MathOverflow
  6. [PDF] smooth numbers: computational number theory and beyond
  7. [PDF] 10 Index calculus, smooth numbers, and factoring integers
  8. [PDF] Counting perfect numbers - Paul Pollack
  9. Dickman Function -- from Wolfram MathWorld
  10. [PDF] Explicit Estimates for the distribution of numbers free of large prime ...
  11. Smooth numbers and max-entropy - Terry Tao - WordPress.com
  12. [PDF] The Sieve of Eratosthenes and Rough Numbers
  13. A003418 - OEIS
  14. [PDF] Elementary Number Theory: Primes, Congruences, and Secrets
  15. On additive and multiplicative decompositions of sets of integers ...
  16. Some problems of analytic number theory on arithmetic semigroups
  17. None
  18. [PDF] 1 The Sieve of Eratosthenes 2 The principle of inclusion-exclusion
  19. [PDF] Sieve Methods - cs.wisc.edu
  20. [PDF] Smooth numbers and the quadratic sieve - Dartmouth Mathematics
  21. [PDF] The number field sieve - Dartmouth Mathematics
  22. [PDF] 11 Index calculus, smooth numbers, and factoring integers
  23. [PDF] Factoring Pollard's rho algorithm
  24. [PDF] THE ELLIPTIC CURVE METHOD
  25. A Tale of Two Sieves - American Mathematical Society
  26. [PDF] A Beginner's Guide To The General Number Field Sieve
  27. VSH, an Efficient and Provable Collision Resistant Hash Function
  28. [PDF] ECM at Work - Cryptology ePrint Archive
  29. [PDF] Pollard's p-1 and Lenstra's factoring algorithms
  30. [PDF] Divisibility, Smoothness and Cryptographic Applications
  31. FFTW Home Page
  32. [PDF] Filip D. Jevtic SMOOTH NUMBERS IN MUSIC AND ARCHITECTURE
  33. [PDF] Mathematical Harmony Analysis - arXiv
  34. Babylonian numerals - MacTutor History of Mathematics
  35. Square Root Approximations in Old Babylonian Mathematics
User Avatar
No comments yet.