光滑數

光滑數（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）
• 高合成數

參考資料

1. Gérald Tenenbaum. 解析与概率数论导引. 高等教育出版社. 2011年1月. ISBN 9787040294675. 使用|accessdate=需要含有|url= (幫助)
2. M. E. Hellman, J. M. Reyneri, "Fast computation of discrete logarithms in GF (q)", in Advances in Cryptology: Proceedings of CRYPTO '82 (eds. D. Chaum, R. Rivest, A. Sherman), New York: Plenum Press, 1983, p. 3–13, online quote （頁面存檔備份，存於互聯網檔案館） at Google Scholar: "Adleman refers to integers which factor completely into small primes as 「smooth」 numbers."
3. OEIS Search
4. Aaboe, Asger, Some Seleucid mathematical tables (extended reciprocals and squares of regular numbers), Journal of Cuneiform Studies, 1965, 19 (3): 79–86, doi:10.2307/1359089, MR0191779.
5. Longuet-Higgins, H. C., Letter to a musical friend, Music Review, 1962, (August): 244–248.
6. Dijkstra, Edsger W., Hamming's exercise in SASL (PDF), 1981 [2013-01-15], Report EWD792. Originally a privately-circulated handwitten note, （原始內容存檔 (PDF)於2019-04-04）.
7. David Naccache, Igor Shparlinski, Divisibility, Smoothness and Cryptographic Applications （頁面存檔備份，存於互聯網檔案館）

外部連結

• 埃里克·韋斯坦因. 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