查看“光滑數”的源代码

{{NoteTA|G1=Math}}
'''光滑數'''（{{lang|en|'''smooth number'''}}），或译'''脆数'''<ref>{{cite book |author1=Gérald Tenenbaum |title=解析与概率数论导引 |date=2011年1月 |publisher=高等教育出版社 |isbn=9787040294675 |accessdate=2019-05-23}}</ref>{{rp|ix}}，是一個可以[[因數分解]]為小[[質數]]乘積的[[正整數]]。光滑數一詞是是[[伦纳德·阿德曼]]所提出<ref name="Hellman"/>。光滑數在以因數分解為基礎的[[密码学]]中扮演重要角色。

==定義==
若一正整數的[[質因數]]均不大於<var>B</var>，此整數即為<var>B</var>-光滑數。例如1620的因數分解為2<sup>2</sup> × 3<sup>4</sup> × 5，質因數均不大於5，因此1620是5-光滑數。

10和12的因數分解分別為2 × 5和2<sup>2</sup> × 3，二者質因數也都不大於5，因此二者均是是5-光滑數，雖然其質因數未包括不大於5的所有質數，但仍然可以是5-光滑數。

5-光滑數常稱為[[正规数_(整数)|正規數]]或漢明數（Hamming numbers）。7-光滑數有時會稱為「謙虛數」或「高合成數」<ref name="humble_number"/>，不過後者會和以因數個數來定義的[[高合成數]]混淆。

<var>B</var>-光滑數的<var>B</var>不一定要是質數，例如上述舉例的10和12不但是5-光滑數，也是6-光滑數（質因數都不大於6）。一般而言會選擇<var>B</var>為質數的<var>B</var>-光滑數，但<var>B</var>也可以是合數。一正整數為<var>B</var>-光滑數[[若且唯若]]正整數為<var>p</var>-光滑數，且<var>p</var>是小於等於<var>B</var>的最大質數。

==應用==
有些[[快速傅里叶变换]]演算法中會用到光滑數，例如[[库利－图基快速傅里叶变换算法]]會將問題一直分解為較小的問題，其大小為原問題大小的因數，若原問題大小是''B''原問題大小，原問題可以分解為許多很小的問題，此情形有有快速的演算法，若大小是較大的質數，就要應用像是[[Chirp-Z 轉換]]之類效率較差的演算法。

5-光滑數〈或稱為[[正规数_(整数)|正規數]]〉在[[巴比倫數學]]中有重要的角色<ref name="Aaboe"/>，在[[音樂理論]]中也很重要<ref name="Longuet-Higgins"/>。有一個[[函數程式語言]]的問題就是要產生正規數<ref name="Dijkstra"/>。

密码学中也有應用光滑數<ref name="David Naccache"/>。雖然大部份的密码学都會用到[[密码分析]]（已知最快的[[因數分解]]演算法），但{{link-en|VSH|Very smooth hash}}雜湊函數利用光滑數來取得{{link-en|可证安全加密散列函数|Provably secure cryptographic hash function}}。

==分佈==
令<math>\scriptstyle \Psi(x,y)</math>表示小於等於''x''的''y''-光滑數的個數（de Bruijn函數）。

若''B''為定值且數值很小，可以用下式估計<math>\scriptstyle\Psi(x,B)</math>:

:<math> \Psi(x,B) \sim  \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p}. </math>
 
其中<math>\scriptstyle{\pi(B)}</math>為小於等於<math>\scriptstyle B</math>的質數個數。

否則，定義參數''u''= log&nbsp;''x''&nbsp;/&nbsp;log&nbsp;''y''：因此，''x'' = ''y''<sup>''u''</sup>，則：

:<math> \Psi(x,y) = x\cdot \rho(u) + O\left(\frac{x}{\log y}\right)</math>

其中<math>\scriptstyle\rho(u)</math>為{{link-en|Dickman函數|Dickman function}}。

==幂次光滑數==<!-- This section is linked from [[Table of prime factors]] -->

