光滑數

光滑數（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）。

令 $\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函數（英語：Dickman function）。

若所有可以整除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演算法（英語：Pollard's p − 1 algorithm），這類演算法一般會應用在光滑數中，但不會特別標示光滑數的B是多少。此時的B需是一個較小的整數，若B增加，演算法的效率就會迅速的變差。例如計算離散對數的Pohlig–Hellman演算法（英語：Pohlig–Hellman algorithm）的時間複雜度是O(B^1/2)。

^ Gérald Tenenbaum. 解析与概率数论导引. 高等教育出版社. 2011年1月. ISBN 9787040294675.
^ 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."
^ OEIS Search
^ 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, MR 0191779 .
^ Longuet-Higgins, H. C., Letter to a musical friend, Music Review, 1962, (August): 244–248 .
^ 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） .
^ David Naccache, Igor Shparlinski, Divisibility, Smoothness and Cryptographic Applications （頁面存檔備份，存於網際網路檔案館）

整數數列線上大全（OEIS）中有包括以下B較小的B-光滑數：