Integer Factorization using Rust

Integer Factorization using Rust

Python is useful, but it struggles in many areas. That said, it has opened-up coding to many and continues to be one of the most useful programming languages. But, it is far from perfect, and it’s the compiled languages that are rising to the top in creating a secure and robust software environment. We must remember that most programming languages were developed in a time where there were no GitHub’s or code that could be versioned and downloaded for code integration. For them, there were static libraries (LIB) and dynamic ones (DLL). Golang and Rust see code libraries as online places to download open-source code, and which can be examined by the developers. So, let’s have a quick look at a simple Rust program to factorize a number.

Factorization

The RSA public key encryption method takes two random prime numbers (p and q) and then multiples them together to give a modulus (N). The strength of the encryption is then based on the hard problem of finding p and q, when we have N. If we can find these, we will break the encryption. And so factorizing an integer is thus a key challenge within encryption.

Overall a non-prime number can be represented by the multiplication of prime numbers. For example, a value of 8 can be represented by 2x2x2, and 6392 by 2x2x2x17x47. The values of 2, 17 and 47 are prime numbers. Within cryptography, we often look for factors in a value, as this can often significantly reduce the overall security of a method. So let’s do some Rust coding [here]:

extern crate reikna;
extern crate thousands;

use reikna::factor::quick_factorize;
use std::env;
use thousands::Separable;



fn main() {
    let mut x=5332;

    let args: Vec = env::args().collect();
  
    if args.len() >1 { x = args[1].parse().unwrap();}


    let fac = quick_factorize(x);

    println!("Input: {}",x.separate_with_commas());
    println!("Factors: {:?}",fac);
    print!("\n {}= ",x);
    let mut count=1;

    for f in fac.iter() {
        count=count+1;
        if fac.len()==count-1 { print!("{:}",f); }
        else { print!("{:}x",f.separate_with_commas()); }
  
    }
}

There are few better development environments than Visual Studio Code. As we see below, it knows the syntax of the language, and tries to automate things:

The staring point of a Rust project is to create a cargo folder:

rust % cargo new factors
     Created binary (application) `factors` package
rust % cd factors
factors % ls
Cargo.lock    Cargo.toml    src        target

In here we see we have a src folder (with main.rs in it), and a Cargo.toml file. The executable file will be placed in the target folder. In Rust, external code is integrated with a crate, and where we create a Cargo.toml to point to the required crate. In this case, we will use the reikna crate, and which can be viewed on docs.rs:

As we can see, the current version is 0.12.3. Visual Studio code makes tracing the versions easy, as it will identify the required one in the toml file:

When we need to integrate constants or methods, we simply integrate the crate with an extern crate line, and then add a use:

Once we have this, it is an easy integration of the factorization code:

let fac = quick_factorize(x);

This passes a 64-bit unsigned integer (x) and returns back a vector containing all of the factors. It is then possible to display this vector with the {:?} format with a println!() statement:

println!("Factors: {:?}",fac);

If we now want to pick off the values in the vector, we can integrate around them:

for f in fac.iter() {
        count=count+1;
        if fac.len()==count-1 { print!("{:}",f); }
        else { print!("{:}x",f.separate_with_commas()); }
  
    }

This will place each value in the vector into f, and then display it. In this case, we want to add a “x” for a multiplication of the factors, but not for the last one. Finally, we just build with “cargo build” and then run with “cargo run”:

Here is a sample run:

Input: 653,764,321,953,243
Factors: [3, 3, 17, 51151, 83536381]

 653764321953243= 3x3x17x51,151x83,536,381

I have added a method that parses an integer with commas for thousands, using the thousands crate.

Here is the finished code:

https://asecuritysite.com/rust/factors

and the Replit code:

https://replit.com/@billbuchanan/rustfactor

The code is not perfect and needs exception catching for the input value from the command line, and also need to support larger values (such as for 128-bit integers and for Big Integers). So, I’ll follow up with another article to show how you do this, and maybe we can crack some large integers.