Skip to content

Instantly share code, notes, and snippets.

@inaz2
Last active August 17, 2023 03:51
Show Gist options
  • Save inaz2/2aa7931dbe9eee9f126ac92e105e6bcc to your computer and use it in GitHub Desktop.
Save inaz2/2aa7931dbe9eee9f126ac92e105e6bcc to your computer and use it in GitHub Desktop.
Pollard-rho algorithm in Rust and rug
[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"
$ 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
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);
}
},
}
}
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment