Rusty Smooth Numbers

Rusty Smooth Numbers

Rust is an amazing programming langauge. While it might take a while to master, it is truly rock solid in its robust and access to a wide range of libraries. While Python still feels like an alien lanague to me, Rust just feels so natural. It’s like C, but it’s fit for a modern world. So, let’s take a simple example, and see it in full boom.

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

use std::cmp;
use std::env;

fn findMaxPrimeDivisor(mut n: i32)->i32 {
        
    let mut max_prime_div= 1;
 
    if n == 1 {
        return 1;
    }
 
    while n % 2 == 0 {
        max_prime_div= 2;
        n   = n / 2;
    }
    
    let size =  (f32::powf(n as f32,0.5) as i32) + 1;

    for odd in (3..size).step_by(2) {
        while n % odd == 0 {
        
            max_prime_div= odd;
            n = n/ odd;
        }
    }

max_prime_div= cmp::max (n, max_prime_div);
 
    max_prime_div
}

fn generate_p_smooth(p: i32, end: i32) ->Vec<i32> {
        
    let mut intvec: Vec<i32> = Vec::new();

intvec.push(1);
     
    for i in 2.. (end + 1) {
       if findMaxPrimeDivisor(i) <= p {       
        intvec.push(i);
       }
    }
    return(intvec);

}
fn main() {

let mut vals: Vec<i32> = Vec::new();

let mut p=3;
    let mut end=1000;
    let args: Vec<String> = env::args().collect();
  
    if args.len() >1 { p = args[1].parse().unwrap();}
    if args.len() >2 { end = args[2].parse().unwrap();}

    println!("{}-smooth, end={}",p,end); 
    vals = generate_p_smooth(p, end) ;
    println!("{:?}",vals);
}

A sample run for 3-smooth up to 1,500 is [here]:

3-smooth, end=1500
[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, 1024, 1152, 1296, 1458]

Breaking it down

I like this program, as it highlights some key syntax areas of Rust. One area of Python I really do not like it the usage of the loop() in the for statement. It really doesn’t make any sense for me. In Rust there is a nice simple format. For a loop for i equal to 1 to 10 is:

for i in (1..10){ }

But, how do we increment the value in the loop with a value greater than 1? Well, we have a step_by() modifier. For example, to start at 3 and go up to size, in steps of 2:

for odd in (3..size).step_by(2) {

The definition of functions makes complete sense to me, too. In the following we pass a value of n (which is a 32-bit integer) into the function. We make it mutable, so that we can change it in the function. Then we define the output value (which is a 32-bit integer):

fn findMaxPrimeDivisor(mut n: i32)->i32 {

The way Python can grow arrays is also a little confusion. In Rust, cannot let them grow as they keep their dimensions thoughout the program. To grow a data array, we use a Vector in Rust, and the push() method to add a value onto the end of the vector:

for i in 2.. (end + 1) {
       if findMaxPrimeDivisor(i) <= p {       
        intvec.push(i);
       }

To remove an element, we can use the pop() method. Rust, too, has a wide range of maths functions. In this case we use a power function using floating point values:

let size =  (f32::powf(n as f32,0.5) as i32) + 1;

As we see, Rust is very much focused on data types, and where we formalise the data types we use at any given time. Notice how we use “as f32” to convert an integer to a 32-bit floating point value. If you are interested, here’s the running code:

If you are interested in Rust, here’s a few example related to cryptography:

https://asecuritysite.com/rust/