📂Number Theory

Smooth Primes

Definitions

1. A prime number $p$ that has many divisors is called a smooth prime if $(p-1)$.
2. A number that can be represented as a product of prime numbers less than or equal to $B$ is called a $B$-smooth number.
3. $\psi ( X , B )$ represents the number of $B$-smooth numbers less than or equal to $X$.

Description

As an example of a smooth prime, consider $p=37$ where $(p-1)$ is expressed as a product of small prime numbers such as $p-1 = 36 = 2^2 3^2$. The concept of smoothness was introduced to describe primes not suitable for cryptography as cryptography advanced.

Examples of $5$-smooth numbers include $$ 2,3,4,5,6,8,9,10,12,15,16,18 \cdots $$ and examples of numbers that are not $5$-smooth numbers include $$ 7,11,13, 14, 17,19,21,22,23,26,28,29,31,33\cdots $$

$\psi : \mathbb{N}^2 \to \mathbb{N}_{0}$ is a typical counting function. For instance, if we consider $\psi (25,5)$, there are $2,3,4,5,6,8,9,10,12, $$ 15,16,18 ,20,24,25$ $5$-smooth numbers less than or equal to $25$, which can be represented as $\psi (25,5) = 15$.