psmooth

psmooth refers to a property of integers called p‑smoothness, which describes how the prime factors of a number relate to a given bound p. An integer n is called p‑smooth if every prime divisor of n is less than or equal to p. For example, 60 = 2^2·3·5 is 5‑smooth, whereas 77 = 7·11 is not 5‑smooth because one of its prime factors exceeds 5. The concept is also known as “smooth” or “e‑smooth” in different contexts, depending on the chosen bound.

The distribution of p‑smooth numbers has been well studied. The Dickman–de Bruijn function ψ(u) provides an asymptotic estimate for the proportion of numbers ≤x that are x^1/u‑smooth. Roughly, as x grows, the proportion of p‑smooth numbers decays polynomially in p, which makes smooth numbers increasingly rare when the bound p is small relative to the size of the integers considered.

In analytic number theory, smooth numbers play a crucial role in the study of factorization algorithms, such as the quadratic sieve and the number field sieve. These algorithms search for relations among p‑smooth numbers because they allow the construction of congruences of squares, which are key to factoring large integers. In cryptography, the hardness of certain problems, like the discrete logarithm in finite fields, is sometimes connected to the difficulty of finding smooth numbers with large prime factors.

Testing whether an integer is p‑smooth can be performed by trial division or by sieving to remove all prime factors ≤p; if the remainder equals 1, the number is p‑smooth. Generating lists of p‑smooth numbers up to a bound may employ recursive back‑tracking or dynamic programming to multiply admissible primes without exceeding the target range. Efficient sieving methods and precomputed prime lists further accelerate these tasks.

Related notions include y‑friable numbers, which generalize smoothness to variable bounds, and strongly smooth numbers in which each prime factor appears to a certain multiplicity. The theory of smooth numbers is intertwined with the distribution of primes, the Riemann hypothesis, and computational aspects of modern cryptography.