"Adleman refers to integers which factor completely into small primes as “smooth” numbers." (ME Hellman, JM Reyneri. Advances in Cryptology, 1983: citation link.)
Does anyone know what is the intuitive reason behind the choice of the adjective "smooth" for this concept?
I asked Ron Rivest, and he replied:
Yes, I coined the term "smooth number" to refer to a number that has only small prime factors. I don't recall now much about the thinking process, except that smooth is rather the opposite of "lumpy"...
This is almost certainly not the historical justification for the term "smooth", but I have found that the term happily coincides with my analytic intuition of smoothness. Namely, I think of a scalar function $f: G \to {\bf C}$ on an additive group $G$ as being "smooth" (or at least "continuous") if there are lots of shifts $h \in G$ in which one has $f(x+h) \approx f(x)$ for typical $x \in G$ (or more generally if $f(x+h)$ exhibits polynomial type behaviour in $h$). In the classical "Archimedean" setting of analysis over the reals, it is the "small" directions $h \in G$ for which one has this approximate constancy, but in more arithmetic settings, one can work with other sets of shifts. For instance, if working over the $p$-adics, one can consider functions that are ``smooth'' in the sense that $f(x+h)$ is close to $f(x)$ (or otherwise behaves very tamely with respect to $h$) when $h$ is highly divisible by $p$.
Now suppose we are working over a large cyclic group ${\bf Z}/N{\bf Z}$. In this case, one type of smoothness is periodicity (or almost periodicity): there could be some large subgroup $H$ of ${\bf Z}/N{\bf Z}$ such that one has $f(x+h)=f(x)$ (or at least $f(x+h) \approx f(x)$) for all $x \in {\bf Z}/N{\bf Z}$ and $h \in H$. If $N$ is smooth in the sense of having no large prime factors, then there are plenty of subgroups $H$, and plenty of smooth functions. Moreover, many of the functions on ${\bf Z}/N{\bf Z}$ that arise naturally in arithmetic can be represented in terms of smooth functions. For instance, if $a, b$ are residue classes mod $N$ and $f = f_{a,b,N}$ is the Kloosterman phase $f(x) := e^{2\pi i (a\overline{x}+bx)/N} 1_{(x,N)=1}$, with $\overline{x}$ being the multiplicative inverse of $x$ in ${\bf Z}/N{\bf Z}$, then an application of the Chinese remainder theorem shows that whenever $N = qr$ with $q,r$ coprime, then $f_{a,b,N}$ splits as a sum $f_{a',b',q} + f_{a'',b'',r}$ for certain $a',b',a'',b''$, with $f_{a',b',q}$ periodic with respect to the copy of ${\bf Z}/r{\bf Z}$ in ${\bf Z}/N{\bf Z}$, and $f_{a'',b'',r}$ periodic with respect to the copy of ${\bf Z}/q{\bf Z}$. If $N$ is smooth, we can keep splitting up this phase into smoother and smoother pieces. (Such a decomposition, incidentally, was used in the Polymath8 project (following the work of Graham and Ringrose) to obtain improved exponential sum estimates that feed into the method of Yitang Zhang to obtain bounded gaps between primes.)
The Fast Fourier transform algorithm on ${\bf Z}/2^N{\bf Z}$ can be viewed as an exploitation of the smoothness (approximate periodicity) of the Fourier kernel on this group, which ultimately arises from the smoothness (no large prime factors) of $2^N$, and so is another example of how the arithmetic notion of smoothness dovetails with the analytic one.
It should be mentioned though that the term "smooth" is a bit overloaded in analytic number theory, in which one needs both the analytic (Archimedean) notion of smoothness and the arithmetic notion (e.g. when considering exponential sums over smooth moduli, weighted by a smooth cutoff function). Some authors have suggested the alternative term "friable" for the latter concept to reduce the conflict; see e.g. https://blogs.ethz.ch/kowalski/2008/12/08/more-mathematical-terminology-friable/ .
As I far as I recall the story (as related to me by Len Adleman), Len had originally come up the notion of smooth numbers and needed an appropriate name for the definition. Ron suggested calling them 'smooth', and although Len rather disliked the term, he adopted it anyway.
mice()function in R: Multivariate Imputation by Chained Equations. :-) $\endgroup$