Smooth number

In number theory, an n-smooth (or n-friable) number is an integer whose prime factors are all less than or equal to n.[1][2] For example, a 7-smooth number is a number in which every prime factor is at most 7. Therefore, 49 = 72 and 15750 = 2 × 32 × 53 × 7 are both 7-smooth, while 11 and 702 = 2 × 33 × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman.[3] Smooth numbers are especially important in cryptography, which relies on factorization of integers. 2-smooth numbers are simply the powers of 2, while 5-smooth numbers are also known as regular numbers.

  1. ^ "P-Smooth Numbers or P-friable Number". GeeksforGeeks. 2018-02-12. Retrieved 2019-12-12.
  2. ^ Weisstein, Eric W. "Smooth Number". mathworld.wolfram.com. Retrieved 2019-12-12.
  3. ^ Hellman, M. E.; Reyneri, J. M. (1983). "Fast Computation of Discrete Logarithms in GF (q)". Advances in Cryptology – Proceedings of Crypto 82. pp. 3–13. doi:10.1007/978-1-4757-0602-4_1. ISBN 978-1-4757-0604-8.