光滑數

维基百科,自由的百科全书
跳转至: 导航搜索

光滑數smooth number)是一個可以因數分解為小質數乘積的正整數。光滑數一詞是是伦纳德·阿德曼所提出[1]。光滑數在以因數分解為基礎的密码学中扮演重要角色。

定義[编辑]

若一正整數的質因數均不大於B,此整數即為B-光滑數。例如1620的因數分解為22 × 34 × 5,質因數均不大於5,因此1620是5-光滑數。

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

5-光滑數常稱為正規數或漢明數(Hamming numbers)。7-光滑數有時會稱為「謙虛數」或「高合成數」[2],不過後者會和以因數個數來定義的高合成數混淆。

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

應用[编辑]

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

5-光滑數〈或稱為正規數〉在巴比倫數學中有重要的角色[3],在音樂理論中也很重要[4]。有一個函數程式語言的問題就是要產生正規數[5]

密码学中也有應用光滑數[6]。雖然大部份的密码学都會用到密码分析(已知最快的因數分解演算法),但VSH英语Very smooth hash雜湊函數利用光滑數來取得可证安全加密散列函数英语Provably secure cryptographic hash function

分佈[编辑]

\scriptstyle \Psi(x,y)表示小於等於xy-光滑數的個數(de Bruijn函數)。

B為定值且數值很小,可以用下式估計\scriptstyle\Psi(x,B):

 \Psi(x,B) \sim  \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p}.

其中\scriptstyle{\pi(B)}為小於等於\scriptstyle B的質數個數。

否則,定義參數u= log x / log y:因此,x = yu,則:

 \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}滿足以下方程,則mB-幂次光滑數:

p_i^{n_i} \leq B.\,

例如,243251為5-光滑數,但不是5-幂次光滑數。因為其最大的質數幂次為24,該數為16-幂次光滑數,也是17-幂次光滑數,18-幂次光滑數……。

數論中有用到B-光滑數及B-幂次光滑數。例如波拉德p-1演算法英语Pollard's p − 1 algorithm,這類演算法一般會應用在光滑數中,但不會特別標示光滑數的B是多少。此時的B需是一個較小的整數,若B增加,演算法的效率就會迅速的變差。例如計算離散對數Pohlig–Hellman演算法英语Pohlig–Hellman algorithm的時間複雜度是O(B1/2)。

相關條目[编辑]

參考資料[编辑]

  1. ^ 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."
  2. ^ OEIS Search
  3. ^ 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 .
  4. ^ Longuet-Higgins, H. C., Letter to a musical friend, Music Review. 1962 (August): 244–248 .
  5. ^ Dijkstra, Edsger W., Hamming's exercise in SASL. 1981, Report EWD792. Originally a privately-circulated handwitten note .
  6. ^ David Naccache, Igor Shparlinski, Divisibility, Smoothness and Cryptographic Applications

外部連結[编辑]

整數數列線上大全(OEIS)中有包括以下B較小的B-光滑數: