Miller–Rabin primality test: Difference between revisions

}

}

// is_prime() checks the passed-in number against many known small primes.

// If that doesn't determine if the number is prime or not, then the number

return false

}

let small_primes = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,

47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,

919, 929, 937, 941, 947, 953, 967, 971, 977, 983,

991, 997, 1009, 1013];

use num::traits::Zero; // for Zero::zero()

// Check to see if our number is a small prime (which means it's prime),

// or a multiple of a small prime (which means it's not prime):

for sp in small_primes {

let sp = sp.to_bigint().unwrap();

if n.clone() == sp {

return true

}

}

is_rabin_miller_prime(&n, None)

}

// Note: "use bigint::RandBigInt;" (which is needed for gen_bigint_range())

// fails to work in the Rust playground ( https://play.rust-lang.org ).

return low.clone()

}

let middle = (low.clone() + high) / 2.to_bigint().unwrap();

let go_low: bool = rand::random();

if go_low {

return get_random_bigint(low, &middle)

}

}

// k is the number of times for testing (pass in None to use 5 (the default)).

fn is_rabin_miller_prime<T: ToBigInt>(n: &T, k: Option<usize>) -> bool {

let n = n.to_bigint().unwrap();

use num::traits::{Zero, One}; // for Zero::zero() and One::one()

let zero: BigInt = Zero::zero();

let one: BigInt = One::one();

let two: BigInt = 2.to_bigint().unwrap();

// The call to is_prime() should have already checked this,

// but check for two, less than two, and multiples of two:

}

let n_minus_one: BigInt = n.clone() - &one;

}

// Try k times to test if our number is non-prime:

let a = get_random_bigint(&two, &n_minus_one);

let mut v = modular_exponentiation(&a, &s, &n);

if v == one {

}

let mut i: BigInt = zero.clone();

}

i += &one;

}

}

// If we get here, then we have a degree of certainty

// that n really is a prime number, so return true: