Smooth Numbers

Smooth Numbers

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 ×3 ×17 [here]. A value of 56 is 2 ×2 ×2 ×7, and is thus 7-smooth, but not 3-smooth nor 5-smooth. In the following we determine the 3-smooth smooth numbers up to 1,000 [here]:

[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]

and for 5-smooth [here]:

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192, 200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384, 400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675, 720, 729, 750, 768, 800, 810, 864, 900, 960, 972, 1000]

Notice that none of these values has a factor greater than 5, and each can be factorized with values which are less than or equal to 5.

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:

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

If you are interested in integer factorization, such as in cracking the RSA method, here are some methods:

• Difference of squares . Diffsq. This factorizes using the difference of squares method.
• Factors of integers. Factors. Determine factors of an integer.
• Pollard’s ρ method (Factoring integers). Pollard. The Pollard ρ method factorises integers.
• Elliptic Curve method (Factoring integers). Elliptic. The Elliptic Curve method factorises integers.
• Quadratic residue (mod p). Go. Outline of quadratic residue (mod p).