光滑数

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

定义

若一正整数的素因数均不大于B,此整数即为B-光滑数。例如1620的约数分解为22 × 34 × 5,素因数均不大于5,因此1620是5-光滑数。

10和12的约数分解分别为2 × 5和22 × 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英语Very smooth hash杂凑函数利用光滑数来取得可证安全加密散列函数英语Provably secure cryptographic hash function

分布

 表示小于等于xy-光滑数的个数(de Bruijn函数)。

B为定值且数值很小,可以用下式估计 :

 

其中 为小于等于 的素数个数。

否则,定义参数u= log x / log y:因此,x = yu,则:

 

其中 Dickman函数英语Dickman function

幂次光滑数

若所有可以整除m的素数幂次  满足以下方程,则mB-幂次光滑数:

 

例如,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. ^ Gérald Tenenbaum. 解析与概率数论导引. 高等教育出版社. 2011年1月. ISBN 9787040294675. 
  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页面存档备份,存于互联网档案馆

外部链接

整数数列线上大全(OEIS)中有包括以下B较小的B-光滑数: