Pollard-rho algorithm in Rust and rug

Cargo.toml

[package]
name = "pollard_rho"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
rug = "1.20.1"

gistfile1.txt

$ rustc --version
rustc 1.71.1 (eb26296b5 2023-08-03)

$ cargo build -r
   Compiling gmp-mpfr-sys v1.6.0
   Compiling libc v0.2.147
   Compiling az v1.2.1
   Compiling rug v1.20.1
   Compiling pollard_rho v0.1.0 (/home/user/work/pollard_rho/pollard_rho)
    Finished release [optimized] target(s) in 13.66s

$ time ./target/release/pollard_rho 12814570762777948741
12814570762777948741 = 3861801803 * 3318288047

real	0m0.027s
user	0m0.022s
sys	0m0.005s

$ time ./target/release/pollard_rho 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949

real	0m4.038s
user	0m4.027s
sys	0m0.009s


$ python3 --version
Python 3.10.12

$ time python3 pollard_rho.py 12814570762777948741
12814570762777948741 = 3861801803 * 3318288047

real	0m0.218s
user	0m0.204s
sys	0m0.013s

$ time python3 pollard_rho.py 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949

real	0m14.637s
user	0m14.615s
sys	0m0.017s

main.rs

use rug::integer::IsPrime;
use rug::{Assign, Integer};
use std::env;

fn pollard_rho(n: &Integer) -> Option<Integer> {
    let mut x = Integer::from(2);
    let mut y = Integer::from(2);
    let mut d = Integer::from(1);

    while d == 1 {
        x = (x.square() + 1) % n;
        y = (y.square() + 1) % n;
        y = (y.square() + 1) % n;
        d.assign(&x - &y);
        d = d.abs().gcd(n);
    }

    if &d != n {
        return Some(d);
    } else {
        return None;
    }
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let n = Integer::from(Integer::parse(&args[1]).unwrap());

    match n.is_probably_prime(20) {
        IsPrime::Probably | IsPrime::Yes => {
            println!("{} is prime", &n);
        }
        IsPrime::No => match pollard_rho(&n) {
            Some(p) => {
                println!("{} = {} * {}", &n, &p, Integer::from(&n / &p));
            }
            None => {
                println!("{} is prime", &n);
            }
        },
    }
}

pollard_rho.py

import sys
from random import randint
from math import gcd

def miller_rabin(n, k=20):
    s, d = 0, n-1

    while d % 2 == 0:
        s += 1
        d //= 2

    for i in range(k):
        a = randint(2, n-1)
        x = pow(a, d, n)
        if x == 1:
            continue
        for r in range(s):
            if x == n-1:
                break
            x = (x*x) % n
        else:
            return False

    return True

def pollard_rho(n):
    x, y, d = 2, 2, 1

    while d == 1:
        x = (x*x + 1) % n
        y = (y*y + 1) % n
        y = (y*y + 1) % n
        d = gcd(abs(x-y), n)

    if d != n:
        return d

if __name__ == '__main__':
    n = int(sys.argv[1])
    is_prime = miller_rabin(n)
    if is_prime:
        print('{} is prime'.format(n))
    else:
        p = pollard_rho(n)
        print('{} = {} * {}'.format(n, p, n//p))