Smooth Numbers

Definition

A positive integer is called $y$ -smooth if all of its prime factors are at most $y$ .

For example,

72=2^3\cdot 3^2

is $3$ -smooth, because its only prime factors are $2$ and $3$ . The integer

210=2\cdot3\cdot5\cdot7

is $7$ -smooth, but not $5$ -smooth.

Smooth numbers are integers whose prime factors are small relative to their size. They form a sparse but highly structured subset of the positive integers.

The Smooth Counting Function

The main counting function for smooth numbers is

\Psi(x,y)=\#\{n\leq x : n \text{ is } y\text{-smooth}\}.

This function asks how many integers up to $x$ have no prime factor larger than $y$ .

The behavior of $\Psi(x,y)$ depends on the relation between $x$ and $y$ . If $y\geq x$ , then every integer up to $x$ is $y$ -smooth. If $y$ is small, smooth numbers become rare.

A useful parameter is

u=\frac{\log x}{\log y}.

Equivalently,

y=x^{1/u}.

Large $u$ means that $y$ is small compared with $x$ , so smoothness is a strong condition.

The Dickman Function

The density of smooth numbers is governed by the Dickman function $\rho(u)$ .

Roughly,

\Psi(x,y)\approx x\rho(u), \qquad u=\frac{\log x}{\log y}.

The function $\rho(u)$ is defined by

\rho(u)=1 \qquad (0\leq u\leq 1),

and for $u>1$ , by the differential-delay equation

u\rho'(u)+\rho(u-1)=0.

This function decreases rapidly as $u$ grows. It measures the probability that a random integer near $x$ has all prime factors at most $x^{1/u}$ .

Heuristic Interpretation

A random integer near $x$ usually has some prime factors of moderate or large size. Requiring all prime factors to be at most $y$ imposes many restrictions at once.

y=x^{1/2},

then $u=2$ . A $y$ -smooth integer has no prime factor larger than $\sqrt{x}$ . This excludes primes near $x$ , but still leaves many composite numbers.

y=x^{1/10},

then $u=10$ . Smoothness is much rarer, because every prime factor must be quite small.

The Dickman function makes this heuristic precise in many ranges.

Smooth Numbers and Factorization

Smooth numbers are central in integer factorization algorithms.

Many factorization methods seek relations of the form

x^2\equiv y^2\pmod N.

To construct such relations, one often searches for integers whose residues factor completely over a small factor base.

For example, the quadratic sieve studies values

Q(t)=t^2-N.

If many values of $Q(t)$ are smooth, their prime factorizations can be combined through linear algebra over $\mathbb{F}_2$ . This eventually produces a congruence of squares and may reveal a nontrivial factor of $N$ .

Thus the efficiency of factorization algorithms depends directly on the frequency of smooth numbers.

Factor Bases

A factor base is a chosen list of small primes

p_1,p_2,\ldots,p_m.

An integer is smooth over this factor base if it factors entirely into these primes.

For example, relative to the factor base

\{2,3,5,7\},

the integer

2^4\cdot3\cdot7=336

is smooth, while

2\cdot11=22

is not.

Factor bases turn multiplicative arithmetic into linear algebra. Once a smooth integer is factored over the base, its exponent vector

(e_1,\ldots,e_m)

records the powers of the primes. Reducing this vector modulo $2$ allows one to detect products that become squares.

Smoothness Probability

The probability that a random integer near $x$ is $y$ -smooth is approximately

\rho\left(\frac{\log x}{\log y}\right).

This probability controls the expected running time of many algorithms.

If smooth values are too rare, the algorithm spends too much time searching. If the factor base is too large, linear algebra becomes expensive.

Practical algorithms must balance these costs.

This balance is one reason smooth numbers are so important in computational number theory: they determine the tradeoff between relation collection and matrix solving.

Powers and Multiplicative Structure

Smooth numbers are multiplicatively rich. If $a$ and $b$ are $y$ -smooth, then

ab

is also $y$ -smooth.

This closure under multiplication makes them useful in algorithms and algebraic constructions.

However, smooth numbers are not closed under addition. The sum of two smooth numbers may have a large prime factor.

This asymmetry reflects the fundamentally multiplicative nature of smoothness.

Friable Integers

Smooth numbers are also called friable integers, especially in analytic number theory.

The term emphasizes that such integers break apart into small prime pieces.

Analytic questions about friable integers include:

estimating $\Psi(x,y)$ ,
studying smooth numbers in arithmetic progressions,
counting smooth values of polynomials,
understanding gaps between smooth numbers.

These questions are technically subtle because smoothness depends on complete prime factorization.

Smooth Values of Polynomials

Many algorithms and conjectures concern smooth values of polynomial expressions.

For example, one may ask how often

f(n)

is $y$ -smooth for a polynomial $f(x)\in\mathbb{Z}[x]$ .

This is much harder than studying random integers, because polynomial values have arithmetic biases.

In the number field sieve, one searches for simultaneous smoothness in rational and algebraic values. The success of the method depends on finding enough such values.

Smooth Numbers in Cryptography

Smoothness can weaken cryptographic systems.

For example, Pollard’s $p-1$ method factors an integer $N$ efficiently if some prime divisor $p$ has

p-1

smooth.

Similarly, discrete logarithm algorithms often exploit smooth group orders or smooth auxiliary structures.

Therefore cryptographic parameter generation usually avoids primes for which nearby arithmetic quantities factor too smoothly.

Rough Numbers

The opposite of a smooth number is often called a rough number.

An integer is $y$ -rough if all of its prime factors are greater than $y$ .

Rough numbers also appear in sieve theory. While smooth numbers are built only from small primes, rough numbers avoid all small primes.

Both concepts measure how prime factors are distributed across size ranges.

Conceptual Importance

Smooth numbers connect the statistical behavior of prime factors with explicit computation.

They appear naturally in:

integer factorization,
discrete logarithm algorithms,
sieve methods,
probabilistic number theory,
cryptographic security analysis.

Their importance comes from a simple fact: small prime factors are easy to handle. When an integer factors entirely into small primes, it becomes computationally tractable.

Smooth numbers therefore form one of the main bridges between analytic estimates and practical algorithms in modern number theory.