Smooth numbers are used in cryptography to provide fast factorization methods. A smooth number is defined as a number whose factors are smaller than a given value. For a 5-smooth number, the factors must be equal to five or less. Every value, apart from prime numbers can be reduced to the multiplication of prime numbers. For example 102 is equal to 2 x 3 x 17 [here]. A value of 56 is 2 x 2 x 2 x 7, and is thus 7-smooth, but not 3-smooth nor 5-smooth. In the following we determine the smooth numbers up to 1,000:
Smooth Numbers |
Method
Smooth numbers are used in cryptography to provide fast factorization methods. A smooth number is defined as a number whose factors are smaller than a given value. For a 5-smooth number, the factors must be equal to five or less. Every value, apart from prime numbers can be reduced to the multiplication of prime numbers. For example 102 is equal to 2 x 3 x 17 [here]. A value of 56 is 2 x 2 x 2 x 7, and is thus 7-smooth, but not 3-smooth nor 5-smooth.
For 3-smooth we will not have any factors who have prime numbers greater than 3 as factors:
[1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486, 512, 576, 648, 729, 768, 864, 972]
A value of 28, for example has factors of 2×2×7 (where the largest factor is 7), and will thus not be 3-smooth, but 16 will, as it has factors of 2×2×2×2 (where the largest factor is 2).
The following outlines some sample code:
# https://asecuritysite.com/encryption/smooth?Length=10 import sys p = 5 def findMaxPrimeDivisor(n): max_prime_div= -1 if n == 1: return 1 while n % 2 == 0: max_prime_div= 2 n = n // 2 size = int(n ** 0.5) + 1 for odd in range( 3, size, 2 ): while n % odd == 0: max_prime_div= odd n = n // odd max_prime_div= max (n, max_prime_div) return max_prime_div def generate_p_smooth(p, end): smooth = [1] for i in range(2, end + 1): if findMaxPrimeDivisor(i) <= p: smooth.append(i) return smooth print (p,"-smooth\n") end=1000 vals = generate_p_smooth(p, end) print (vals)