Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

"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?

share|improve this question
1  
Probably because naive trial factorization goes so smoothly for such numbers. –  The Masked Avenger May 6 at 23:21
3  
I think it's a variation on "round" numbers, which have a lot of twos and fives in their factorization. –  Gerry Myerson May 6 at 23:21
2  
@WillJagy: There is a mice() function in R: Multivariate Imputation by Chained Equations. :-) –  Joseph O'Rourke May 6 at 23:56
2  
3  
There is a vague analogy with Fourier series. The more weight is carried by high frequencies in a Fourier series, the less smooth the function is. From this point of view, the most smooth functions are composed of finitely many harmonics. –  Yuri Bakhtin May 7 at 0:41

3 Answers 3

up vote 21 down vote accepted

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"...

share|improve this answer

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/ .

share|improve this answer
1  
An aside: One quote among the comments to the blog entry to which you linked is interesting: "I think of it like gravy: smooth gravy has no lumps or chunks in it, and the analogue of lumps for integers is big prime factors." –  Joseph O'Rourke May 7 at 1:04
1  
Supposedly, the opposite of "smooth" was "chunky", following a peanut butter analogy. –  Conder May 7 at 1:06

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.