光滑数

光滑数（smooth number），或译脆数，是一个可以因数分解为小质数乘积的正整数。光滑数一词是是伦纳德·阿德曼所提出。光滑数在以因数分解为基础的密码学中扮演重要角色。

定义

若一正整数的质因数均不大于B，此整数即为B-光滑数。例如1620的因数分解为2² × 3⁴ × 5，质因数均不大于5，因此1620是5-光滑数。

10和12的因数分解分别为2 × 5和2² × 3，二者质因数也都不大于5，因此二者均是是5-光滑数，虽然其质因数未包括不大于5的所有质数，但仍然可以是5-光滑数。

5-光滑数常称为正规数或汉明数（Hamming numbers）。7-光滑数有时会称为“谦虚数”或“高合成数”，不过后者会和以因数个数来定义的高合成数混淆。

B-光滑数的B不一定要是质数，例如上述举例的10和12不但是5-光滑数，也是6-光滑数（质因数都不大于6）。一般而言会选择B为质数的B-光滑数，但B也可以是合数。一正整数为B-光滑数若且唯若正整数为p-光滑数，且p是小于等于B的最大质数。

应用

有些快速傅里叶变换演算法中会用到光滑数，例如库利－图基快速傅里叶变换算法会将问题一直分解为较小的问题，其大小为原问题大小的因数，若原问题大小是B原问题大小，原问题可以分解为许多很小的问题，此情形有有快速的演算法，若大小是较大的质数，就要应用像是Chirp-Z 转换之类效率较差的演算法。

5-光滑数〈或称为正规数〉在巴比伦数学中有重要的角色，在音乐理论中也很重要。有一个函数程式语言的问题就是要产生正规数。

密码学中也有应用光滑数。虽然大部份的密码学都会用到密码分析（已知最快的因数分解演算法），但VSH杂凑函数利用光滑数来取得可证安全加密散列函数。

分布

令$\scriptstyle \Psi (x,y)$表示小于等于x的y-光滑数的个数（de Bruijn函数）。

若B为定值且数值很小，可以用下式估计$\scriptstyle \Psi (x,B)$:

$\Psi (x,B)\sim {\frac {1}{\pi (B)!}}\prod _{p\leq B}{\frac {\log x}{\log p}}.$

其中$\scriptstyle {\pi (B)}$为小于等于$\scriptstyle B$的质数个数。

否则，定义参数u= log x / log y：因此，x = y^u，则：

$\Psi (x,y)=x\cdot \rho (u)+O\left({\frac {x}{\log y}}\right)$

其中$\scriptstyle \rho (u)$为Dickman函数。

幂次光滑数

若所有可以整除m的质数幂次 $\scriptstyle p_{i}^{n_{i}}$满足以下方程，则m为B-幂次光滑数：

$p_{i}^{n_{i}}\leq B.\,$

例如，2⁴3²5¹为5-光滑数，但不是5-幂次光滑数。因为其最大的质数幂次为2⁴，该数为16-幂次光滑数，也是17-幂次光滑数，18-幂次光滑数……。

数论中有用到B-光滑数及B-幂次光滑数。例如波拉德p-1演算法，这类演算法一般会应用在光滑数中，但不会特别标示光滑数的B是多少。此时的B需是一个较小的整数，若B增加，演算法的效率就会迅速的变差。例如计算离散对数的Pohlig–Hellman演算法的时间复杂度是O(B^1/2)。

相关条目

• 粗糙数
• Størmer定理
• 高合成数

外部链接

• 埃里克·韦斯坦因. Smooth Number. MathWorld. 

整数数列线上大全（OEIS）中有包括以下B较小的B-光滑数：

• 2-光滑数：A000079 (2ⁱ)
• 3-光滑数：A003586 (2ⁱ3^j)
• 5-光滑数：A051037 (2ⁱ3^j5^k)
• 7-光滑数：A002473 (2ⁱ3^j5^k7^l)
• 11-光滑数：A051038
• 13-光滑数：A080197
• 17-光滑数：A080681
• 19-光滑数：A080682
• 23-光滑数：A080683