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

定义

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

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

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

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

应用

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

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

密码学中也有应用光滑数^[7]。虽然大部分的密码学都会用到密码分析（已知最快的约数分解算法），但VSH杂凑函数利用光滑数来取得可证安全加密散列函数（英语：Provably secure cryptographic hash function）。

分布

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

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

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

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

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

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

其中${\displaystyle \scriptstyle \rho (u)}$为Dickman函数（英语：Dickman function）。

幂次光滑数

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

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

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

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

相关条目

• 粗糙数
• Størmer定理（英语：Størmer's theorem）
• 高合成数

参考资料

外部链接

查 论 编 和约数有关的整数分类 简介 素因数分解 约数 元约数 除数函数 素因数 算术基本定理 依约数分解分类 素数 合数 半素数 普洛尼克数 楔形数 无平方数因数的数 幂数 素数幂 平方数 立方数 次方数 阿喀琉斯数 光滑数 正规数 粗糙数 不寻常数 依约数和分类 完全数 殆完全数 准完全数 多重完全数 Hemiperfect数 Hyperperfect number（英语：Hyperperfect number） 超完全数 元完全数 半完全数 本原半完全数 实际数 有许多约数 过剩数 本原过剩数 高过剩数 超过剩数 可罗萨里过剩数 高合成数 Superior highly composite number（英语：Superior highly composite number） 奇异数 和真因子和数列有关 不可及数 相亲数 交际数 婚约数 其他 亏数 友谊数 孤独数 卓越数 欧尔调和数 佩服数 节俭数 等数位数 奢侈数