Skip to content

Instantly share code, notes, and snippets.

@inaz2

inaz2/Cargo.toml

Last active August 17, 2023 03:51
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save inaz2/2aa7931dbe9eee9f126ac92e105e6bcc to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save inaz2/2aa7931dbe9eee9f126ac92e105e6bcc to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. inaz2 revised this gist Aug 17, 2023. 3 changed files with 50 additions and 98 deletions.
    5 changes: 1 addition & 4 deletions Cargo.toml
    View file
    Original file line number Diff line number Diff line change
    @@ -6,7 +6,4 @@ edition = "2021"
    # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

    [dependencies]
    num-bigint = { version = "0.4.3", features = ["rand"] }
    num-integer = "0.1.45"
    num-traits = "0.2.15"
    rand = "0.8.5"
    rug = "1.20.1"
    47 changes: 20 additions & 27 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -1,49 +1,42 @@
    $ rustc --version
    rustc 1.68.0 (2c8cc3432 2023-03-06)
    rustc 1.71.1 (eb26296b5 2023-08-03)

    $ cargo build -r
    Compiling autocfg v1.1.0
    Compiling libc v0.2.141
    Compiling cfg-if v1.0.0
    Compiling ppv-lite86 v0.2.17
    Compiling num-traits v0.2.15
    Compiling num-integer v0.1.45
    Compiling num-bigint v0.4.3
    Compiling getrandom v0.2.9
    Compiling rand_core v0.6.4
    Compiling rand_chacha v0.3.1
    Compiling rand v0.8.5
    Compiling pollard_rho v0.1.0 (/home/user/work/rust/pollard_rho)
    Finished release [optimized] target(s) in 5.30s
    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.099s
    user 0m0.091s
    sys 0m0.000s
    real 0m0.027s
    user 0m0.022s
    sys 0m0.005s

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

    real 0m36.635s
    user 0m36.605s
    sys 0m0.004s
    real 0m4.038s
    user 0m4.027s
    sys 0m0.009s


    $ python3 --version
    Python 3.10.6
    Python 3.10.12

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

    real 0m0.089s
    user 0m0.068s
    sys 0m0.000s
    real 0m0.218s
    user 0m0.204s
    sys 0m0.013s

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

    real 0m16.371s
    user 0m16.334s
    sys 0m0.004s
    real 0m14.637s
    user 0m14.615s
    sys 0m0.017s
    96 changes: 29 additions & 67 deletions main.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,80 +1,42 @@
    use std::{env,process};
    use num_bigint::{BigInt,RandBigInt};
    use num_traits::{One,Signed};
    use num_integer::Integer;

    fn miller_rabin(n: &BigInt) -> bool {
    let k = 20;
    let mut rng = rand::thread_rng();

    let mut s = 0;
    let mut d: BigInt = n - 1;

    while d.is_odd() {
    s += 1;
    d /= 2;
    }

    for _ in 0..k {
    let a = rng.gen_bigint_range(&BigInt::from(2), n);
    let mut x = a.modpow(&d, n);
    if x.is_one() {
    continue
    }
    let mut is_found = false;
    for _ in 0..s {
    if x == n - 1 {
    is_found = true;
    break;
    }
    x = (&x*&x) % n;
    }
    if !is_found {
    return false;
    }
    }

    true
    }

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

    while d.is_one() {
    x = (&x*&x + 1) % n;
    y = (&y*&y + 1) % n;
    y = (&y*&y + 1) % n;
    d = (&x - &y).abs().gcd(n);
    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 {
    Some(d)
    return Some(d);
    } else {
    None
    return None;
    }
    }

    fn main() {
    let args: Vec<String> = env::args().collect();
    if args.len() < 2 {
    println!("Usage: {} N", args[0]);
    process::exit(1);
    }
    let n_buf = &args[1].as_bytes();
    let Some(n) = BigInt::parse_bytes(n_buf, 10) else {
    println!("Error: \"{}\" is not decimal digits.", args[1]);
    process::exit(1);
    };
    let n = Integer::from(Integer::parse(&args[1]).unwrap());

    let is_prime = miller_rabin(&n);
    if is_prime {
    println!("{} is prime", &n);
    } else {
    match pollard_rho(&n) {
    Some(p) => { println!("{} = {} * {}", &n, &p, &n/&p); }
    None => { println!("{} is prime", &n); }
    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);
    }
    },
    }
    }
  2. inaz2 revised this gist Apr 15, 2023. 2 changed files with 56 additions and 11 deletions.
    22 changes: 11 additions & 11 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -14,20 +14,20 @@ $ cargo build -r
    Compiling rand_chacha v0.3.1
    Compiling rand v0.8.5
    Compiling pollard_rho v0.1.0 (/home/user/work/rust/pollard_rho)
    Finished release [optimized] target(s) in 4.51s
    Finished release [optimized] target(s) in 5.30s

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

    real 0m0.095s
    user 0m0.092s
    real 0m0.099s
    user 0m0.091s
    sys 0m0.000s

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

    real 0m36.526s
    user 0m36.469s
    real 0m36.635s
    user 0m36.605s
    sys 0m0.004s


    @@ -37,13 +37,13 @@ Python 3.10.6
    $ time python3 pollard_rho.py 12814570762777948741
    12814570762777948741 = 3861801803 * 3318288047

    real 0m0.074s
    user 0m0.054s
    sys 0m0.012s
    real 0m0.089s
    user 0m0.068s
    sys 0m0.000s

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

    real 0m16.749s
    user 0m16.705s
    sys 0m0.008s
    real 0m16.371s
    user 0m16.334s
    sys 0m0.004s
    45 changes: 45 additions & 0 deletions pollard_rho.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,45 @@
    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))
  3. inaz2 revised this gist Apr 15, 2023. 1 changed file with 4 additions and 1 deletion.
    5 changes: 4 additions & 1 deletion main.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -63,8 +63,11 @@ fn main() {
    process::exit(1);
    }
    let n_buf = &args[1].as_bytes();
    let Some(n) = BigInt::parse_bytes(n_buf, 10) else {
    println!("Error: \"{}\" is not decimal digits.", args[1]);
    process::exit(1);
    };

    let n = BigInt::parse_bytes(n_buf, 10).unwrap();
    let is_prime = miller_rabin(&n);
    if is_prime {
    println!("{} is prime", &n);
  4. inaz2 revised this gist Apr 15, 2023. 1 changed file with 5 additions and 1 deletion.
    6 changes: 5 additions & 1 deletion main.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,4 @@
    use std::env;
    use std::{env,process};
    use num_bigint::{BigInt,RandBigInt};
    use num_traits::{One,Signed};
    use num_integer::Integer;
    @@ -58,6 +58,10 @@ fn pollard_rho(n: &BigInt) -> Option<BigInt> {

    fn main() {
    let args: Vec<String> = env::args().collect();
    if args.len() < 2 {
    println!("Usage: {} N", args[0]);
    process::exit(1);
    }
    let n_buf = &args[1].as_bytes();

    let n = BigInt::parse_bytes(n_buf, 10).unwrap();
  5. inaz2 revised this gist Apr 14, 2023. 2 changed files with 7 additions and 8 deletions.
    10 changes: 5 additions & 5 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -19,15 +19,15 @@ $ cargo build -r
    $ time ./target/release/pollard_rho 12814570762777948741
    12814570762777948741 = 3861801803 * 3318288047

    real 0m0.094s
    user 0m0.089s
    sys 0m0.004s
    real 0m0.095s
    user 0m0.092s
    sys 0m0.000s

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

    real 0m36.070s
    user 0m36.025s
    real 0m36.526s
    user 0m36.469s
    sys 0m0.004s


    5 changes: 2 additions & 3 deletions main.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -17,7 +17,7 @@ fn miller_rabin(n: &BigInt) -> bool {

    for _ in 0..k {
    let a = rng.gen_bigint_range(&BigInt::from(2), n);
    let mut x = BigInt::modpow(&a, &d, n);
    let mut x = a.modpow(&d, n);
    if x.is_one() {
    continue
    }
    @@ -46,8 +46,7 @@ fn pollard_rho(n: &BigInt) -> Option<BigInt> {
    x = (&x*&x + 1) % n;
    y = (&y*&y + 1) % n;
    y = (&y*&y + 1) % n;
    let abs = (&x - &y).abs();
    d = BigInt::gcd(&abs, n);
    d = (&x - &y).abs().gcd(n);
    }

    if &d != n {
  6. inaz2 revised this gist Apr 14, 2023. 2 changed files with 20 additions and 27 deletions.
    12 changes: 6 additions & 6 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -14,20 +14,20 @@ $ cargo build -r
    Compiling rand_chacha v0.3.1
    Compiling rand v0.8.5
    Compiling pollard_rho v0.1.0 (/home/user/work/rust/pollard_rho)
    Finished release [optimized] target(s) in 4.85s
    Finished release [optimized] target(s) in 4.51s

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

    real 0m0.102s
    user 0m0.096s
    sys 0m0.000s
    real 0m0.094s
    user 0m0.089s
    sys 0m0.004s

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

    real 0m38.746s
    user 0m38.696s
    real 0m36.070s
    user 0m36.025s
    sys 0m0.004s


    35 changes: 14 additions & 21 deletions main.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,35 +1,29 @@
    use std::env;
    use num_bigint::{BigInt,ToBigInt,RandBigInt};
    use num_traits::{Zero,One,Signed};
    use num_bigint::{BigInt,RandBigInt};
    use num_traits::{One,Signed};
    use num_integer::Integer;

    fn miller_rabin(n: &BigInt) -> bool {
    let k = 20;
    let mut rng = rand::thread_rng();

    let mut s = 0;
    let mut d = n - BigInt::one();
    let mut d: BigInt = n - 1;

    loop {
    let lsb: BigInt = &d % 2;
    if lsb.is_zero() {
    break;
    }
    while d.is_odd() {
    s += 1;
    d /= 2;
    }

    let two = 2.to_bigint().unwrap();
    let n_1 = n - 1.to_bigint().unwrap();
    for _ in 0..k {
    let a = rng.gen_bigint_range(&two, n);
    let a = rng.gen_bigint_range(&BigInt::from(2), n);
    let mut x = BigInt::modpow(&a, &d, n);
    if x.is_one() {
    continue
    }
    let mut is_found = false;
    for _ in 0..s {
    if x == n_1 {
    if x == n - 1 {
    is_found = true;
    break;
    }
    @@ -44,17 +38,16 @@ fn miller_rabin(n: &BigInt) -> bool {
    }

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

    while d.is_one() {
    x = (&x*&x + BigInt::one()) % n;
    y = (&y*&y + BigInt::one()) % n;
    y = (&y*&y + BigInt::one()) % n;
    let z = &x - &y;
    let abs = BigInt::abs(&z);
    d = Integer::gcd(&abs, n);
    x = (&x*&x + 1) % n;
    y = (&y*&y + 1) % n;
    y = (&y*&y + 1) % n;
    let abs = (&x - &y).abs();
    d = BigInt::gcd(&abs, n);
    }

    if &d != n {
  7. inaz2 created this gist Apr 9, 2023.
    12 changes: 12 additions & 0 deletions Cargo.toml
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,12 @@
    [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]
    num-bigint = { version = "0.4.3", features = ["rand"] }
    num-integer = "0.1.45"
    num-traits = "0.2.15"
    rand = "0.8.5"
    49 changes: 49 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,49 @@
    $ rustc --version
    rustc 1.68.0 (2c8cc3432 2023-03-06)

    $ cargo build -r
    Compiling autocfg v1.1.0
    Compiling libc v0.2.141
    Compiling cfg-if v1.0.0
    Compiling ppv-lite86 v0.2.17
    Compiling num-traits v0.2.15
    Compiling num-integer v0.1.45
    Compiling num-bigint v0.4.3
    Compiling getrandom v0.2.9
    Compiling rand_core v0.6.4
    Compiling rand_chacha v0.3.1
    Compiling rand v0.8.5
    Compiling pollard_rho v0.1.0 (/home/user/work/rust/pollard_rho)
    Finished release [optimized] target(s) in 4.85s

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

    real 0m0.102s
    user 0m0.096s
    sys 0m0.000s

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

    real 0m38.746s
    user 0m38.696s
    sys 0m0.004s


    $ python3 --version
    Python 3.10.6

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

    real 0m0.074s
    user 0m0.054s
    sys 0m0.012s

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

    real 0m16.749s
    user 0m16.705s
    sys 0m0.008s
    81 changes: 81 additions & 0 deletions main.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,81 @@
    use std::env;
    use num_bigint::{BigInt,ToBigInt,RandBigInt};
    use num_traits::{Zero,One,Signed};
    use num_integer::Integer;

    fn miller_rabin(n: &BigInt) -> bool {
    let k = 20;
    let mut rng = rand::thread_rng();

    let mut s = 0;
    let mut d = n - BigInt::one();

    loop {
    let lsb: BigInt = &d % 2;
    if lsb.is_zero() {
    break;
    }
    s += 1;
    d /= 2;
    }

    let two = 2.to_bigint().unwrap();
    let n_1 = n - 1.to_bigint().unwrap();
    for _ in 0..k {
    let a = rng.gen_bigint_range(&two, n);
    let mut x = BigInt::modpow(&a, &d, n);
    if x.is_one() {
    continue
    }
    let mut is_found = false;
    for _ in 0..s {
    if x == n_1 {
    is_found = true;
    break;
    }
    x = (&x*&x) % n;
    }
    if !is_found {
    return false;
    }
    }

    true
    }

    fn pollard_rho(n: &BigInt) -> Option<BigInt> {
    let mut x = 2.to_bigint().unwrap();
    let mut y = 2.to_bigint().unwrap();
    let mut d = 1.to_bigint().unwrap();

    while d.is_one() {
    x = (&x*&x + BigInt::one()) % n;
    y = (&y*&y + BigInt::one()) % n;
    y = (&y*&y + BigInt::one()) % n;
    let z = &x - &y;
    let abs = BigInt::abs(&z);
    d = Integer::gcd(&abs, n);
    }

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

    fn main() {
    let args: Vec<String> = env::args().collect();
    let n_buf = &args[1].as_bytes();

    let n = BigInt::parse_bytes(n_buf, 10).unwrap();
    let is_prime = miller_rabin(&n);
    if is_prime {
    println!("{} is prime", &n);
    } else {
    match pollard_rho(&n) {
    Some(p) => { println!("{} = {} * {}", &n, &p, &n/&p); }
    None => { println!("{} is prime", &n); }
    }
    }
    }