若所有可以整除''m''的質數幂次 <math>\scriptstyle p_i^{n_i}</math>滿足以下方程，則''m''為''B''-幂次光滑數：
:<math>p_i^{n_i} \leq B.\,</math>

例如，2<sup>4</sup>3<sup>2</sup>5<sup>1</sup>為5-光滑數，但不是5-幂次光滑數。因為其最大的質數幂次為2<sup>4</sup>，該數為16-幂次光滑數，也是17-幂次光滑數，18-幂次光滑數……。

數論中有用到''B''-光滑數及''B''-幂次光滑數。例如{{link-en|波拉德p-1演算法|Pollard's p &minus; 1 algorithm}}，這類演算法一般會應用在光滑數中，但不會特別標示光滑數的''B''是多少。此時的''B''需是一個較小的整數，若''B''增加，演算法的效率就會迅速的變差。例如計算[[離散對數]]的{{link-en|Pohlig–Hellman演算法|Pohlig–Hellman algorithm}}的時間複雜度是[[大O符号|O]](''B''<sup>1/2</sup>)。

==相關條目==
*[[粗糙數]]
*{{link-en|Størmer定理|Størmer's theorem}}
*[[高合成數]]

==參考資料==
{{reflist|refs=
<ref name="Hellman"> 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, [http://scholar.google.com/scholar?q=%22Adleman+refers+to+integers+which+factor+completely+into+small+primes+as+smooth+numbers.%22 online quote] at Google Scholar: "Adleman refers to integers which factor completely into small primes as “smooth” numbers."
</ref>
<ref name="humble_number">[http://oeis.org/search?q=humble+number&sort=&language=&go=Search OEIS Search]</ref>
<ref name="Aaboe">{{citation
 | last = Aaboe | first = Asger
 | title = Some Seleucid mathematical tables (extended reciprocals and squares of regular numbers)
 | journal = Journal of Cuneiform Studies
 | volume = 19
 | issue = 3
 | pages = 79–86
 | year = 1965
 | id = {{MathSciNet | id = 0191779}}
 | doi = 10.2307/1359089}}.</ref>
<ref name="Longuet-Higgins">{{citation
 | last = Longuet-Higgins | first = H. C.
 | year = 1962
 | title = Letter to a musical friend
 | journal = Music Review
 | issue = August
 | pages = 244–248}}.
</ref>
<ref name="Dijkstra">{{citation
 | last = Dijkstra | first = Edsger W.
 | title = Hamming's exercise in SASL
 | year = 1981
 | url = http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF
 | id = Report EWD792. Originally a privately-circulated handwitten note}}.
</ref>
<ref name="David Naccache">David Naccache, Igor Shparlinski, [http://eprint.iacr.org/2008/437.pdf Divisibility, Smoothness and Cryptographic Applications]</ref>
}}

==外部連結==
{{div col|cols=2}}
* {{mathworld|urlname=SmoothNumber|title=Smooth Number}}
[[整數數列線上大全]]（OEIS）中有包括以下B較小的B-光滑數：
* 2-光滑數：[[OEIS:A000079|A000079]] (2<sup>''i''</sup>)
* 3-光滑數：[[OEIS:A003586|A003586]] (2<sup>''i''</sup>3<sup>''j''</sup>)
* 5-光滑數：[[OEIS:A051037|A051037]] (2<sup>''i''</sup>3<sup>''j''</sup>5<sup>''k''</sup>)
* 7-光滑數：[[OEIS:A002473|A002473]] (2<sup>''i''</sup>3<sup>''j''</sup>5<sup>''k''</sup>7<sup>''l''</sup>)
* 11-光滑數：[[OEIS:A051038|A051038]]
* 13-光滑數：[[OEIS:A080197|A080197]]
* 17-光滑數：[[OEIS:A080681|A080681]]
* 19-光滑數：[[OEIS:A080682|A080682]]
* 23-光滑數：[[OEIS:A080683|A080683]]
{{div col end}}

{{Divisor classes navbox}}

[[Category:解析数论]]
[[Category:整数数列]]